[Study] Dynamic Branch Prediction

이전 포스트 들 중에서 Pipeline에 대해서 다뤘던 적이 있다.

Pipeline 자체가 그 Never Waste Time이라는 말처럼 각 stage가 노는 여유가 없이 계속 돌리게 함으로써, 전체적으로 instruction의 처리 시간을 줄이는 효과를 가져온다고 언급했었다. 하지만 분명 pipeline을 수행하다 보니 stage간의 순서를 반드시 지켜줘야 하는 경우가 있으며, 이를 지키지 않았을 경우에는 원하는 답을 얻지 못하는 경우가 발생하기도 한다. 그런데 발생할 수 있는 hazard 중에 control hazard 라는 것을 다뤘었고, 이 문제 자체는 branch와 jmp 같은 memory 주소를 뛰어 넘는 instruction 수행시 자주 발생한다. 분명 pipeline의 효과를 수행하기 위해서는 instruction이 원래의 타이밍보다 일찍 수행되어야 하는데 branch 자체는 주소를 해당 instruction이 지정하는 곳으로 넘어가기 때문에 상황에 따라서는 일찍 수행하는 것이 의미가 없을 수도 있는 것이다.

 그럼 이걸 해결하려면 어떻게 해야 될까.. 가장 쉬운 방법은 그 글에서도 언급했었지만 stall을 시켜버리는 것이다. 어차피 수행해봤자 정확한 결과를 얻기 힘들기 때문에 그냥 그 stage에서는 멈추게끔 하고 다시 해당 instruction을 수행할 때까지 기다리는 형태가 된다. 그런데 딱보면 알다시피 stall을 하는 것 자체는 기존의 instruction을 미리 수행함으로써 전체 수행시간을 줄이고자 했던 pipeline의 원래 목적에서 조금 벗어나게 된다. 분명 그 목적을 유지하기 위해서는 branch를 하는 순간에도 다른데서는 뭔가를 수행해놓고 있어야 할 듯하다. 

 그래서 생각한 방법이 예측(Predict)을 하자는 것이다. 그래서 사전에 결과를 예측해놓고, 그 결과가 맞으면 당연히 instruction 수행이 빨라지고, 다르면 그만큼 mispredict에 대한 penalty를 가지게 하면 그래도 기존의 stall을 주는 방식보다는 효율적으로 처리할 수 있을 것이다. 이게 바로 Branch Prediction이다. 그래서 지난 포스트에서 소개한 방법이 아닐때를 가정하고 예측하는 방식인 Predict-Not-Taken 방식과 맞을 때를 가정하고 예측하는 Predict-Taken 방식을 소개했었다. 

 그런데 사실 이 예측에도 한계가 존재한다. pipeline의 특성상 multi stage로 구성되어 있어서 여러 instruction을 동시에 실행시키게끔 되어 있다.(Multiple Instruction Launch) 만약 예측이 잘 못되었다면 그 이후에는 어떻게 처리를 해야 될까? 물론 앞에서 예측이 잘못되었을 때에 대한 mispredict Penalty를 가지면 된다고 언급했었지만 해당 stage가 커지게 되면 이런 penalty로 인한 손실도 무시못할만큼 커질 것이다. 여기서 고민하고 있는 것은 stage를 늘리면서도 어떻게 하면 penalty로 인한 손실을 줄일 수 있느냐는 것이다. 지금 발생하는 mispredict를 빠르게 판단하고 그에 맞는 대처 방안을 줄 수 있으면 그만큼 penalty를 줄일 수 있지 않는가 하는 접근 방식이 있는 것이고, 이로 인해서 나온 방식이 Dynamic Branch Prediction이다.기존의 Branch Prediction 수행방식은 앞에서 말한 Predict-Not-Taken이나 Predict-Taken을 그대로 수행하되, 만약 mispredict가 일어나면 해당 instruction을 flush 시키고 다시 retry하는 구조로 되어 있다. 이게 Static Branch Prediction인데 이른바 instruction의 type에 의해서 구조가 정해진 형태인 것이다. 만약 Prediction의 결과물이 20개의 instruction으로 이뤄져 있는데 마지막에 Prediction이 잘못되었다는게 판별되면 그 20개의 instruction이 모두 waste되는 비효율적인 결과를 낳는 것이다. 그래서 runtime 내에 mispredict가 일어나면 유동적으로 수행 절차를 바꿀 수 있는 방식이 Dynamic Prediction 방식인 것이다. 그래서 보통 이걸 수행하기 위해서는 Branch Prediction Buffer가  구조내에 포함된다. 다음이 Prediction Buffer의 예이다.

위의 예시는 1bit의 runtime information을 활용한 prediction scheme이다. 이렇게 하면 현재의 Prediction의 여부에 따라서 그에 맞는 scheme를 수행하게 된다. 그런데 사실 이 방법도 한계가 있다. 

가령 Doubly nested loop를 들어보면 위와 같은 구조는 branch instruction에서 miss가 날때마다 prediction state가 변경된다. 그런데 전체적으로 루프가 한개가 다른 한개를 포괄하고 있는 상태에서 전체 state를 predict가 확실하다고 보장하지 못하는 것이다. 다시 말해 안쪽 loop가 수행되면서 branch가 taken이 되더라도 마지막 반복구문에서는 그 branch에 대한 prediction이 일어나지 않으므로 그 상태가 not taken으로 변경된다. 그런데 이 상태에서 안쪽 loop를 다시 수행하면 처음 branch predict를 수행하면 다시 수행하기 위해 state가 taken으로 변경되면서 결론적으로 안쪽 루프의 처음 state와 나중 state가 맞지 않는 현상이 발생하는 것이다.

2bit에서는 branch prediction이 두번 연속으로 틀릴 경우에만 state가 변경되기 때문에 위의 케이스 경우에는 안쪽 루프의 마지막 instruction이 mispredict 되더라도 state가 taken을 유지하게 된다. 물론 그 상태에서 다시 안쪽 루프를 수행하더라도 전체적으로 prediction state가 맞게 되는 것이다.

계속 나와있다시피 이 방법 자체는 Branch Prediction에 대한 문제를 hardware적으로 해결하기 위한 방법이고, 그냥 간단하게 buffer를 다는 걸로 보면 좋을 것 같다. 

이와는 다른 Branch Prediction이 바로 delayed Branch를 넣는 것이다. 말그대로 branch 명령어가 있는 경우에는 그 다음 instruction 에 대한 수행이 불확실하기 때문에 컴파일러나 어셈블러 자체적으로  아무것나 실행시키게끔 하는 아이디어이다. 이를 다른 말로 Branch delayed slot이라고 한다. 보통 이렇게 삽입되는 instruction 은 nop가 들어간다. 다음 예시가 delayed branch를 나타낸 예이다.

만약 $4와 $0 이 같다면 당연히 다음 instruction인 and는 수행할 필요가 없다. 하지만 pipeline 구조인 이상 아무 필요가 없어도 미리 수행해놓는 것이다. 이럴때는 compiler 자체가 여기에 nop이 배치되게끔 재구성되는 것이다. 

 아무튼 이정도...