[CSAPP] Pipelining - Part 1

1. 파이프라인 동작 방식

---

1-1. 기본

파이프라인 방식으로 구현된 CPU는 위의 그림과 같은 구조를 가진다. 명령어 실행을 위한 과정을 독립적인 N개의 단계로 나누고, 그러한 단계들을 차례차례 거치면서 명령어의 실행이 처리되도록 한다. SEQ 방식은 한 명령어의 실행이 완전히 마무리되어야 다음 명령어를 실행하는 반면, 파이프라인 방식은 한 명령어의 첫 번째 단계 실행만 마무리되면 바로 다음부터 그다음 명령어를 실행하게 된다. 따라서 N개의 단계를 가진 파이프라인 방식에서는 한 순간에 N개의 명령어가 동시에 처리되므로, 처리 속도 측면에서 성능이 상당히 우수하다고 볼 수 있다.

---

1-2. 파이프라인 레지스터

파이프라인 방식을 구현하는 핵심 원리는 바로 단계별로 존재하는 파이프라인 레지스터이다. 특정 단계의 파이프라인 레지스터는 직전 단계의 CLC에서 계산되어 전달받은 값들을 저장하고 있으며, 그 값들을 바탕으로 현재 단계의 CLC가 다음 단계로 전달할 값들을 계산하게 된다. 레지스터의 값은 클락의 Rising-edge 때 변경되므로, 첫 번째 단계부터 시작하여 CLC에 의해 계산되는 값들이 한 사이클마다 한 단계씩 위로 올라가게 된다. 클락의 신호에 따라 레지스터의 값이 변하는 모습을 그림으로 나타내면 다음과 같다.

 

---

1-3. Y86-64 파이프라인 하드웨어 구조

앞선 포스팅에서 설명한 SEQ 방식의 하드웨어 구조는 파이프라인 방식에서 다음과 같이 변화한다. Fetch 단계에서는 현재의 PC 값을 바탕으로 실행할 명령어를 메모리에서 읽고, 명령어의 길이를 바탕으로 다음 PC 값을 계산한다. 그리고 Decode 단계에서는 피연산자에 해당하는 레지스터의 값들을 읽으며, Execute 단계에서 ALU로 연산을 수행한다. Memory 단계에서는 데이터 메모리에 값을 쓰거나 데이터 메모리로부터 값을 읽는다. 마지막으로 Write Back 단계에서는 레지스터에 특정 값을 저장한다.

 

 

Y86-64의 파이프라인 하드웨어 구조를 조금 더 자세히 나타내면 다음 그림과 같다. 각 단계의 파이프라인 레지스터는 직전 단계에서 계산된 값들을 저장하고, 이 값들을 바탕으로 현재 단계의 CLC에서 새로 계산하는 값들은 다음 단계의 파이프라인 레지스터에 입력으로 들어간다. 결국 Fetch 단계부터 계산된 값들은 클락의 신호에 따라 위로 한 단계씩 올라가는데, 그 값들을 중간에 저장하는 것이 파이프라인 레지스터의 역할인 것이다. 참고로 S_Field는 S 단계의 레지스터에 저장된 필드 값, s_Field는 S 단계의 CLC에 의해 계산되는 필드 값을 나타낸다는 것을 기억하도록 하자.

 

 

위의 그림에서 빨간색으로 표시된 피드백(Feedback) 경로들에 대해 간단히만 짚고 넘어가자(추후 자세히 알아볼 예정). 먼저 Predict PC 컨트롤 로직은 다음에 실행할 명령어의 주소를 계산(예측)하는 역할을 수행한다. 그리고 M_Cnd는 조건 이동/분기 명령어 실행 시에 필요한 정보로, 조건 만족 여부를 판단한 결과를 담고 있다. 만약 조건 분기 명령어인데 조건이 만족되지 않은 경우라면, 이때부터는 M_valA의 값에 해당하는 주소에 위치한 명령어를 실행해야 한다. M_valA는 조건이 만족되지 않은 경우에 실행해야 하는 명령어의 주소를 담고 있기 때문이다. 마지막으로 W_valE와 W_valM은 레지스터에 쓸 값에 해당하며, W_valM의 경우 리턴 명령어 실행 시에는 스택에서 팝 한 복귀 주소를 의미하게 된다.

 

2. 파이프라인 성능 비교

2-1. 성능 척도

클락의 Rising-edge에 도달한 시점부터 시작하여, n번째 단계 레지스터의 값이 변경될 때까지 걸리는 시간을 Rn이라고 하자. 그리고 그 레지스터로부터 전달받은 값을 토대로 다음 단계에 전달할 값을 계산할 때까지 걸리는 시간을 Cn이라고 하자. 그러면 총 지연 시간(Overall Latency)은 ∑(Rn+Cn)이 된다. 다음으로, 클락의 주기는 반드시 max(Rn+Cn)보다 크거나 같아야 한다. 그렇지 않으면 한 사이클 내에 전달받은 값을 토대로 다음 단계에 전달할 값을 계산해내지 못하기 때문이다. 마지막으로, 이렇게 구한 클락의 주기에 역수를 취하면 처리량(Throughput), 즉 초당 처리되는 명령어의 수를 계산할 수 있다. 처리량의 단위로는 보통 GIPS(Giga Instructions Per Second)를 사용한다. 성능 척도를 요약하면 다음과 같다.

 

① Rn = 전달받은 값을 레지스터에 저장하는 데 걸리는 시간

② Cn = 다음 단계로 전달할 값을 계산하는 데 걸리는 시간

③ 총 지연 시간 (Overall Latency) = ∑(Rn+Cn)

④ 클락의 주기 = T ≥ max(Rn+Cn) 

⑤ 처리량 (Throughput) = 1/T

 

---

2-2. 성능 이슈 ① - Nonuniform Delays

앞서 언급했듯, CPU의 전반적인 속도를 결정짓는 클락의 주기는 (Rn+Cn)의 최댓값에 의해 결정된다. 즉, 가장 딜레이가 긴 단계에 맞춰서 클락의 주기를 설계하게 된다는 의미이다. 따라서 명령어의 실행 과정을 최대한 비슷한 무게의 단계들로 나누는 것이 중요하다. 한 단계가 지나치게 긴 계산과 딜레이를 요구하면 이에 따라 클락의 주기도 길어져야 하고, 그러면 나머지 단계들은 그 단계 하나 때문에 한 사이클 내에 아무것도 하지 않는 시간이 많아지기 때문이다. 최대한 각 단계가 비슷한 딜레이를 갖도록 설계하면, 클락의 주기를 줄일 수 있기 때문에 처리 속도도 향상될 것이다.

---

2-3. 성능 이슈 ② - Register Overhead

단계의 개수(N)에 따라 파이프라인의 성능은 어떻게 달라질까? 단계가 많으면 기본적으로 한 순간에 처리되는 명령어의 개수가 늘어나며, 하나의 작업을 여러 단계로 쪼갠 결과 각 단계의 딜레이는 짧아지므로 클락의 주기를 더 짧게 만들 수 있다. 하지만 늘 그렇듯 단점도 존재한다. 단계가 늘어날수록 파이프라인 레지스터의 개수가 늘어나므로 총 지연 시간이 증가하고, 각 단계에서 레지스터의 딜레이가 차지하는 비율도 증가한다. 하지만 앞서 언급한 장점의 효과가 더욱 크기 때문에, 현대의 고속 CPU들은 대부분 많은 단계를 갖춘 파이프라인 방식으로 구현되어 있다.

 

3. 파이프라인 주요 이슈

3-1. Data Hazard (RAW Hazard)

직전 명령어의 실행 결과에 해당하는 레지스터의 값을 현재 명령어에서 사용해야 할 때 발생하는 문제이다. 이에 대한 기본적인 해결 방법으로는 Stalling과 Forwarding이 있다. Stalling은 직전 명령어의 실행 결과가 레지스터에 저장이 될 때까지 버블을 끼워 넣으며 기다리는 방식을 의미하며, Forwarding은 직전 명령어의 실행 결과를 계산되는 즉시 현재 명령어에게 전달해주는 방식을 의미한다.

 

Forwarding은 이후 포스팅에서 다루도록 하고, 여기서는 먼저 Stalling에 대해 다뤄보도록 하자. 다음 그림의 예시를 보자. 세 개의 버블을 끼워 넣음으로써 앞선 명령어의 Write Back 단계까지 안전하게 실행된 다음에 addq 명령어가 실행되도록 하고 있다.

 

 

반면에 3개보다 적은 버블을 끼워 넣으면 Data Hazard가 발생한다. 다음은 각각 버블을 2개 끼워 넣은 경우, 1개 끼워 넣은 경우, 끼워 넣지 않은 경우에 해당한다. addq가 잘못된 값을 읽게 되어 오동작을 하는 것을 볼 수 있다.

 

---

3-2. Control Hazard

파이프라인 방식에서는 앞선 명령어의 Fetch 단계 실행이 끝나면 바로 다음 명령어의 실행을 시작해야 한다. 하지만 명령어를 Fetch 단계까지만 실행하고서는 다음에 실행할 명령어가 무엇인지 바로 결정하지 못하는 경우가 있다. 이에 대한 해결 방법으로는 크게 두 가지가 있다. 첫째, 다음에 실행할 명령어의 주소를 예측(Predict)하여 그 명령어를 우선 실행하고, 만약 나중에 그것이 잘못된 예측이었다는 답을 얻게 되면 잘못 실행한 몇 개의 명령어들을 취소시키는 방법이다. 둘째, 다음에 실행할 명령어의 주소를 정확하게 알아낼 때까지는 버블을 삽입하면서 기다리는 방법이다.

 

우리가 구현할 Y86-64 파이프라인에서 다음에 실행할 명령어의 주소, 즉 다음 PC 값을 결정하는 방식은 다음과 같다. 우선 PC 값을 바꾸지 않는 명령어들은 바로 다음 위치(valP)의 명령어를 실행하면 되고, 무조건 분기와 call 명령어도 단순히 다음 PC 값을 valC로 설정하면 된다. 문제는 Fetch 단계에서 다음에 실행할 명령어의 주소를 정확히 알 수 없는 경우이다. 바로 조건 분기 명령어와 ret 명령어이다.

 

조건 분기 명령어의 경우, 다음 PC의 값을 valC로 예상한다(= 일단은 점프한다). 이 경우 만약 실제로 조건이 만족된 것이 맞다면 문제없이 동작할 것이고, 조건이 만족되지 않았다면 틀린 동작이 된다. 조건 만족 여부는 조건 분기 명령어가 Execute 단계에 돌입했을 때 알 수 있는데, 직전 명령어의 실행 결과로 세팅된 컨디션 코드 레지스터의 값을 바탕으로 조건 만족 여부를 그때 계산할 수 있기 때문이다. 또한, 조건 분기 명령어는 조건이 만족되지 않을 경우에 대비하여 조건 분기 명령어 바로 다음 위치 명령어의 주소에 해당하는 valP의 값(Fetch 단계에 계산됨)을 계속 위로 들고 올라간다. 따라서 Memory 단계에 돌입하여 M_Cnd의 값을 통해 조건이 만족되지 않았음을 파악하게 되면, M_valA로 전달받은 값을 바탕으로 다시 올바른 명령어를 실행하게 된다. 그리고 이 순간에 Decode와 Execute 단계에 위치하는 2개의 명령어는 잘못 실행된 명령어이므로 적절한 과정을 거쳐 이 둘을 취소시켜야 할 것이다(이 과정은 추후 설명).

 

ret 명령어의 경우, 예측이라는 것을 할 수 없으므로 복귀 주소를 알아낼 때까지 버블을 삽입하며 기다린다. 복귀 주소는 reqt 명령어가 Memory 단계에 돌입했을 때 알 수 있는데, 그때 메모리에서 복귀 주소를 팝 할 수 있기 때문이다. 따라서 최소한 세 사이클은 버블을 끼워 넣으면서 기다려야 하고, Write Back 단계에 돌입하여 W_valM의 값을 통해 복귀 주소를 알아내면 그 주소에 해당하는 명령어를 Fetch 단계에서 실행하게 된다. 그리고 이 순간에 Decode, Execute, Memory 단계에 위치하는 3개의 명령어는 잘못 실행된 명령어이므로 적절한 과정을 거쳐 이 셋을 취소시켜야 할 것이다(이 과정은 추후 설명).

 

3-2-1. 조건 분기 명령어 예시 (예측이 틀린 경우)

 

3-2-2. ret 명령어 예시