[컴퓨터구조] Tomasulo Algorithm

Tomasulo Algorithm

 

 

In-order Execution vs Out-of-order Execution

In-order Execution

• 순차 실행 (순서대로 실행)
• 앞의 Instruction들이 Issue 되어야 현재 Instruction이 Issue 될 수 있다.
• RAW dependencies or structural hazards가 있을 때, 해결될 때까지 Issue 단계에서 Stall 된다.

 

Out-of-order Execution

• 비순차 실행 (실행 순서가 유동적)
• In-order와 달리 hazards가 존재하더라도, 기다리지 않고 Reservation Station에 Instruction이 전달된다.
• Issue Buffer 안에 있는 앞선 Instruction들이 있더라도, 뒤에 나오는 Instruction이 먼저 Issue 될 수 있다.

 

Issue Limitations

CSED503 from POSTECH

Out-of-order execution만으로는 성능 향상이 항상 일어나는 것은 아니다.

 

CSED503 from POSTECH

확실한 성능 향상을 위해서는 Register Renaming도 함께 적용되어야 한다. 위의 예시에서 f4 -> f4'으로 변경되면서 3번 instruction과 5번 instruction의 dependecy가 사라지면서 성능 향상을 얻을 수 있었다.

 

Tomasulo's Algorithm

Special Compiler 없이 Hazard를 피하면서 높은 floating-point 성능을 얻기 위해서 만들어진 알고리즘이다.

 

CSED503 from POSTECH

Function Unit마다 Buffer가 존재하는데, 이를 Reservation Station이라고 한다.

 

Reservation Station에 Instruction이 전달될 때, Register Renaming이 진행된다. Renaming을 통해 WAR, WAW Hazard를 피할 수 있다. 실제 Register보다 Reservation Station을 더 많이 할당할 수 있게 되어 Compiler가 기존에 하지 못하던 Optimization을 할 수 있게 된다.

 

Function Units(FU)에서 나온 결과는 Common Data Bus를 통해 Broadcast 된다. (Not Registers!) 이를 통해 RAW Hazard를 피할 수 있게 된다.

 

Load와 Stores는 reservation station을 사용하는 다른 FU와 동일하게 작동된다.

 

Tomaslo Algorithm은 Branch Prediction을 할 수 있고, Speculative exection이 가능하다. 하지만 Integer instruction들은 in-order로 실행되며, Branch prediction이 Correct인지 확인하지 전까지 FP Operation들은 실행할 수 없다.

 

 

Three Stages of Tomasulo Algorithm

1. Issue

Instruction이 FP Operation Queue -> Reservation Station으로 이동 (Reservation Station이 Free 해야 한다. 즉, structural hazard가 없어야 한다.) 이때 Reservation station entry에 저장되는 정보는 instruction과 operands이다.

 

2. Execute

operands가 모두 준비가 되면, 실행한다. 준비가 되지 않았다면, Common Data Bus에서 오는 Result 값들을 확인한다.

 

3. Write Result

Execution이 끝나는 부분으로, Common Data Bus 통해 이 결과를 기다리고 있는 Unit에 값을 전달하고 해당 Reservation Station에 available 한 상태임을 표시해야 한다.

 

Common Data Bus (CDB)

• Data + Source ("come from" bus)로, 데이터 값과, 어디로부터 왔는지 정보가 있는 Bus이다.
• 64bit data와 4bit tag bit이 존재하고, tag bit은 Functional Unit의 source address 또는 Reservation Station Number를 의미한다.
• Tag Bit이 Match 된다면 결과 값을 Write 한다.

 

Reservation Station Components

• Op: Operation 종류 (ex. ADD/SUB/...)
• Vj, Vk: source operand 값 (Store Buffer의 경우 결과 값을 store 하기 위한 V field가 존재한다)
• Qj, Qk: source register 값이 어디서 write 되는지에 대한 정보
• Busy: Reservation Station 또는 FU가 Busy 상태인지 확인
• Register Result Status: 어떤 FU가 해당 Register에 결과를 만드는지에 대한 정보를 담고 있음

 

Example

 

 

 

Dynamic Loop Unrolling Example

Tomasulo Algorithm의 경우 Branch 결과를 기다리지 않으면, Branch Prediction의 결과가 틀렸을 때, Reservation Station에 있는 값들이 잘못된 것을 돌려놓을 수 없다. 그렇기 때문에 Branch 결과를 기다려야 한다.

 

이때 Unrolling을 해주면 Branch를 줄일 수 있기 때문에 성능 향상이 일어날 수 있다. Register Renaming을 해주면 Physical Register 보다 더 큰 Register 수를 얻을 수 있기 때문에 loop unrolling에 대한 효과를 더 크게 받을 수 있다.

 

Reservation Station을 사용하면 Out-of-order로 실행되면서 Interger 연산과, Control Flow Operation이 먼저 완료되어 Branch가 Correct인지 알 수 있다. 그렇다면 다음 iteration들의 instruction을 미리 Issue 할 수 있게 된다. 또한, WAR Stall을 피할 수 있는데, 이는 Register의 이전 값을 Reservation Station에 저장해 둘 수 있기 때문이다.

 

2 Major Advantages of Tomasulo's Scheme

1. Distribution of the hazard detection logic

Distributed CDB와 Reservation Station를 통해 Result Write를 Simultaneously 하게 할 수 있고, 여러 Instruction에게 Broadcast가 가능하다. 만약 Centralized Register File이 사용되었다면, reigster bus가 가능할 때만 result 값을 읽을 수 있을 것이다.

 

2. Elimination of stalls for WAW and WAR hazard

 

Tomasulo Drawbacks

• Complexity
• Many associative stores (CDA) at high speed, it limts the clock frequency
• Performance limited by Common Data Bus
  • 각 CDB는 functional unit마다 존재해야 하므로 높은 wiring density와 capacitance가 필요하다
  • 한 사이클 당 Complete 할 수 있는 Functional Unit의 수는 1개로 제한된다. 여러 개의 CDB를 사용하게 되면, 더 많은 Parallel Associative Store을 위한 FU Logic이 필요해진다.
• Non-precise Interrupts