[컴퓨터구조#2-2] 파이프라인(Pipelining) - Pipeline Hazards, Branch Prediction

참고: Computer Architecture: A Quantitative Approach (5th edition) - Appendix C. Pieplining: Basic and Intermediate Concepts

지난 글에 이어, 이번 글에서는 파이프라인을 적용할 때 신경 써야 할 문제인 Pipeline Hazards와 Branch Prediction에 대해 다룰 것이다.

2024.04.11 - [Computer Architecture] - [컴퓨터구조#4] 파이프라인(Pipelining) (1/2) - 기초

목차

1. Basic Pipelining

2. Pipeline Hazards

- Structural Hazard

- Data Hazard

- Control Hazard

3. Branch Prediction

- Static / Dynamic

- Branch Target Buffer (BTB)

---

2. Pipeline Hazards

Piepline Hazards에는 크게 세 종류가 있다. 여러 명령어들이 같은 clock cycle에 같은 structure를 사용하려고 하는 경우(structure는 한 번에 하나의 접근만 허용) 발생하는 Structural Hazard, younger 명령어가 파이프라인 내의 older 명령어의 결과를 사용하려고 하는 경우 발생하는 Data Hazard, 브랜치 대상이 정해지는 IF와 EX 간 지연 시간으로 인해 발생하는 Control Hazard가 그것이다. 이런 hazard에 대한 일반적인 해결 방법은 pipeline stall, 즉 파이프라인을 멈추는 것이다. 해당 hazard가 해결될 때까지 최근 명령어들을 잠시 멈추고, 해결되면 다시 파이프라인을 개시하는 것이다. 하지만 이 경우 성능 loss가 발생한다.

Structural Hazard

예시를 통해 살펴보자. 다음 그림에서, clock cycle 4일 때 load와 Instr.3(IF 단계) 모두 Mem을 사용해야 한다. 

이런 경우, 단순히 파이프라인을 1 사이클 stall해줌으로써 메모리 접근 충돌을 회피할 수 있다. (*in-order processor) 다음 표의 CC4에서 i+3번째 명령어가 stall된 것을 확인할 수 있다. (stall하지 않는 해결 방법으로는, Mem port를 하나 더 추가할 수도 있다.)

 

Data Hazard

세 종류의 데이터 hazard가 있다.

RAW (Read after Write)	true dependence
WAR (Write after Read)	false dependence
WAW (Write after Write)	false dependence (output dependence)

다음과 같은 순서대로 명령어가 실행된다고 해 보자. (각 피연산자는 첫 번째가 destination, 뒤의 두 개가 source이다.)

Add R1, R2, R3
Sub R4, R1, R3
And R3, R5, R6
Xor R3, R7, R8

1. Add의 destination인 R1을 Sub의 source로 사용하므로 Add와 Sub 간 RAW
2. Sub의 source인 R3을 And의 destination으로 사용하므로 Sub와 And 간 WAR
3.  And의 destination인 R3을 Xor의 destination으로 사용하므로 And와 Xor간 WAW

이때, WAR과 WAW는 false dependence이긴 하지만 어디까지나 in-order 프로세서일 때 한정으로 괜찮고, out-of-order pipeline 프로세서의 경우 true dependence가 될 수 있기 때문에 주의가 필요하다.

이러한 Data Hazard는 Bypassing(forwarding)을 통해 해결할 수 있다. 파이프라인 내 younger 명령어들이 아직 레지스터에 저장되기 전 데이터를 필요로 하는 경우, 다음과 같이 pipeline에 datapath를 추가하여 아직 저장되기 전의 값들을 bypassing을 통해 필요한 명령어들에 전달해줄 수 있다.

혹은, 위 structural hazard에서와 같이 pipeline stall을 통해 해결할 수도 있다. 두 방법의 장단을 비교해보자. (Recap: Exec_time = #Instr * CPI * clock_cycle)

Data Hazard solutions	stall (w/o bypassing)	Bypassing
특징	bubble cycle	extra logic
CPI	>1 (CPI 1에 가까울수록 이상적)	stall에서보다 작지만, clock cycle이 증가

또한, 경우에 따라서는 bypassing만으로는 해결할 수 없고 bypassing과 stall 모두 사용해야 해결할 수 있을 때도 있다.

Case 1

Lw R1, 0 (R4)
Sw R1, 0 (R6)

Lw의 destination을 Sw의 source로 사용하는 RAW dependency가 존재하는 상황이다. Lw에서 R1에 들어갈 값은 MEM 단계에서 계산되어 생성되고, Sw에서 source로 사용하는 R1 값도 역시 MEM 단계에서 메모리를 통해 접근되어 얻어진다. 따라서, MEM과 WB 사이에 bypassing 경로를 추가하여 dependency를 해결할 수 있다.

Case 2 

Lw R1, 0 (R4)
Add R4, R1, R2

Lw의 destination을 역시 Add의 source로 사용하는 RAW dependency 예시이다. 다만, 위와 다른 점은 Add에서 source가 필요한 시점은 EX단계(ALU 연산)이라는 것이다. 하지만, 바로 인접한 명령어들의 경우 파이프라인 stage도 하나밖에 차이가 나지 않기 때문에 Lw의 MEM과 Add의 EX는 같은 사이클에 시작하게 된다. 즉 Lw의 MEM 직후에 R1에 들어갈 값을 얻을 수 있는데, 이 시점에 이미 Add의 EX가 끝나야 하기 때문에 bypassing만으로 해결할 수 없다. 따라서 이 예시에서는 최소 한 사이클의 stall (pipeline bubble)이 필요하다.

 

Control Hazard

브랜치 명령어의 경우, 브랜치 조건이 참인지 거짓인지 판단하는 EX 단계 전까지는 결과를 알 수 없다. 하지만 바로 다음 사이클에서 명령어를 fetch해야 하므로, PC+4로 할지 혹은 브랜치에 명시된 주소로 해야 할지 알 수 없다. 브랜치 조건 결과를 알 때까지 파이프라인을 stall할 수도 있고, 브랜치 결과를 예측할 수도 있다.(만약 예측이 틀리면 flush 후 recovery하면 된다.) → Speculation

 

3. Branch Prediction

즉, branch prediction은 실제 브랜치 조건 결과가 나오기까지 기다리지 않고 브랜치 결과를 예측함으로써 control hazard를 해결하기 위한 방법이다.

 

Static Branch Prediction

taken 혹은 not taken 중 하나로만 정적으로 예측하는 방법이다.

항상 not taken으로만 예측한다고 해보자. 계속해서 명령어를 PC+4로 순차적으로만 fetch해오고, 만약 branch 결과가 taken인 경우 잘못 fetch한 명령어들을 flush 후 branch destination에서부터 파이프라인을 재시작한다.

 

Dynamic Branch Prediction

history 기반으로 브랜치 결과를 동적으로 예측하는 방법이다.

가장 간단한 형태는 branch prediction buffer(혹은 BHT, branch history table)에 브랜치가 taken이었는지 not taken이었는지 저장하여 그 결과를 기반으로 판단하는 것이다.

• BHT는 PC의 lower bit로 address되고, IF/ID 파이프라인 레지스터를 통해 ID로 전달된 bit를 저장한다.
• BHT를 통해 예측한 결과가 틀릴 수도 있다. 하지만, 이는 correctness에는 영향을 주지 않고 단지 성능(performance)에만 영향을 미친다. 
• 만약 예측이 틀린 경우, static에서와 마찬가지로 flush 후 재시작한다.

Branch prediction buffer는 가장 간단하게는 위와 같이 1-bit로 구현된다. 하지만 만약 어떤 브랜치가 거의 대부분 taken이었어도, not taken인 경우 두 번의 misprediction이 일어날 수 있다(misprediction은 prediction bit를 flip하기 때문).

이런 약점을 보완하기 위해, 2-bit 예측 scheme도 많이 사용된다. 다음과 같은 2-bit scheme은 prediction bit를 바꾸려면 두 번의 misprediction이 전제되어야 하므로 90%의 정확도를 낼 수 있다.(←근거는 잘 모르겠음)

2-bit branch predictor

 

Branch Target Buffer (BTB)

BHT는 언제 브랜치가 taken인지는 예측하지만, 어디로 taken되는지는 알려주지 않는다.

IF 단계의 BTB는 브랜치 타겟 주소를 캐싱하지만, 우리는 그 다음 순차 명령어도 fetch해야 한다. IF/ID의 예측 비트는 다음번 clock edge에 어떤 다음 명령어가 올지 선택한다. 만약 현재 PC가 entry에 존재한다면, 다음 사이클에는 PC+4가 아닌 BTB의 해당 PC와 같이 저장된 predicetd PC에서 fetch해온다.

혹은, instruction 메모리가 다음 sequential 명령어를 fetching하는 동안 BTB는 branch taken 명령어를 캐싱할 수 있다.