# Dyn Sched CSE 471: Enhancements to Tomasulo's Algorithm

This article discusses the weaknesses of Tomasulo's algorithm such as centralized control and no forwarding. It also explores the concept and implementation of renaming registers which eliminates WAR and WAW hazards. Additionally, it proposes an improvement to dispatch with reservation stations.

## About Dyn Sched CSE 471: Enhancements to Tomasulo's Algorithm

PowerPoint presentation about 'Dyn Sched CSE 471: Enhancements to Tomasulo's Algorithm'. This presentation describes the topic on This article discusses the weaknesses of Tomasulo's algorithm such as centralized control and no forwarding. It also explores the concept and implementation of renaming registers which eliminates WAR and WAW hazards. Additionally, it proposes an improvement to dispatch with reservation stations.. The key topics included in this slideshow are Dyn Sched, Tomasulo's algorithm, reservation stations, register renaming, functional unit,. Download this presentation absolutely free.

## Presentation Transcript

1. Dyn. Sched. CSE 471 Autumn 02 19 Tomasulos algorithm Weaknesses in scoreboard: Centralized control No forwarding (more RAW than needed) Tomasulos algorithm as implemented first in IBM 360/91 Control decentralized at each functional unit Forwarding Concept and implementation of renaming registers that eliminates WAR and WAW hazards

2. Dyn. Sched. CSE 471 Autumn 02 20 Improving on Dispatch with Reservation Stations With each functional unit, have a set of buffers or reservation stations Keep operands and function to perform Operands can be values or names of units that will produce the value ( register renaming ) with appropriate flags Not both operands have to be ready at the same time When both operands have values, functional unit can execute on that pair of operands When a functional unit computes a result, it broadcasts its name and the value.

3. Dyn. Sched. CSE 471 Autumn 02 21 Tomasulos solution to resolve hazards Structural hazards No free reservation station (stall at issue time). No further issue RAW dependency (detected in each functional unit -- decentralized) The instruction with the dependency is issued (put in a reservation station) but not dispatched (stalled). Subsequent instructions can be issued, dispatched, executed and completed. No WAR and WAW hazards Because of register renaming through reservation stations Forwarding Done at end of execution by use of a common (broadcast) data bus

4. Dyn. Sched. CSE 471 Autumn 02 22 Example machine (cf. Figure 3.2) From memory From I-unit Fp registers Load buffers Store buffers To memory Reservation stations F-p units Common data bus

5. Dyn. Sched. CSE 471 Autumn 02 23 An instruction goes through 3 steps Assume the instruction has been fetched 1. Issue, dispatch, and read operands Check for structural hazard (no free reservation station or no free load-store buffer for a memory operation). If there is structural hazard, stall until it is not present any longer Reserve the next reservation station Read source operands If they have values, put the values in the reservation station If they have names, store their names in the reservation station Rename result register with the name of the reservation station in the functional unit that will compute it

6. Dyn. Sched. CSE 471 Autumn 02 24 An instruction goes through 3 steps (ced) 2. Execute If any of the source operands is not ready (i.e., the reservation station holds at least one name), monitor the bus for broadcast When both operands have values, execute 3. Write result Broadcast name of the unit and value computed. Any reservation station/result register with that name grabs the value Note two more sources of structural hazard : Two reservation stations in the same functional unit are ready to execute in the same cycle: choose the first one Two functional units want to broadcast at the same time. Priority is encoded in the hardware

7. Dyn. Sched. CSE 471 Autumn 02 25 Implementation All registers (except load buffers) contain a pair {value,tag} The tag (or name) can be: Zero (or a special pattern) meaning that the value is indeed a value The name of a load buffer The name of a reservation station within a functional unit A reservation station consists of : The operation to be performed 2 pairs (value,tag) ( Vj,Qj) (Vk,Qk) A flag indicating whether the accompanying f-u is busy or not