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

Tomasulo 알고리즘은 대표적인 Dynamic Scheduling 기법이다. 다이나믹 스케줄링은 하드웨어가 CPU stall을 줄이기 위해 명령어 실행 순서를 재배열하는 행위를 말하며, 이때 데이터의 흐름은 변경되지 않는다. 즉, 일종의 리팩토링인 셈

다이나믹 스케줄링을 통해 얻을 수 있는 이점
1. 컴파일 시점에 의존성을 알 수 없는 경우에도 통제가 가능하다.
2. 캐시 미스 같은 예측 불가능한 딜레이가 발생하는 경우에도 다른 코드를 실행하며 패널티를 줄일 수 있다.
3. 한 파이프라인에서 효율적으로 동작하도록 작성된 코드가 다른 파이프라인에서도 유효하다.
4. 실행 시점에 코드가 재배열되므로 컴파일러의 부담을 단순화할 수 있다.
5. 다이나믹 스케줄링은 Hardware Speculation에 도움이 된다.

DIVD F0, F2, F4
ADDD F10, F0, F8
SUBD F12, F8, F14

In-Order Execution 환경이라면, 다음 경우에 ADDD는 DIVD가 완전히 끝난 이후 실행된다. Out-of-Order Execution을 적용하면, ADDD가 DIVD의 결과(F0)를 기다리는 동안 SUBD를 실행할 수 있다. 다만, SUBD가 ADDD보다 먼저 Instruction Fetch(issue) 되는 것이 아니며, IF 순서는 여전히 In-Order이다.

Out-of-Order Execution은 MIPS 5 stage Pipeline을 더욱 세분화하여, Begins Execution과 Completes Execution을 구분한다.

MIPS 5 stage Pipeline은 Instruction Decode 1 스테이지 안에 Structural Hazard와 Data Hazard를 체크하기 때문에 부담이 크다. 이를 해결하기 위해 ID 스테이지를 다시 issue와 read operands 스테이지로 나눈다. Issue는 명령어를 디코드하고, Structural Hazard를 확인한다. read operands는 Data Hazard가 해결될 때까지 기다린 뒤 operand를 읽어들인다.

다이나믹 스케줄링은 예외 처리가 더 어려운 WAW(Write After Write), WAR(Write After Read) Hazard를 일으킬 수 있다.

Tomasulo Algorithm의 주요 특징
- 각 Function Unit(FU)마다 Control & buffers가 존재한다
* FU 버퍼는 Reservation Station(RS)이라 불리며, operand를 기다린다.
- 명령어 내에 있는 레지스터의 이름을 RS 값이나 포인터로 바꾼다. 이를 Register Renaming이라 한다.
* 이를 이용하면 원래 값이 변형되지 않아 WAR, WAW 해저드를 피할 수 있다.
* RS는 레지스터보다 많기 때문에 컴파일러가 하지 못하는 최적화도 가능하다.
- 결과값은 RS에서 FU로, 레지스터를 거치지 않고 이동한다. 이때 Common Data BUS를 사용하는데 일반적인 BUS가 data와 target id를 전송하여 해당 target만 데이터를 수신하는 반면, Common Data Bus는 data와 함께 source id를 전달하기 때문에 여러 FU에서 같은 값을 받는 게 가능하다.
* FU에 값이 존재할 때만 명령어를 실행할 수 있어 RAW 해저드를 피할 수 있다.
- load/store 또한 FU처럼 RS를 이용한다

Tomasulo 하드웨어 구성은 다음과 같다.

Reservation Station은 (구성에 따라 다르겠지만) 다음과 같은 7개의 영역을 가진다.
- op: operation
- Qj, Qk: src operand가 생성될 RS 번호 (Common Data Bus source로 사용될 값)
- Vj, Vk: src operand의 값
- A: 메모리 주소 (from/to)
- Busy: 해당 RS가 사용 중인지 나타내는 비트

레지스터 파일은 Qi 필드를 가진다.
- Qi: 레지스터에 저장될 값을 생산하는 FU를 지칭

토마슬로 알고리즘의 세 단계 과정
1. issue: FP Op Queue로부터 명령어를 받아온다.
RS가 비어있으면 (structural hazard가 없으면) 명령어를 issue하고 operand를 rename하여 전달한다.
2. Execute: 두 operand가 준비되면 실행한다. (EX)
그렇지 않으면 Common Data Bus를 통해 값이 전달되기를 기다린다.
3. Write Result: Execution을 종료한다. (WB)
Common Data Bus에 데이터를 쓰고 available을 1로 만든다. 데이터는 모든 awaiting unit에 전달되며 이 중 해당 RS를 기다리는 FU가 데이터를 받는다.

다음을 가정하고 예제를 살펴보자.
Floating Point +, -: 2 clocks
Floating Point *: 10 clocks
Floationg Point /: 40 clocks
load: 2 clocks

실행할 명령어는 다음과 같다.
Instructions:
LD F6 34+ R2
LD F2 45+ R3
MULTD F0 F2 F4
SUBD F8 F6 F2
DIVD F10 F0 F6
ADDD F6 F8 F2

이는 다음과 같이 실행된다.

먼저 첫 번째 사이클에 LD F6 34+ R2가 issue 된다. FU Load 1이 Busy로 세팅되며, 불러들일 Address는 34+R2이다. 해당 FU 번호가 Register File F6에 기록된다.

두 번째 사이클에 LD F2 45+ R3이 issue 된다. FU Load 2가 Busy, Address는 45+R3, Register File F2=Load2이다.

세 번째 사이클에는 MULTD F0 F2 F4가 이슈되며, RS Mult1에 세팅된다. 또한, LD F6 34+ R2의 실행이 끝난다.

네 번째 사이클에는 실행이 끝난 Load 1이 Common Data Bus에 WB하고, 두 번째 LD는 실행이 끝난다. SUBD가 Add1 RS로 이슈되면서 동시에 Common Data Bus에서 F6 값을 받아 세팅한다.

쭉쭉쭉 진행되어 57 사이클의 결과이다.

Tomasulo Algorithm은 Register Renaming을 통해 루프 당 각기 다른 physical destination을 설정할 수 있어 Loop Unrolling과 같은 효과를 낼 수 있다. (Dynamic Loop Unrolling)

Tomasulo Algorithm을 사용하면 hazard detection logic을 RS와 CDB로 분산시킬 수 있고, WAW, WAR 해저드로 인한 stall을 방지할 수 있다. 그러나 HW 복잡성이 증가하고 CDB로 인해 퍼포먼스가 제한되고, interrupt가 부정확하다는 단점이 있다.