Speculative Tomasulo Algorithm - 임베디드 컴퓨터 구조

Tomasulo's Algorithm 리뷰

• Reservation Station을 사용하여 in-order issue 된 명령을 out-of-order로 실행하는 하드웨어 구조
• Register가 Renaming 되는 효과가 있어 out-of-order 시 발생할 수 있는 WAR, WAW Hazard를 방지할 수 있다.
• Loop Unrolling 기법을 하드웨어를 통해 실시할 수 있다. (컴파일러의 부담이 줄어든다.)
• Cache Miss 시에도 딜레이가 생기는 동안 다른 작업을 실행하므로 도움이 된다.

예측 기반 Tomasulo's Algorithm (Speculative Tomasulo's Algorithm)

Speculative Tomasulo's Algorithm은 Branch Prediction을 예측하여 Instruction을 issue 하고, 예측이 틀릴 경우 되돌아올 수 있는 로직을 탑재한, Tomasulo's Algorithm의 향상된 버전이다.

ILP (Instruction Level Parallelism)을 향상시키기 위해 Speculation, Dynamic Scheduling(= 여기선 Tomasulo's Algorithm)을 사용한다. Branch를 마주하면 멈추는 대신, predict가 100% correct 하다는 가정 하에 계속해서 명령어를 실행한다.

3 Components of HW-based Speculation

1. Dynamic Branch Prediction (e.g. Branch Target Buffer)
2. Control Dependence가 해소되기 전에 명령을 실행하는 로직 + 잘못 예측된 seq의 작업을 undo 할 수 있는 장치
3. 다른 Basic Block을 동시에 실행시킬 수 있는 Dynamic Scheduling (= Tomasulo's Algorithm)

Adding Speculation to Tomasulo

Tomasulo Pipeline: IF IS EX WB
Speculative Tomasulo: IF IS EX Exec Completion Instruction Commit

Execution Completion은 Functional Unit의 연산이 끝나서 해당 값을 다른 유닛에 전송하는 스테이지이며,
Branch Prediction이 맞았을 경우 register나 00의 값을 업데이트 하는 스테이지를 Instruction Commit이라고 한다. Write Back이 두 개의 스테이지로 나뉘었다고 보아야한다.

명령어의 결과값을 커밋을 하거나 폐기하려면, 먼저 결과값을 저장할 중간 저장소가 필요하며 이를 Reorder Buffer (ROB)라고 한다. Execution이 Out-of-Order로 실행되고 끝나지만, 이를 다시 정렬하여 in-order 순서로 적용되도록 하는 역할을 하기 때문에 Reorder Buffer라는 이름이 붙은 것이다.

Reorder Buffer Operation

• 명령어 실행이 종료되면 결과가 ROB에 저장된다.
  • 해당 값을 기다리는 다른 명령어에 값을 제공한다.
  • RS와 같이 추가적인 레지스터에 해당한다.
• Instruction Commit 되면 ROB Head의 값이 레지스터에 저장된다.
• mispredict 시에는 값을 레지스터에 옮기지 않는다.
  • easy to undo instruction
• 기존 Tomasulo's Algorithm은 바로 레지스터에 값이 저장되고 Register File에서 값을 읽어왔음.
  • 이제는 Latest Value 확인을 위해 Reorder Buffer를 Search 하고 탐색 실패 시 Register File을 Search

Reorder Buffer Entry

각각의 ROB Entry는 네 개의 필드를 갖는다.

1. Instruction Type:
   • branch (= destination 없음)
   • store (= memory address가 destination)
   • register operation (e.g. add, sub, load) (= Register Destination)
2. Destination:
   • Memory Address (= store)
   • Register Number (= ALU operation or load)
   • 기존의 source id와 같은 기능
3. Value:
   • result value of instruction until commit
4. Ready:
   • complete exec, ready to commit value

Reorder Buffer는 Issue 되는 순서대로 차곡차곡 쌓이며, Execution Complete 때 값이 완성되며 Ready bit이 Set 된다. Commit 시 Value 필드의 값이 Destination Field의 Address에 기록한다. Mispredicted Branch의 경우 Reorder Buffer를 Flush 하며, 아직 ROB의 value가 메모리나 Register에 끼친 영향이 없으므로 harmless 하다. Flush를 하기 위해 ROB에서 head pointer와 tail pointer를 업데이트한다.

Flush 과정을 이해하기 위해 다음 그림을 통해 과정을 살펴보자

먼저 LD F0 10(R2) 명령어가 issue 되었다. 해당 명령어는 Load Reservation Station에 전달된다. 그림에서 ROB 필드 순서는 Destination, Value, Instruction Type, Ready 순이다. Load RS의 Destination이 1로 세팅된 이유는 해당 RS의 결과값이 ROB 1에 전달되어야 하기 때문이다. 이렇듯 RS의 Destination에는 이전의 source id와는 달리, ROB의 ID가 Destination ID로 사용된다.

 

계속해서 명령어가 이슈되고 RS가 설정된다. RS는 연산을 위해 레지스터 값을 ROB에서 찾는다. 마침 F0, F10이 ROB1, ROB2를 통해 생성되므로 해당 ID의 결과값을 위해 대기한다.

Branch Instruction이 들어오고, Prediction이 맞다는 가정하에 예측된 PC에서 명령어를 가져와 ROB와 RS를 세팅한 모습이다.

Store 명령어의 경우, 레지스터 F4의 값이 ROB5에서 나오기 때문에 ROB5의 결과값으로 대체한다. (사실 value field와 ROB field는 따로 존재하지만, 예시 그림에서는 공간의 한계로 합쳐져 있다...)

명령어가 실행되고 있는 모습이다.

실제로 이렇게 설계될 일은 없겠지만, prediction이 틀렸을 경우 ROB가 Flush 되는 모습을 보여주기 위한 구성이다. 아직 ROB 1의 명령어가 완료되지 않아, Head Pointer는 ROB 1을 가리키고 있다. Tail Pointer는 명령어가 issue 될 때마다 하나씩 증가하여, 현재 ROB 7을 가리키고 있다. (물론 구현에 따라 달라지겠지만..)

만일 ROB3까지 결과값이 생성되고, Branch를 했는데 Prediction이 틀렸을 경우, Tail Pointer를 ROB3으로 옮긴다. 자연스럽게 다음 이슈되는 명령어는 ROB4부터 ROB를 덮어쓰고, 우리는 데이터를 지우거나, Undo 하거나 할 필요없이 ROB를 Flush 할 수 있다. (Head Pointer도 ROB3을 가리키고 있다.)