[CA] Lecture #22

Control Hazard

Control Hazard

: beq에서 branch 여부는 원칙적으로 EX 단계가 끝나고, MEM 단계에서 알 수 있다.

--> beq instruction 다음에 어떤 연산을 수행해야 할 지, 따라서 어떤 PC 값을 설정해야 할 지( PC+4 또는 PC+offset)를 알기 위해서는 3 STALL이 발생한다.

 

Example: branch taken

▶ beq: PC-relative branch

• MIPS: PC = (PC+4) + (immediate * 4)

 

Reducing Branch Delay: Register Compactor

Reducing Branch Delay: Register Compactor

▶ Register Compactor

: ID 단계의 Register file에서 beq에서 비교 연산에 사용되는 레지스터 값을 읽고, 그 결과를 IF 단계의 MUX에 전달하여, (PC + 4) 또는 (PC + offset) 중 어떤 PC 값을 선택할 지를 미리 결정할 수 있도록 한다.

 

▷ Branch instruction의 STALL:

• 그냥 파이프라인 순서대로 --> 3 STALL
• Forwarding --> 2 STALL
• Register compactor --> 1 STALL

 

Example: Branch Taken

: 일단, branch가 일어나지 않는다고 가정한다. (branch not taken)

--> 그 다음 instruction을 실행한다.

 

: 만약 beq가 ID 단계에 진입하여, beq 연산이 있음을 확인하고 나면, Bubble이 하나 발생한다.

--> Branch instruction이 있으면, 1 STALL 이후 그 다음 instruction을 수행한다.

• Register compactor를 통해 ID 단계에서 미리 branch instruction의 유무를 판단할 수 있다고 하더라도, 1 STALL은 불가피하다.

 

---

Data Hazard for Branches

Data Hazard for Branches

▶ Forwarding

• MEM --> EX
• WB --> EX

▶ EX, MEM의 결과를 ID 단계로 가져오는 것

: ID 단계에서 beq instruction이 있음을 확인하고, branch 여부를 결정하기 위해서는 앞에서 MEM 단계와 EX 단계에서 연산된 레지스터 결과가 필요하기 때문이다.

 

: beq가 있으면, 무조건 1 STALL은 발생한다.

 

: 만약 앞에 lw까지 있으면, 1 STALL이 더 추가돼서, 2 STALL이 된다.

 

 

Dynamic Branch Prediction: Branch Predictor

• Problem: Register compactor를 통해 ID 단계에서 branch instruction의 존재 여부를 판단한다고 하더라도, 1 STALL은 불가피하다. 거기에 lw 연산이 beq 연산에 영향을 준다면, 1 STALL이 추가되어 2 STALL이 된다.

--> Solution: Dynamic branch prediction - Branch predictor

: Branch predictor를 이용하여, 무조건 branch not taken으로 예측하는 것이 아니라, 상황에 따라 예측의 결과를 바꾼다.

 

1-BIT Predictor: Shortcoming

1-BIT Predictor: Shortcoming

1. Outer loop: i=0 --> branch taken (1번 맞게 예측)
2. Inner loop: j=0~4 --> branch taken (5번 맞게 예측)
   Inner loop: j=5 --> branch not taken (1번 틀리게 예측) --> 상태가 Predict Not Taken으로 바뀐다.
3. Outer loop: i=1 --> branch taken (1번 틀리게 예측) --> 상태가 Predict Taken으로 바뀐다.
4. Inner loop: j=0~4 --> branch taken (5번 맞게 예측)
   Inner loop: j=5 --> branch not taken (1번 틀리게 예측) --> 상태가 Predict Not Taken으로 바뀐다.

... 반복됨!

▷ 결론:

• Outer loop: i=0에서만 맞게 예측하고, 나머지(i=1~5)는 항상 틀리게 예측한다.
• Inner loop: j=0~4는 항상 맞게 예측하고, j=5는 항상 틀리게 예측한다.

--> Correct Prediction: 1(outer loop) + 5*6(inner loop) = 31

--> Mis Prediction: 5(outer loop) + 1*6(inner loop) = 11

 

Cf) 만약 branch predictor를 inner loop와 outer loop가 각각 따로 가진다면, correct prediction rate가 높아진다. 

 

2-BIT Predictor

2-BIT Predictor

1. Outer loop: i=0에서 branch taken으로 맞게 예측한다.
2. Inner loop: j=0~4에서 branch taken으로 맞게 예측한다.
   Inner loop: j=5에서 branch not taken으로 틀리게 예측한다. 하지만 이때, 상태는 아직 (weak) Predict Taken에 머무른다.
3. Outer loop: i=1에서 branch taken으로 맞게 예측한다.

... 반복됨!

▷ 결론: 상태가 두 번의 예측에만 변화하기 때문에, mis prediction이 (j==5)에서 한 번만 일어난다.

• 상태는 (strong) Predict Taken과 (waek) Predict Taken 사이만을 이동하여, 항상 Predict Taken에 머무르게 된다.

 

 

Calculating the Branch Target

▶ Target Buffer

: Cache of target addresses. --> Branch prediction에 이용한다.

 

 

 

 

 

출처: 이화여자대학교 윤명국교수님 컴퓨터구조