RISC-V 컴퓨터구조 - 4. The Processor - 4.8. Control Hazards

만약 beq x1, x2, L1 다음에 add x1, x2, x3라는 instruction이 온다고 하자. 만약 x1과 x2가 같지 않다면 이 add instruction이 시행되겠지만, 같다면 L1위치에 있는 instruction으로 넘어갈 것이다. 따라서 다음 instruction인 add를 할지 말지 결정해야 하는데, 이는 memory stage가 되어서야 알 수 있으므로, 3 clock cycle의 stall이 필요한데, 모든 상황에서 이렇게 하면 너무 비효율적이다. 

따라서 가정을 한다.

Assume Branch Not Taken

Branch가 무조건 Not Taken 된다고 가정한다음 다음 instruction을 그냥 진행시킨다. 그러다가 만약 branch가 take되어 버리면, 지금까지 한 것들을 다 discard해야 한다. Load use stall이 발생한 경우에는 그냥 ID/EX의 control signal을 0으로 놓고 앞으로 propagation을 시켰는데, 이 경우에는 그렇게 할 수 없으므로 IF, ID, EX에 있는 모든 instruction을 flush해야 한다. (Flush: To discard instructions in a pipeline, usually due to an unexpected event)

Reducing the Delay of Branches

한 가지 방법은 PC의 주소를 Mem 단계에서 계산하지 말고, 그 앞의 단계에서 계산하는 것이다. 이렇게 하려면 두 과정을 빨리 해야 하는데, 한 과정은 branch target address를 계산하는 과정이고, 나머지는 branch decision을 하는 과정이다. 

사실 IF/ID에서 PC value와 immediate field를 알고 있으므로 branch adder를 EX가 아니라 ID 단계에서 계산할 수 있고, 사실은 branch decision도 이 과정에서 할 수 있다. 두 개의 값을 xor하고 각각의 bit를 or해서 0이 나오면 같은 것으로 결론을 내릴 수 있다. 하지만, 이 과정에서 전 instruction에서 수정된 값이 사용된다면 forwarding을 해야 한다. 

이렇게 해도 문제점이 또 있는데, 바로 앞의 instruction이 ALU instruction일 경우, 앞의 EX단계가 끝난 후에야 값이 나오기 때문에 branch instruction의 ID 단계에서 이를 알 수가 없다. 따라서 한 단계가 stall되어야 한다. 만약 바로 앞의 instruction이 ld인 경우라면..?  두 단계의 stall이 필요할 것이다. 

생각보다 굉장히 복잡한 과정이라는 것을 알 수 있다. 하지만 이러한 어려움에도 불구하고, MEM 단계에서 ID 단계로 이를 끌어오는 것은 improvement이다. 3 cycle을 낭비할 것을 1 cycle 만 낭비할 수 있게 하기 때문이다. 

이렇게 했을 때 만약 예상을 잘못한 경우 IF의 instruction을 flush해야 하는데, flush 하는 방법은 IF.Flush라는 control line을 추가하는 것이다. 이렇게 되면 IF/ID pipeline register의 instruction값이 0으로 초기화된다. Register을 Clear하면 nop 상태로 바뀌어서, state가 바뀌지 않는다.

Dynamic Branch Prediction

하드웨어를 조금 더 추가해서 branch의 결과를 예측할 수 있다. 한 가지 방법은 예전에 taken이 되었다면 taken되게 하고, taken이 안되었다면 taken을 하지 않는 것이다. 이를 구현하려면 branch prediction buffer나 branch history table을 만들어야 한다. Branch prediction buffer는 branch instruction의 lower portion으로 indexing이 되고, 이 branch가 최근에 taken됐는지 여부를 나타내는 bit을 포함한다. 하지만, 이 경우에는 오히려 true로 예측하는 rate가 떨어지는 경우가 발생한다. 따라서, 2-bit prediction을 생각해 볼 수 있다.이 경우 successive하게 두 번의 wrong prediction이 발생할 경우 그 다음 instruction을 바꾼다. Finite State Machine을 나타내면 다음과 같다.

 

Correlating Predictor

이 경우에는 local bracnch의 정보를 이용함과 동시에(2 bit predictor) global 한 정보도 이용한다. 이전 branch가 taken됐는지 안됐는지에 따라서 predictor중 하나를 선택한다.

Tournament branch predictor

각각의 branch에 대해서 multiple prediction을 한 후에, selection mechanism으로 어떤 predictor를 enable할지 결정한다.

긴긴 여정을 달려왔는데, 최종적인 pipeline 그림은 다음과 같다.

출처 : Patterson, David A., and John L. Henessy. Computer Architecture and design the hardware/software interface. Cambridge, MA: Morgan Kaufman Publishers, 2018. Print.