Instruction-Level Parallelism : Hardware Based Speculation for Out-of-Order Execution

* 이글의 내용 및 그림들의 많은 부분을 아래 자료들로 부터 참고해 왔습니다.

- Computer Architecture: A Quantitative Approach   ( 6th edition )

- Prof. Dr. Ben H. Juurlink youtube ( https://www.youtube.com/@prof.dr.benh.juurlink5459/videos )

 

 

 

* 이글은 프로세서의 Out-of-Order Execution 에 대한 심화내용이니, 해당 내용을 모른다면 이전글 Instruction-Level Parallelism : Out-Of-Order Execution( https://zbvs.tistory.com/36 )을 참고하세요.

Key Ideas for H/W Based Out-of-Order Speculative Execution

H/W Based Speculative Execution의 Key Idea는 다음과 같다.

- instruction들을 out-of-order로 실행하게 허용 하되, commit은 in-order로 한다. 

- 이때 commit이 되기 전까지는, recover 불가능한 action들은 모두 금지시킨다.

 

Reorder Buffer ( ROB )

Reorder Buffer

- instruction들이 “정말로 실행되었어야 함"알기 전 까지(즉 commit하기 전 까지) 대기하는 Buffer이다. 

* commit을 complete 혹은 graduate라고 표현하기도한다.

- instruction들인 ROB에 대기하면서 실행은 하지만, 프로세서의 상태( Register , Memory 등등)을 바꾸지는 않는다.

- 이때 instruction이 commit이 되면, 비로소 ROB에서 제거 되면서 Register, Memory 등등의 상태를 바꾸게 된다.

- commit이 될 때 exception을 발생시켜 precise exception 을 가능하게 한다.

 

Reorder Buffer의 구조와 ROB entry number

reorder buffer는 circular buffer 형태이며, Buffer의 각 Entry는 type, destination, ready, value 4개의 필드로 이루어져 있다.

- type : instruction의 타입을 나타내는데, 타입은 3가지 타입만 구분하면 된다. 즉  branch , store,  load & register operation  이 3가지를 구분하는 값이면 충분하다. register operation 이란, 출력 대상이 register인 ADD, MUL, MUL.D 등등과 같은 operation들이다.

- destination : instruction의 출력 대상이다. 예를들면 F0, F1 와 같은 특정 레지스터 이름이나 특정 메모리의 주소이다.

- ready : 이 Entry가 나타내는 instruction의 실행이 끝났음을 나타내는 flag이다.

- value : 실행한 이후의 출력값이다. 명령어가 실행했을 때 destination에 저장 되었어야 할 값이다. 오직 ready flag가 1일 때만 존재한다.

 

모든 instruction은 issue가 될 때 issue가 될 때 RS에 insert 되는 동시에 ROB에도 insert되며, ROB의 insert 순서대로  ROB entry number를 부여받는다. 즉 정확히 issue된 in-order 순서대로 ROB entry number 가 부여된다. ROB entry는 ROB entry number 순서로 commit 되므로, 결론적으로 instruction 들은 ROB에서 issue가 된 in-order 순서로 commit 된다. 가장 중요한 사실은 ROB entry number는 이제 RS identifer의 역할을 대신한다는 사실이다.

 

ROB에는 아래 그림처럼 tail과 head라는 buffer에서의 offset field가 존재한다.

- head : issue된지 가장 오래된 instruction ( 다음에 commit되어야 할 instruction)을 가리키며, 해당 entry를 oldest entry라 부른다.

- tail : 가장 최근에 issue된 instruction을 나타내며, 해당 entry를 youngest entry라 부른다.

- exception : speculative execution 도중에 발생한 exception 이 기록된다. 단 실제 exception 발생은 commit 단계에서 발생한다.

Speculative Tomasulo

Speculative Tomasulo를 설명하려면, Non-Speculative Tomasulo와 비교해보는게 이해하기 빠르다. 아래 그림을 보면서 Speculative Tomasulo와 Tomasulo를 비교해가며 설명을 해보자.

- 1. register file은 CDB가 아니라, reorder buffer가 commit 할 때 쓰여진다( 단 RS는 여전히 CDB에 의해 쓰여진다. )

따라서 register file은 이제 CDB와 연결되어 있지 않음을 볼수 있다. 이는 commit 되기 전 까지는 프로세서의 상태가 변경되지 않음을 보장한다.

 

- 2. Instruction이 issue될 때, ROB역시 operand value를 제공한다. 

만약 레지스터와 ROB 둘 모두에서 operand가 사용 가능하다면 ROB에 있는 값을 사용한다. ROB에 있는 값이 가장 최근에 register에 쓰여진 값(가장 youngest 한 값)이기 때문이다. 사실 이 부분은 상당히 고려해야 할 부분이 많고 복잡하니, Issue와 Write Result 단계를 설명할 때 이부분을 자세히 살펴보자.

 

- 3. store buffer가 사라지고, store buffer의 기능은 reorder buffer로 통합되었다.

 

- 4. address unit과 ROB에 data bus가 있다. 

address unit이 주소를 계산하면, ROB에 대기하고 있던 Store 명령어 entry의  destination field를 채워넣어야 하기 때문이다.

 

- 5. 각 Unit ( FU, Memory Unit ) 에 의한 결과값은 CDB를 통해 ROB에도 broadcasting 되어야 한다. 

broadcast 될 때에는 ROB entry number와 함께 broadcast되며, 따라서 ROB 해당 number에 대응하는 entry의 value field를 채워넣을 수 있게 된다. 

이때 RS에도 broadcasting이 되긴 하지만, 1 에서 설명 했듯 register file에는 broadcasting 되지 않는다. 

 

- 6. 이제 RS identifier가 수행하던 renaming 등의 역할은 ROB entry number 이 대신하게 된다.

instruction이 issue되면서 RS에 들어갈 때, 해당 instruction이 부여받은 ROB entry number도 함께 쓰여진다. 

Non-Speculative Tomasulo에서는 Write Result 단계에서 RS identifier  와 함께 value를 broadcast 했지만,  Speculative Tomasulo에서는 ROB entry number와 함께 broadcast 한다. 

예를들어 아래에서 ADD.D는 F0에 대해 먼저 Issue되어 Reorder Buffer에 있는 MUL.D에 의존적이다. 따라서 ADD.D가 Issue되어 RS에 들어갈 때는, RS1 field가 MUL.D의 ROB entry number로 채워진다. 이후 MUL.D 가 Write Result 단계에서 broadcasting 될 때, RS1 field가 ROB entry number 와 일치하면 ADD.D의  Val1 field 를 결과값으로 채워넣는다.

 

- 7. 이제 RS Identifier가 수행하던 역할은 ROB entry number가 대신하므로, Register 의 RS field는 필요없어서 사라졌다. 

 

Issue & Write Result Phase 

Speculative Tomasulo의 Issue phase를 자세히 살펴보자. 

instruction은 issue가 될 때 issue되는 순서대로 ROB entry number를 부여받고, RS와 ROB에 삽입된다( RS와 ROB에 여유공간이 있다면).

 

resolve dependent operand

instruction이 issue 될 때 operand는 ROB에서 발견된 경우와, 발견되지 않은 경우로 경우의 수를 나눠서 살펴보자.

 

1. operand source와 동일한 destination을 가진 ROB entry가 1개 이상 발견되었을 때

- 1.1. ready flag가 true인 entry가 그 중 가장 youngest 하다면, 이는 가장 최근에 write를 한(즉 program 순서상 마지막에 write한) 값이 되므로 사용해도 안전하다. 따라서 RS에 집어넣을 때 해당 entry의 value field를 가져와서 같이 써 넣는다.

- 1.2. ready flag가 true인 entry가 그 중 가장 youngest 하지 않다면, 최신이 아닌 값을 사용하는 것을 의미하므로 사용해선 안된다. true인 녀석이 가장 youngest 하지 않다는 건 youngest 한 녀석은 false임을 의미한다. false인 youngest 한 녀석의 ROB entry number를 RS의 RS1 혹은 RS2 (또는  Qj 혹은  Qk ) field 에 써준 후, 이후 나중에 CDB를 관찰하다 동일한 ROB entry number와 함께 value가 broadcast되면 update해준다.

 

2. 만약 ROB에서 동일한 destination을 가진 그 어떤 entry 도 발견되지 않았다면, 이는 Register File에 있는 값이 최신값임을 의미하므로 Register에 있는 값을 그대로 가져다 쓰면 된다.

Store instruction

Speculative Tomasulo는 store buffer가 없고, Store instruction이 issue 될 때 곧장 ROB라 insert된다. 만약 Store의 dependent operand(즉 write할 값)는 위 “resolve dependent operand” 에서와 동일하게 계산된 value를 그대로 가져오거나, ROB entry number 가져온 후 나중에 CDB를 관찰하다 동일한 ROB entry number와 함께 value가 broadcast되면 해당 value로 update해준다. ( 예를들어 아래 그림에서  # 12로 CDB broadcasting 이 온다면, result value인 1234로 # 13 Store 의 value field를 update 해준다 )

Commit Phase 

ROB의 head가 가리키는 entry는 in-order상 가장 먼저실행된 (가장 오래된) instruction이다. head가 가리키는 entry가 ready 상태라면, 이 명령어의 앞에는 분기 명령어가 없으므로 “확정적"인 (즉 프로그램 순서상 실제로 실행되었어야 할) 명령이며, 따라서 commit을 진행할 수 있음을 의미한다.

commit을 할 때는 head update를 하면서 instruction type에 따라 각각 다른 처리를 한다. 

 

branch operation

head가 branch라는 것은, branch이후에 ROB에 있는 명령어들은 모두 branch-prediction으로 예상한 지점에서 fetch/issue한 명령어 들이란 말이 된다.

 

- branch-prediction success

아무 행동도 취하지 않고 그냥 head만 한칸 올려주면 된다.

 

- branch-prediction failed

branch instruction은 commit처리를 하면서 head를 한칸 올린다. 이후 tail을 head와 같은 값으로 바꾸는 형태로 ROB를 모두 flush해버린다. 그리고 prediction이 틀렸으므로 Instruction Fetch 포인트를 반대 방향으로 고쳐잡고 fetch를 실행한다( 물론 branch 명령어 자체는 commit을 했으니, branch 명령어 이후부터 Instruction Fetch를 한다.   ).

 

Memory Load or register operation

head entry가 memory load나 ADD, MUL.D 와 같이 operation의 출력이 특정 register에 써지는 operation이라면, head entry에 있는 value field값을 destination register에 반영하는 것이 commit이다. 

 

Store operation

head entry가 Store 명령어라면, entry의 value field 값을 memory 주소에 Write하는 것이 commit이다.

 

CALL & RETN instruction

CALL은 사실 PUSH PC+4; JMP [target address];   두 명령어의 조합이고, RETN 명령어는 JMP [stack register]; POP; 두 명령어의 조합이다.

 

- POP, PUSH

POP은  단순히 ADD SP, 4 하는 연산으로, PUSH 는 SUB SP, 4; STORE value, [sp]; 두 명령어의 연속으로 구현한다.

 

- JMP [target address]

JMP [target address] 의 경우 target address가 정적으로 정해진 address라면 이는 “무조건" 분기이기에 prediction이 필요없고, 따라서 사실상 일반 명령어와 동일하게 취급된다.

반면 target address가 중간에서 메모리에서 가져온 값이거나 동적으로 계산되어지는 값이라면, target address를 예상해서 branch prediction을 해야하며, 이는 일반적인 true/false branch prediction보다 성공 확률이 극도로 낮을 것이다. 이런 경우도 branch prediction을 하는지는 모르겠지만, branch prediction을 하든 안하든 정적인 address에 대한 CALL보다 성능이 극도로 떨어지는건 자명하다.

Preserving Exception ( Precise Exception )

exception이 발생한 경우 entry의 exception field에 저장되었다가 commit 단계에서 실제 interrupt가 발생한다. 

How Much Speculation

언 뜻 봐서는 Speculative Execution은 있으면 무조건 좋은 것 처럼 보일것이다. Speculation이 성공하면 cycle 손실을 줄이는 반면, Speculation이 실패했다 하더라도 어차피 Speculation을 사용하지 않은것과 동일하게 cycle을 소모할테니   이러나 저러나 손해보는 장사는 아닌것 같아 보인다.

 

하지만 실상은 그렇지 않다. 다음 예시들을 봐보자.

예를들어 Speculative Execution을 진행하다 L2, L3 Cache Miss가 발생했다고 하자. 사실 L2, L3 Cache Miss 자체는  Speculative Execution의 성능을 떨어뜨리는 수준이지, 실패했을 때의 성능에 영향을 주지는 않는다(즉 아직까지는 다다익선이다). 문제는 실패했을 때, 다시 Eviction된 Cache가 필요한 경우이다. 

- Speculation 성공시 : prediction으로 미리 실행한 cycle만큼 아낀다.

- Speculation 실패시 : Speculative Execution에 의해 Eviction된 Cache가 다시 필요해지면 또다시 Cache-Miss가 발생한다. 

 

이처럼 Speculation 실패시의 비용이 큰 예외상황이 발생한다면, 딱 거기까지만 Speculation을 진행하고 예외상황이 commit될 때까지 대기(즉 미리 Issue하지 않는)하는 방안이 있다. 어느 수준만큼의 예외상황을 멈추지 않고 허용할지는 성공시 이득과  실패시 손실 사이의 기회비용, prediction 성공 확률 등등에 달려있다. 

* Page Fault의 경우는 프로세서에 실제 Page Fault Excpetion interrupt를 발생시켜야 Page를 가져올 수 있다. 따라서 내 추측이긴 하지만, 아마 Page Fault Exception이 발생하면 이 또한 딱 거기까지만 Speculation을 진행하고 Page Fault Exception이 commit될 때 까지 대기할 것으로 추측된다.