4. Control Hazard (Branch Hazard)

Branch Hazard

Conditional jump(beq, bne)에서 branch의 여부는 4번째 cycle(MEM stage)에서 판단이 완료된다.

따라서 3 cycle 동안 nop을 수행해야 한다.

 

성능

Conditional jump instruction은 약 15% 확률로 나타나기 때문에 CPI는 1.45 (= 1 + 0.15*3)가 된다.

이는 성능에 있어서 큰 감소를 일으킨다.

 

 

해결

beq/bne를 ID stage에서 끝냄으로써 손실을 최대한 줄일 필요가 있다.

ID stage에서 끝낸다면 1cycle로 줄일 수 있다.

 

이를 위해서 ID stage에서 adder와 comparator가 필요하다.

• adder
  • ID stage에서 target address를 계산한다.
• comparator
  • 두 개의 register의 값이 같은지 계산한다.
  • 단순히 equality check를 하기 위해서 빼기를 수행하는 것이 아니라 bit by bit comparison을 수행한다.

 

ID stage에서 bne/beq를 수행함으로써 nop이 하나만 들어가면 된다.

따라서 CPI는 1.15가 된다.

이를 위해 다음의 decode stage로 fetch된 instruction이 들어가는 것이 아니라 IF.Flush를 통해 nop이 들어가도록 한다.

 

 

blt를 제공하지 않고 slt와 beq로 수행하는 이유?

blt를 제공한다면 branch hazard를 없애기 위해서 ID stage에 subtraction unit이 추가되어야 한다.

 

그런데 단순한 equality check는 bit by bit comparison을 통해서 빠르게 수행이 가능하다.

그러나 subtraction은 carry/borrow 등으로 인해 bit가 순차적으로 계산되어야 하기 때문에 속도가 느리다.

 

때문에 blt를 구현하려면 ID stage의 cct가 증가해야 하고 이는 결국 전체 cct의 증가를 야기한다.

따라서 blt를 제공하지 않고 slt와 beq로 나눠서 수행하는 것은 pipeline을 고려한 ISA 설계인 것이다.

 

Side Effect

branch 연산이 ID stage에서 완료되도록 하면 branch hazard에 대한 손실은 줄일 수 있다.

그러나 data hazard와 forwarding은 늘어난다.

 

Control hazard를 줄이는 이득이 더 크게 때문에 data hazard와 forwarding이 늘어남에도 control hazard를 줄인다.

 

원래 연산 수행은 EX stage에서 일어나기 때문에 ID stage에서는 forwarding 받을 필요가 없었다.

그러나 comparison을 위해서 ID stage에서 앞의 instruction에서 변경된 register의 값이 필요하기 때문에 data hazard가 발생한다.

이를 해결하기 위해 바로 앞의 instruction과 2번째 앞의 instruction으로부터 forwarding을 받아야 한다.

 

또한 ALU instruction 바로 뒤에 beq/bne가 나올 수 없다.

한 cycle이 지나야 변경된 값을 쓸 수 있기 때문이다.

 

lw 바로 뒤에 beq/bne이 나올 경우 2개의 nop가 들어가야 한다.

lw의 결과는 MEM이 지나야 나오기 때문이다.

 

---

Branch Prediction

branch가 나오면 한 cycle의 nop가 수행되어야 하기 때문에 바로 뒤에 instruction 수행이 불가능하다.

그러나 실제로는 control branch가 나오면 jump 할지 말지를 예측함으로써 한 cycle의 낭비를 최대한 줄인다.

예측이 맞으면 이득인 것이고 틀리면 그 때 nop를 추가하면 되기 때문이다.

 

• Predict untaken
  • conditional branch가 나오면 항상 jump가 일어나지 않는다고 가정
  • 그 다음 instruction을 무조건 fetch한다.
• Predict taken
  • conditional branch가 나오면 항상 jump를 한다고 가정한다.
  • jump할 곳의 instruction을 fetch 한다.

 

MIPS에서는 다음 instruction을 fetch할 단계에서는 아직 이전의 instruction이 branch인지도 모른다.

따라서 실제 jump 할 곳의 instruction을 fetch 할 수 없으므로 predict taken을 사용하지 않는다.

 

Predict untaken의 정확성은 약 40% 이다.

branch instruction이 나왔을 때 실제 jump하지 않을 확률이 40%라는 것이다.

 

따라서 predict untaken을 한다면 CPI는 1 + 0.15 * 0.6 *1 = 1.09가 된다.

Branch가 나올 확률은 0.15, 실제 jump할 확률(predict가 틀릴 확률)이 0.6, 그 때 손실되는 cycle이 1개이기 때문이다.

만약 predict를 하지 않는다면 CPI = 1.15이다.

 

Deep Pipeline (Longer Pipeline)

Branch prediction은 deep pipeline에서 특히 중요하다.

Deep pipeline이란 stage의 개수가 많은 pipeline을 의미한다.

 

Stage가 많을 수록 predict untaken으로 성능을 낼 수 없고, 미리 jump 여부를 알 수 없기 때문에 branch hazard로 인한 손실이 매우 크다.

따라서 dynamic branch prediction을 주로 사용한다.

 

Realistic Branch Prediction

• Static branch prediction
  • 프로그램 실행 전에 branch predict를 한다.
  • predict backward branches taken
    • 뒤(backward)로 jump하는 경우는 loop이 있다.
    • loop으로 인해 발생하는 branch은 예측 한다.
  • predict forward branches not taken
    • if 등으로 인해 forward branch 하는 것은 예측하지 않는다.
• dynamic branch prediction
  • runtime(프로그램 실행 중)에 branch predict를 한다.
  • 하드웨어가 실제 branch behavior를 측정하고, 미래의 behavior는 지금까지의 행동에 근거하여 예측한다.
    • branch instruction이 나오는 주소 값(PC), 실제 jump를 수행했는지 여부를 branch prediction buffer(branch history table)에 저장한다.
    • jump했다면 어느 곳으로 jump 했는지를 branch target buffer에 저장한다.
    • 과거에 jump 했으면 같은 곳으로 jump 한다고 예측하고, 과거에 jump 하지 않았다면 이번에도 jump 하지 않는다고 예측한다.
    • 만약 예측이 틀리다면 그때 다시 refetch하고, table을 update 한다.