[Computer Architecture] (1-1) Pipelining

Pipeline은 하나의 테스크를 여러 개의 하위 테스크로 나누고 이를 동시에 수행하여 테스트 처리량을 높이는 기술이다.
가장 유명한 예제는 옷을 세탁하는 테스크를 수행하는 것이다.
옷을 세탁하는 테스크을 세탁->건조->접기->수납 4가지 하위 테스크로 나눈다.
2개의 세탁물을 수행하려면 아래와 같이 순차적으로 진행할 수 있다.
(각 세탁물을 A, B로 지정하고, 각 하위 테스크별 시간은 1시간이라 가정하자.)
============================================
          1         2          3         4        5        6          7          8
A :  세탁-->건조-->접기-->수납
B :                                                 세탁-->건조-->접기-->수납
============================================
위와 같이 순차적으로 수행하면 8시간이 걸린다.
그런데 '2'에 해당하는 시점에 보면 건조기로 건조를 수행하지만, 세탁기는 놀고 있는 상태이다.
세탁기가 놀고 있으므로 세탁물 B의 세탁을 수행하면 시간을 아낄 수 있다. 즉 아래와 같이 각 세탁물을 동시에 수행할 수 있다.
============================================
          1         2          3         4          5        6          7          8
A :  세탁-->건조-->접기-->수납
B :              세탁-->건조-->접기-->수납                                
============================================
위와 같은 경우, 5시간 안에 수행이 끝난다.

여기서 잘 살펴보면, 세탁물을 처리하는 시간 자체는 줄어들지 않았다. 다만, 2개의 세탁물을 처리하는 데 걸리는 시간이 8시간에서 5시간으로 줄어들었다. 즉, 시간당 처리하는 양(Trroughput)이 증가하였다. Pipeline은 각 테스크에서 수행되는 일의 양을 줄이는 것이 아니라 처리하는 일을 중첩하여 일의 처리량을 늘린다.

파이프라인의 원리에 알았으니 어떻게 파이프라인을 구성할 수 있을 지에 대해서 알아보자.
예를 들어 햄버거를 만드는 가게에서 햄버거 만드는 처리량을 높이고자 파이프라인을 도입하려고 한다. 파이프라인 스테이지를 만들기 앞서, 햄버거를 만드는 과정이 어떤 과정으로 발생하는 지 파악해야한다. 이 햄버거 집에는 2 종류의 버거가 있다. 클래식 버거와 '고기고기' 버거 이다.
클래식 버거는 빵, 고기, 치즈, 야채로 구성되어 있고, '고기고기' 버거는 빵, 고기, 치즈로 구성되어 있다. 클래식 버거를 만드는 순서는 빵 굽고 넣고, 고기 굽고 넣고, 치즈 넣고, 야채 넣고, 빵 굽고 넣고 완성한다.
'고기고기'버거를 만드는 순서는  빵 굽고 넣고, 고기 굽고 넣고, 치즈 넣고,  빵 굽고 넣고 완성 한다.
이를 아래와 같이 간단히 표현해보자
> 클래식 버거      : 빵(1) -> 고기 -> 치즈 -> 야채 -> 빵(2)
> '고기고기' 버거 : 빵(1) -> 고기 -> 치즈  ->빵(2)

두 버거를 만드는 과정에 필요한 과정들을 나열하면 아래와 같다.
> 빵, 고기, 치즈, 야채

이와 같은 순서로 파이프 라인을 만들어 보자
============================================
                                  1            2          3           4           5         6
> 클래식 버거      :   빵(1)   고기      치즈     야채     빵(2)  
> '고기고기 버거' :                빵(1)    고기     치즈     xxxx   빵(2)
============================================
시점 5에서의 동작을 살펴보자, '고기고기' 버거는 야채를 올리는 동작이 없으므로 빵(2)를 수행할 수 있다. 그런데 앞 서 클래식 버거가 빵(2)를 수행하고 있기 때문에, 해당 동작은 수행할 수 없으므로 야채를 만드는 사람은 아무것도 하지 않고 기다려야 한다.
이렇듯 여러 동작을 수행하는 파이프 라인을 만들기 위해서는 모든 동작이 포함되어야 하며, 일부 동작에서는 수행하지 않는 동작으로 인하여 아무것도 하지 않는 상태가 될 수도 있다.

이는 낭비가 될 수 있다. 이를 고려해서 다시 파이프라인을 구성해보자.
마침, 치즈와 야채를 놓는 단계를 살펴보니, 해야하는 작업량이 많지 않고, 서로 비슷하게 놓는 일을 수행한다. 따라 이를 나누지 않고 하나로 합쳐서 진행해도 무방해보인다. 그래서 파이프 라인을 아래와 같이 변경하였다. 이런 경우, 멈추지 않고 파이프라인이 진행됨을 알 수 있다.
============================================
                                  1            2                3               4                 5        
> 클래식 버거      :   빵(1)   고기      치즈/야채      빵(2)  
> '고기고기 버거 :                빵(1)          고기     치즈/야채       빵(2)
============================================

이제 파이프 라인이 멈추지 않고 진행 되므로 순차적으로 잘 동작하는 것처럼 보였지만, 특정 구성원들의 불만이 쌓이는 것이 보였다. 왜 그런가 살펴보니 어떤 직원들은 계속 바쁘게 일하고, 어떤 직원들은 쉬고 있는 것이 확인된 것이다. 어떤 여유인지 살펴보니 고기 작업에 필요한 시간과 치즈/야채 작업에 필요한 시간이 서로 차이가 났다. 그래서 고기 작업을 수행하는 사람은 쉴틈 없이 일하고 치즈/야채를 만드는 사람은 일을 수행하고, 잠시 쉬고 있었다. 고기 작업을 수행하는 시간으로 인하여 다른 과정에서 쉬고 있는 시간이 늘어났고, 이는 햄버거 만드는 처리량이 작아지는 결과를 보였다.
이렇듯 각 파이프 라인은 동시에 수행되므로 가장 오래 걸리는 테스크를 기준으로 수행되고, 그렇지 않는 테스크는 나머지 시간 동안 아무것도 수행하지 않는다. 즉, 파이프 라인의 처리량은 가장 오래걸리는 테스크로 결정된다.  

이를 해결하는 방법에는 여러 가지가 있다. 종업원을 한 명 더 고용하여 고기 작업을 수행하는 테스크를 두 개로 나누는 방법과 치즈/야채를 수행하는 종업원의 업무에 빵(2)를 추가하여 더 늘리는 방법이 있다.
첫 번째 방법은 파이프 라인의 스테이지는 고기 -> 고기(1) + 고기(2)로 한 스테이지 더 늘지만, 각 스테이지의 속도를 높이는 방법이고, 두 번째 방법은 파이프 라인의 스테이지를 치즈/야채 -> 빵(2)를 치즈/야채/빵(2)로 합쳐서 한 스테이지를 더 줄이고, 각 스테이지의 속도는 그대로 두는 방법이다.

어떤 방법이 더 좋을 지는 파이프 라인의 처리량을 계산해보면 알 수 있다.
첫 번째 방법은 6개의 스테이지와 각 스테이지 별 걸리는 시간은 'X'라 하자.
두 번째 방법은 4개의 스테이지와 각 스테이지 별 걸리는 시간은 'Y(>'X')'라 하자.
계산 하기 쉽게 햄버거의 주문은 무한히 들어와서, 계속 햄버거를 만드는 작업을 수행한다고 가정하자. 이런 경우 모든 파이프라인 의 스테이즈는 계속 동작하고 있을 것이다.
그러면 매 스테이지 마다 햄버거는 완성될 것이다. 각 스테이지 별 걸리는 시간이 작을 수록 처리량이 높다는 것을 알 수 있다. 이렇듯 각 스테이지 별로 걸리는 시간이 작은 첫번 째 방법이 더 빠른 처리량을 수행할 수 있다.

각 스테이지 별로 처리량이 가장 적은게 좋다면, 아주 세분화하여 고기 작업을 고기(1) -> 고기(2) -> 고기(3) -> ... 이렇게 많이 나눠서 사용하면 좋을 까? 그렇지 않을 수도 있다.
각 작업을 수행하는 사람들끼리 처리한 작업을 주고 받는 데도 시간이 소요되기 때문이다.
따라서 파이프라인의 스테이지를 나눌 때는 각 스테이지 별 작업량 뿐만 아니라 스테이지 간의 작업 물을 주고 받는 시간도 고려해야 한다.

이와 같은 개념을 CPU에서 Instruction을 처리하는 데 적용을 해보자. Pipeline은 하나의 테크스를 하위 테스크들로 나누는 것으로 부터 시작한다. 그렇다면 Instruction을 수행하는 과정을 살펴보고 어떻게 나눌 수 있는 지 살펴봐야한다. 예를 들어 Instruction 'ADD X3, X2, X1'를 수행하는 과정을 생각해보자. 제일 처음 수행해야 하는 일은 Instruction 'ADD X3, X2, X1'를 메모리로부터 읽어와야 한다. 모든 Instruction은 메모리에 저장되어 있으며, 이를 순차적으로 읽어가면서 동작을 수행한다.
그 다음에는 Memory로부터 읽어온 Instruction이 어떤 형태인지를 파악해야 한다.  즉 'ADD', 'LD', 'ST'인가? Source/Destination 은 어디 인가? 등을 알아야 수행할 수 있기 때문이다. 해당 동작에 대한 정보를 알았다면 이제 실제 동작을 수행할 수 있다. 수행이 완료되면 수행 결과물을 저장해야 한다. ADD Instruction은 Register에 해당 수행 결과를 저장한다.
요약하면 아래와 같다.
1. 메모리로부터 Instruction을 읽어 오기
2. 어떤 Instruction인지 확인하기
3. 'ADD' 연산 수행
4. Register에 저장.
또 다른 Instruction인 'ld x1, x2'를 살펴보자. 'ld'는 메모리로부터 데이터를 읽어와서 register에 적는 동작이다. 앞 'ADD'와 마찬가지로 메모리로부터 Instruction을 읽어 오고, 어떤 instruction인지를 파악하고, 메모리로부터 데이터를 가져와서 register에 저장한다. 요약하면 아래와 같다.
1. 메모리로부터 Instruction을 읽어 오기
2. 어떤 Instruction인지 확인하기
3. Memory로부터 데이터 읽어오기
4. Register에 저장.
이런 Instruction에 수행하는 동작을 모두 모아서 표현하면 아래와 같다.
IF(Intruction Fetch)       :: 메모리로부터 Instruction 읽어오기
ID(Instruction decode) :: 어떤 Instruction인지 확인 및 Source Register 읽기
EX(Execute)                    :: 연산 수행
MEM(Memory)              :: Memory 접근
WB(Wrtie Back)             :: 연산 결과 Register에 저장.

해당 과정들을 파이프라인으로 구성하여 수행할 수 있다. '햄버거 가게' 예시처럼 각 과정들을 좀 더 세분화하여 파이프라인을 구성하여 처리량을 높일 수 도 있다. 우선은 이해하기 쉽게 각 과정이 하나의 파이프라인 스테이지라고 가정하고 앞으로 설명을 진행하겠다.