Out-of-Order Issue, Out-of-Order Completion

저번에 In-order Issue, Out-of-Order Completion에 대해 알아보았는데요. 이번에는 Out-of-Order Issue, Out-of-Order Completion에 대해 알아보겠습니다.

순서대로 Issue를 하지 말고, Hazard관계가 없는 Instruction부터 Issue하면 빠르지 않을까요? 해서 나온 방법이 Out-of-Order Issue입니다.

먼저 Instruction이 In-order로 들어오면, Dispatch를 하고 그 다음 Issue를 진행합니다. Issue는 Out-of-Order로 진행되며, Instruction finish도 Out-of-Order로 됩니다.

여기서 Dispatch란 Issue buffer에 공간이 있다면 다음 instruction을 시작합니다.

예시를 들어 설명할 것인데, 그 전에 WAR Hazard가 없다고 가정해보겠습니다. WAW와 WAR hazard는 register renaming이라는 것을 통해 해결할 예정입니다.

또한, FU가 busy이면 instrctuion이 dispatch를 하지 않는 다는 조건과 한 cycle에 3 instruction이 dispatch될 수 있다는 가정을 해봅시다.

Issue stage buffer은 여러 instruction이 issue될 때 까지 instruction을 hold합니다.  Issue scheduler가 있는데, RAW hazard가 해결됐는지 확인하는 역할을 하며, 해결됐으면 instruction이 issue되게 합니다. 만일 dispatch unit이 structural hazard를 check하지 않았다면, issue scheduler는 FU availability를 책임을 가지게 됩니다.

위 그림이 예시입니다. Timeline을 그려 Issue를 Out-of-Order로 할 수 있게 되죠.

I1이 cycle 1일 때, dispatch가 됩니다. 이 때 LOAD관련된 FU가 busy되어 L2를 이어서 Dispatch하지 못하게 됩니다. Dispatch는 In-order로 되는 점 기억해주세요!

I1이 Write Back되면, I2와 I3, I4 3개를 동시에 Dispatch합니다. I2와 I3는 Issue Scheduler에서 RAW Hazard를 인식해 Issue가 동시에 실행되지 못합니다. 하지만 I2와 I4는 서로 관련이 없으므로 동시에 Issue될 수 있죠. I2가 Write Back되면 I3가 Issue되며, WAW가 해결된 I5가 Dispatch되기 시작합니다. I5와 I6는 RAW가 있어 I6의 Issue는 좀 더 뒤에 있게 되네요.

여기서 I5과 I6는 제일 뒤에 Dispatch되었던 이유가 I2에서 사용했던 r2라는 register가 그대로 I5, I6에서도 사용되었기 때문이죠. 사실 r2를 I5에서 쓰지 않아도 상관없습니다. 이에 r2를 사용하지 않고 다른 register를 사용하여 Dispatch를 보다 앞당길 수 있게 되죠. 이러면 더 빨리 Instruction을 마무리할 수 있게 됩니다.

Out-of-Order Scoreboarding을 통하여 위 Instruction 5개를 실행하는 과정을 순차적으로 알아보겠습니다.

먼저 FU Status를 적을 수 있는 table과 Scoreboard를 준비합니다. cycle 1일 때, I1만 Dispatch되는데, I1만 Dispatch되는 이유는, FU가 Busy여서 I2가 Dipatch되지 못하기 때문이죠.

FU State에 Busy는 1, Op는 Load, Dest는 r6, Src1에는 r2를 적어줍니다. SB는 dest인 r6에다가 1로 기입합니다.

I1가 WB되면, I2와 I3, I4가 동시에 Dispatch됩니다. Dispatch는 한번에 최대 3개까지 가능하다고 가정하였기 때문에 I5가 Dispatch되지 않습니다. FU status와 SB를 위와 같이 update해줍니다.

I2와 I4는 Issue가 바로 될 수 있습니다. 하지만 I3는 Issue가 바로 되지 않죠. r2의 RAW hazard로 인해 바로 Issue하지 못하는 겁니다. I5는 I2와 I4가 Issue가 되었기 때문에 이제 Dispatch할 수 있습니다. 하지만 I6는 FSUB로 인해 busy여서 Dispatch가 되지 못하죠.

마찬가지로 I5도 바로 Issue되지 못하는데, source register인 r8가 I4에서 destination register이기 때문에 바로 Issue되지 못하죠.

FSUB가 Write Back되면, FU status는 not busy가 되기 때문에 그제야 I6가 Dispatch될 수 있습니다.

Scoreboard에 r8이 0이되면, I5가 Issue될 수 있습니다.

이런 식으로 FU status와 SB를 통해 Out-of-Order Issue와 Completion을 할 수 있죠.

---

Out-of-Order Issue와 Completion에 대해 알아보았습니다. Scoreboard를 사용하면 Out-of-Order를 정확히 사용할 수 있네요!