[CSAPP] Pipelining - Wrap up

1. Exception Handling

1-1. 기본

CPU가 정상적으로 명령어 실행을 계속할 수 없는(계속하면 안 되는) 상황에 부딪혔을 때, 예외가 발생했다고 표현한다. 우리의 Y86-64 파이프라인 CPU에서 발생할 수 있는 예외의 종류는 크게 세 가지이다. Halt 명령어를 실행했을 때, 명령어/데이터 메모리에 잘못된 주소로 접근했을 때, 유효하지 않은 명령어를 실행했을 때이다. 이러한 예외가 발생했을 때 처리하는 방법은 여러 가지가 있을 수 있다. 무슨 방법을 채택하든, 중요한 것은 예외가 발생한 명령어부터 그 이후의 명령어들은 전혀 실행되지 않은 것처럼(아무런 프로세스 상태가 변하지 않도록) 처리해야 한다는 것이다. Sequential Implementation과 동일해야 Correctness가 보장되기 때문이다. 그리고 우리가 다루는 Y86-64 파이프라인 CPU는 예외가 발생하면 프로그램을 중단시키는 방식을 택한다. 즉, 예외가 발생한 명령어부터 그 이후의 명령어들은 실행되지 않게 하고, 현재 프로그램의 실행을 중단시키는 것이다.

---

1-2. 예외 발생 시점

예외가 발생할 수 있는 시점은 바로 Fetch와 Memory 단계이다. Fetch 단계에서는 Halt 명령어를 실행하거나, 명령어 메모리에 잘못된 주소로 접근하거나, 유효하지 않은 명령어를 실행하는 경우에 예외 발생을 감지할 수 있다. 그리고 Memory 단계에서는 데이터 메모리에 잘못된 주소로 접근하는 경우에 예외 발생을 감지할 수 있다.

---

1-3. 예외 처리

1-3-1. 예외 발생을 감지하면 이를 즉시 처리하면 되는 것일까?

그렇지 않다. 이유는 두 가지이다. 첫째, 파이프라인의 명령어 실행 흐름 상 먼저 예외를 발생시키는 명령어가 먼저 예외 발생이 감지된다는 보장이 없기 때문이다. 예를 들어, 데이터 메모리에 잘못된 주소로 접근하는 명령어가 Memory 단계에 진입하기 전에 유효하지 않은 명령어가 Fetch 단계로 진입하면, Fetch 단계에서 먼저 예외 발생이 감지된다. 둘째, 조건 분기 명령어의 경우 Branch Prediction 전략을 사용하는데, 만약 잘못 실행된 명령어라면 여기서 예외가 발생하더라도 이를 처리하면 안 되기 때문이다.

 

1-3-2. 그렇다면 예외는 언제 처리해야 할까?

모든 예외 발생은 Write Back 단계에 진입했을 때 처리하기로 약속한다. 이렇게 하면 먼저 예외를 발생시키는 명령어가 반드시 먼저 처리된다고 보장할 수 있기 때문이다. 이 방식을 위해서는 Fetch 단계에서부터 시작하여 예외 발생 여부를 나타내는 값(stat)을 파이프라인 레지스터를 통해 계속 위로 들고 올라가야 한다. stat 값이 설정될 수 있는 시점은 앞서 말했듯 Fetch와 Memory 단계이다. Decode와 Execute 단계에서는 예외 발생이 감지될 일이 없으므로 직전 단계로부터 전달받은 stat 값을 그대로 위로 전달하기만 하면 된다. 다음은 이와 관련된 HCL 코드를 나타낸다.

 

 

1-3-3. stat 값이 Write Back 단계까지 전달되면

Write Back 단계까지 전달된 stat의 값을 Stat 레지스터에 저장함으로써 예외 처리를 시작하게 된다. 단, W_stat 값을 Stat 레지스터에 그대로 저장하는 건 아니다. 조건 분기 명령어의 Branch Prediction 전략에 의해 잘못 실행된 명령어들은 최대 Deocde 단계까지 이르렀다가(그래서 아무러한 Side Effect를 발생시키지 않음) 이후 버블로 바뀌는데, 그때 stat 값은 파이프라인 컨트롤 로직에 의해 SBUB로 변경된다. 따라서 Write Back 단계로 전달받은 W_stat 값이 SBUB인지 검사하는 과정이 선행되어야 한다. 만약 W_stat 값이 SBUB라면 Stat 레지스터에 SAOK를 저장함으로써 해당 예외 발생을 무시해야 하고, 아니라면 W_stat 값을 그대로 저장하면 된다. 다음은 이와 관련된 HCL 코드와 Y86-64 CPU 하드웨어 구조를 나타낸다.

 

 

1-3-4. Write Back 단계에서 예외를 처리하기 때문에 생길 수 있는 문제

예외 처리의 핵심은 예외를 발생시키는 명령어 이후부터의 명령어가 전혀 실행되지 않은 것처럼 처리가 되어야 한다는 것이다. 그러나 지금까지 설명한 예외 처리 방식에 따르면, 예외를 발생시킨 명령어가 Write Back 단계에 돌입하기 전에 뒤따라오는 다른 명령어들에 의해 프로세서 상태가 변할 수 있다(Side Effect 발생). 예를 들어, 예외를 발생시킨 명령어가 Memory 단계에 있을 때 컨디션 코드 레지스터의 값을 바꾸는 명령어가 Execute 단계에 있다면, 다음 사이클이 되었을 때 바뀌면 안 되는 컨디션 코드 레지스터의 값이 바뀌게 될 것이다. 따라서 Side Effect를 방지하기 위한 로직이 별도로 필요하다.

 

1-3-5. Side Effect를 방지하는 예외 처리 로직

어떠한 명령어이든, 최소한 Memory 단계에는 해당 명령어의 예외 발생 여부를 알 수 있다. 예외가 발생하는 시점은 Fetch 단계와 Memory 단계뿐이기 때문이다. 그리고 현재 명령어가 Memory 단계에 있을 때 바로 뒤따라오는 명령어는 Execute 단계에 있는데, Execute 단계는 프로세서의 상태를 바꿀 수 있는 최초의 단계이다. 컨디션 코드 레지스터의 값을 세팅하기 때문이다. 결론적으로, Side Effect를 방지하기 위해서는 예외를 발생시키는 명령어가 Memory 단계에 돌입하는 순간부터 별도의 처리 작업을 수행해야만 한다.

 

먼저, Memory 단계에서 예외 발생이 감지되면(m_stat이 예외 발생을 나타냄), 파이프라인 컨트롤 로직은 컨디션 코드 레지스터의 값이 변경되지 않도록 컨트롤 신호를 발생시켜서(set_cc 비활성화) 동일 사이클 내의 Execute 단계에 존재하는 명령어에 의해 컨디션 코드 레지스터가 세팅되지 않도록 해야 한다. 마찬가지 방식으로, 데이터 메모리의 값도 변경되지 않도록 적절히 컨트롤 신호를 발생시켜야 한다. 그러면 다음 사이클이 되어도 프로세서 상태에 해당하는 컨디션 코드 레지스터와 데이터 메모리가 변하지 않고 유지될 것이다. 마지막으로, Memory 단계의 레지스터에는 Bubble 신호를 주입하여 이후부터 뒤따라오는 명령어들은 전부 Memory 단계에서 취소되도록 한다.

 

그러면 다음 사이클에는 예외 발생이 감지된 명령어가 Write Back 단계에 도달하게 된다(w_stat이 예외 발생을 나타냄). 이때도 마찬가지로 뒤따라오는 명령어들에 의한 Side Effect는 방지해야 하므로 컨디션 코드 레지스터와 데이터 메모리가 변하지 않도록 동일하게 컨트롤 신호를 발생시켜야 하며, Memory 단계의 레지스터에도 Bubble 신호를 주입해야 한다. 더불어서, Write Back 단계의 레지스터에는 Stall 신호를 주입함으로써 예외를 발생시킨 명령어는 Write Back 단계에 계속 가만히 있도록 한다.

 

다음은 예외를 발생시키는 명령어가 Memory, Write Back 단계에 있을 때 Side Effect를 방지하기 위한 로직을 나타낸다.

 

---

1-4. 실제 CPU의 예외 처리 방식

물론 지금까지 설명한 예외 처리 방식은 현대의 실제 CPU들이 예외를 처리하는 방식과는 약간 차이가 있다. 그렇다면 현대의 실제 CPU는 어떤 방식으로 예외를 처리할까? 위 방식과 대체적으로 유사하지만, 가장 큰 차이점은 단순히 현재 프로그램의 실행을 중단시키는 것이 아니라 OS의 예외 핸들러를 호출한다는 점이다. 이를 위해서는 복귀 주소에 해당하는 PC 값을 계속 위로 들고 올라가도록 설계해야 하며, Memory 단계까지 도달하면 그 복귀 주소를 데이터 메모리의 스택에 푸시하도록 컨트롤 신호를 조정해야 하고, 마지막으로 Write Back 단계까지 도달하면 w_stat의 값을 토대로 적절한 예외 핸들러의 주소에 해당하는 명령어를 Fetch 단계로 진입시켜서 예외 핸들러 코드를 실행시켜야 한다는 것을 유추해볼 수 있다. 참고로 기본적으로 예외의 종류와 각 예외 핸들러의 주소는 ISA에 명시되어 있다.

 

2. Performance Analysis

2-1. 클락 속도 (Clock Rate)

클락의 속도를 결정짓는 척도는 바로 진동수(Frequency)이다. 즉 1초에 진동하는 횟수가 클락의 속도를 나타내며, 일반적으로 단위는 GHz를 사용한다. 1GHz는 1초에 10^9번(≒ 2^30번) 진동함을 의미한다. 진동수는 파이프라인의 단계를 몇 개로 나누는지 등의 CPU 디자인 방식에 따라 크게 달라진다. 예를 들어, 파이프라인의 단계를 여러 개로 쪼갤수록 각 단계의 딜레이는 짧아지므로 클락 주기도 짧아진다(클락 진동수 증가).

---

2-2. CPI (Cycles Per Instruction)

CPI는 평균적으로 한 명령어를 실행하는 데 필요한 클락 사이클의 수로, 명령어 실행 속도를 나타내는 척도이다. 파이프라인 방식에서는 매 사이클마다 한 명령어의 실행이 완료되기 때문에 이상적으로는 CPI가 1이라고 할 수 있다. 이때 CPI를 각 명령어를 실행하는 데 걸리는 총시간을 의미하는 Latency와 혼동하지 말아야 한다. 예를 들어, 우리가 다룬 Y86-64 파이프라인 방식을 기준으로, CPI는 이상적으로 1이지만 각 명령어의 Latency는 다섯 사이클이다.

 

그러나 실제로는 CPI가 1보다 크다. 지금까지 알아보았듯이, 상황에 따라 명령어가 다음 단계로 진입하지 못하고 Stall 하는 경우도 있고 특정 단계에 버블을 삽입하기도 하기 때문이다. 그래서 실제 CPI는 파이프라인을 어떻게 디자인하느냐, 그리고 벤치마크 프로그램(CPI를 측정하기 위해 사용하는 실험용 프로그램)으로 무엇을 사용하느냐에 따라서 조금씩 달라질 수 있다.

 

그렇다면 실제 CPI는 어떻게 계산해볼 수 있을까? 총 I개 명령어의 실행을 완료했고, 그때까지 소요된 클락 사이클의 수를 C라고 해보자. 그리고 명령어 실행 과정에서 삽입된 버블의 개수를 B라고 하자. 그러면 C는 (I+4+B)와 같다. 버블이 아예 삽입되지 않았다면 총 (I+4)번의 사이클을 거쳐서 I개 명령어의 실행을 마쳤을 테지만, 중간에 B개의 버블을 삽입함으로써 총 B번의 사이클 추가로 소요했기 때문이다. 따라서 실제 CPI는 ((I+4+B)/I)로 계산 가능하다. 이때 I가 충분히 크다면 4는 무시할 수 있으므로, 실제 CPI는 (1+(B/I))가 된다.

 

따라서 이론적인 CPI와 실제 CPI의 차이를 만들어내는 핵심은 바로 (B/I)이다. 즉, 평균적으로 한 명령어를 실행하는 데 삽입되는 버블의 개수를 계산해볼 수 있다면, 실제 CPI도 알아낼 수 있다. 그렇다면 우리의 Y86-64 파이프라인 방식을 기준으로 (B/I)는 어떻게 계산해볼 수 있는지 알아보도록 하자. 방법은 총 세 가지이다. 이어지는 설명을 참고하자.

---

2-3. CPI를 증가시키는 페널티 요소

지금까지 알아본 내용에 따르면 일반적인 명령어 실행 흐름에 클락 사이클 페널티를 부여하는 상황은 총 세 가지이다. 첫째는 Load/Use Hazard, 둘째는 Branch Misprediction, 마지막은 Return 명령어이다. 따라서 각 상황별로 한 명령어 당 삽입되는 평균적인 버블의 개수를 구하고, 그것들을 모두 더해서 B/I를 계산해 보도록 하자. 그러면 실제 CPI가 얼마나 되는지 유추해볼 수 있을 것이다.

 

2-3-1. Load/Use Hazard에 의한 페널티 (= LP)

① Load 명령어의 비율 = 0.25

② Stalling을 요구하는 Load 명령어의 비율 = 0.20

③ Load/Use Hazard가 발생할 때마다 삽입되는 버블의 개수 = 1

⇒ LP = 0.25 x 0.20 x 1 = 0.05

 

2-3-2. Branch Misprediction에 의한 페널티 (= MP)

① 조건 분기 명령어의 비율 = 0.20
② 조건 분기 명령어의 예측이 틀릴 확률 = 0.40
③ Branch Misprediction이 발생할 때마다 삽입되는 버블의 개수 = 2
⇒ MP = 0.20 x 0.40 x 2 = 0.16

 

2-3-3. Return 명령어에 의한 페널티 (= RP)

① Return 명령어의 비율 = 0.02
② Return 명령어 하나가 실행될 때마다 삽입되는 버블의 개수 = 3
⇒ RP = 0.02 x 3 = 0.06

 

∴ B/I = LP + MP + RP = 0.05 + 0.16 + 0.06 = 0.27

∴ CPI = 1 + B/I = 1 + 0.27 = 1.27

 

3. Modern CPU Design (Out-of-order Execution)

현대의 실제 CPU들은 우리가 배운 것보다 훨씬 복잡하고 정교하게 설계가 된다. 그래서 현대의 실제 CPU들이 어떤 방식으로 디자인이 되는지에 궁금한 사람들을 위해 여기서 몇 가지 내용만 간단히 설명하고자 한다. 중요한 내용은 아니니 참고만 하도록 하자.

---

3-1. 가상 메모리 (Virtual Memory)

이는 이후 포스팅에서 아주 자세히 다룰 내용이므로, 여기서는 핵심만 간단히 소개하고 넘어가겠다. 실제로는 프로그램이 실행될 때 해당 프로그램의 데이터와 코드가 전부 메인 메모리에 올라가지 않는다. 대신에 그 프로그램의 데이터와 코드가 차지하는 메인 메모리의 영역에 해당하는 카피본을 하드 디스크에 올린다. 그리고 그 프로그램이 실행 도중 자주 접근하는 부분만 하드 디스크에서 꺼내와 메인 메모리에 두는 방식을 택한다. 만약 현재 메인 메모리에 올라와 있지 않은 부분에 대한 참조가 필요해지면, 내부적으로 예외가 발생하여 하드 디스크에게 그 부분을 가져오라고 신호를 보낸 뒤 CPU의 제어는 다른 프로세스에게 넘겨준다. 그러다가 하드 디스크가 요청된 부분을 메인 메모리에 올리는 작업을 마무리하면, CPU에게 인터럽트를 걸어서 다시 해당 프로그램이 실행될 수 있게 한다. 그러면 아까는 참조에 실패했던 부분을 이제는 메인 메모리에 올라와 있어서 참조할 수 있게 되었으므로 정상적으로 명령어 실행을 할 수 있게 된다.

---

3-2. 동적 파이프라인 스케쥴링 (Dynamic Pipeline Scheduling)

우리는 앞서 파이프라인의 주요 이슈 중 Data Hazard와 Control Hazard를 해결하는 몇 가지 방법을 알아본 바 있다. 하지만 우리가 알아본 것 말고도 실제로 현대의 CPU들은 다양한 방법을 통해 그러한 이슈들을 해결한다. 예를 들어 Data Hazard는 Out-of-order Execution이라는 방식으로 해결하고, Control Hazard는 Speculative Execution이라는 방식으로 해결한다. 각각에 대해 간단히만 알아보자.

 

3-2-1. Out-of-order Execution

우리가 지금까지 알아본 파이프라인 방식은 In-order Execution에 해당한다. 즉, 명령어의 실행 순서는 반드시 지킨다는 것이다. 하지만 Out-of-order Execution 방식은 그렇지 않다. 필요한 경우에는 나중에 실행되어야 할 명령어를 먼저 실행함으로써 Data Hazard를 해결하고 성능을 향상시킨다. 예를 들어, 다음과 같은 어셈블리어 코드가 있다고 해보자.

 

divq r1, r2

addq r2

subq r4, r5

 

In-order Execution 방식에서는 위와 같은 상황에서 Load/Use Hazard가 발생하면 두 번째 명령어를 바로 실행하지 못하고 Stall을 해야 한다. 그런데 이렇게 되면 그 이후의 명령어들도 전부 한 사이클만큼 기다리게 되는 결과를 초래한다. 그러나 세 번째 명령어는 사실 앞선 두 개의 명령어와 아무런 연관이 없기 때문에 기다릴 필요가 없기 때문에 억울할 수 있다. 이런 경우에 세 번째 명령어를 먼저 실행할 수 있도록 하는 것이 Out-of-order Execution 방식이다. 자세한 내용은 직접 찾아보기를 권한다.

 

3-2-2. Speculative Execution

Branch Prediction에 지역성(Locality)을 활용하는 사례이다. 우리가 알아본 Branch Prediction이 정적으로 조건 만족 여부를 예측하는 것이라면, 이는 동적으로 조건 만족 여부를 예측한다. 조금 더 구체적으로 설명하자면, 조건 분기 명령어들의 조건 만족 여부 역사를 내부적으로 기억해두고, 이 정보를 바탕으로 현재 조건 분기 명령어의 조건 만족 여부를 예측하는 것이다. 예를 들어, 조건 만족 여부 역사를 2비트로 인코딩한다고 할 때 그것을 담당하는 상태 기계는 다음과 같은 구조를 갖게 된다.

 

 

조건 분기 명령어가 조건을 만족할 때마다 왼쪽으로 한 칸 이동하고, 조건을 만족하지 않을 때마다 오른쪽으로 한 칸 이동하는 구조이다. 그리고 현재 상태가 Yes! 또는 Yes?일 때 현재 조건 분기 명령어가 조건을 만족할 것이라고 예측하는 것이다. 이렇게 하면 반복문과 같은 구조에서 대부분의 경우에 예측에 성공할 수 있기 때문에 정적 예측 방식보다 전반적으로 클락 사이클을 덜 낭비할 수 있게 된다.