Tomasulo Algorithm

Register renaming provided -by reservation stations, which buffer the operands of instructions waiting to issue -by the issue logic Basic idea: -a reservation station fetches and buffers an operand as soon as it is available, as eliminating the need to get the operand from a register (WAR) -pending instructions designate the reservation station that will provide their input (RAW) -when successive writes to a register overlap in execution only the last one is actually used to update the register (WAW) As instructions are issued, the register markers for pending operands are renamed to the names of the reservation station, which provides register renaming (more reservation stations than real registers)

Properties of Tomasulo Algorithm

1. Control & Buffers distributed with Function Units (FU) -Hazard detection and execution control are distributed -FU buffers called, reservation stations have pending operands -Registers in instructions replaced by values or pointers to reservation stations (RS) 2. Bypassing: Results passed directly to FU from RS, not through registers, over common data bus (CDB) -that broadcasts results to all FUs, so allows all units wait for an operand to be loaded simultaneously

Components of Reservation Station

Op: Operation to perform in the unit Qj, Qk: Reservation stations producing the corresponding source operand. If a value of Qj or Qk is zero, the source operand is already available in Vj or Vk or not necessary. Vj, Vk: Value of Source operands -only one of V field or the Q field is valid -store buffers has V field, result to be stored A: Used to hold information for the memory address calculation for a load or a store Busy: Indicates reservation station or FU is busy Register result status Qi: Indicates which functional unit will write each register, if one exists. Blank when no pending instructions that will write that register

Three stages of Tomasulo Algorithm

1. Issue get instruction from FP OP Queue If reservation station is free (no structural hazard), control issues instructions and sends operands (renames registers). 2. Execute operate on operands When both operands are ready, then execute; if not ready, watch Common Data Bus (CDB) for result. 3. Write result (commit) finish execution Write on CDB to all awaiting units; mark reservation station available.

Note: Some other books or journals use commit instead of write result that I am really confused, especially in Tomasulo algorithm tables. The are basically same words. Basic Structure of a MIPS FU unit using Tomasulos algorithm

Tomasulo example (Loop)

Loop: mul mflo subi bgtz $t4,$t2 $t4 $t3,$t3,1 $t3,loop ! branch on greater than zero

this code calculate $t4 = $t2 ^ $t3, and initially $t4 = 1 and $t2 = 5 and $t3 = 2 add/sub/move takes 1 cycle of execute multiply takes 2 cycles branch takes 2 cycles two instructions are issued per cycle in this tomasulo example. When I try to understand Tomasulo tables, I am so confused to understand each tables and their fields, so I will explain them in here before I following the tables in each cycle. Reorder Buffer Entry Busy Instruction State Destination Value

Reorder Buffer -Allows instructions to execute out of order, but complete in order --Each instruction is allocated a reorder buffer entry at the tail of the buffer --Instructions write into their entry --Instructions complete out of the buffer in-order Entry->The number of order the machine is reading in Busy->If the register is in use, yes Instruction->The actual instruction goes here State->Three states go here Issue - Issue the instruction if there is an empty reservation station and an empty slot in the

Reorder buffer. If they are in the register file or reorder buffer, send the operands to the reservation station. Store the reorder buffer entry in the reservation station so the result can be tagged when it is written to the CDB Execute-Monitor CDB for results and execute operations from reservation stations when all Operands are ready Commit-When both the address and data value are available, they are sent to the memory Unit and the store complete. Then mark reservation stations available. Destination->The location of the register where the result will go Value->Value will be generated in the commit state Registers Field Data Reorder Busy $t0 $t1 Field the register location Data value stored in the register Reorder The entry line of code from Reorder Buffer associated with the register Busy yes if the register is in use Reservation Station Name Busy Op V1 V2 S1 S2 Dest A Name This is just name tag for the operand where you can keep track of operations. The generic names are load, add, mult, br, shift(sub/div/mflo/mfhi dont have their own name tags. When sub needed, it goes to add, as div to mult, mflo/mfhi to add) Busy yes if the register is in use Op this is actual Op working on V1/V2(Vj and Vk in our Textbook) These contain the value sof the source operands. Only one of the V field or S field is valid for each operand S1/S2(Qj and Qk in our Textbook) The reservation stations that will produce the corresponding Source operand. A value of zero indicates that the source Operand is already available in V1 or V2 or unnecessary Dest The location of the register that the resulting calculation will go A holding information for the memory address calculation for load and store

cycle 1 Reorder Buffer Entry Busy Instruction 1 y mul $t4,$t2 2 y mflo $t4 3 4 5 6 7 8 9 10 Reservation Station Name Busy Op Add1 mflo Add 2 Add3 Add4 Mul1 mul Mul2 Br1 Br2 V1 V2 S1 #1 S2 Dest #2 A State Destination issue $Hi, $Lo issue $t4 Value

Registers Field $t0 $t1 $t2 $t3 $t4 $t5 $t6 $t7 $t8 $t9 Data 5 2 1 Reorder Busy

#2

#1

In cycle 1, we issue the mul and mflo. As we explained in the Reservation Station, mflo goes to Add1 raw and its source from entry 1 and destination is entry 2($t4). mul goes Mul1 raw and its destination is entry 1 which is Hi/Lo, and will stall the mflo in the second cycle. Register also shows initial values like $t4 = 1, $t2 = 5, and $t3 = 2.

cycle 2 Reorder Buffer Entry 1 2 3 4 5 6 7 8 9 10 Busy y y y y Instruction mul $t4,$t2 mflo $t4 subi $t3,$t3,1 bgtz $t3,loop State exec issue issue issue Destination $Hi, $Lo $t4 $t3 Value

Registers Field $t0 $t1 $t2 $t3 $t4 $t5 $t6 $t7 $t8 $t9 Data 5 2 1 Reorder Busy

#3 #2

y y

Reservation Station Name Busy Op Add1 mflo Add 2 subi Add3 Add4 Mul1 y mul Mul2 Br1 bgtz Br2 V1 2 1 V2 1 5 #3 S1 #1 S2 Dest #2 #3 #1 #1 A

In cycle 2, we issue subi and bgtz. We put subi to Add2 and bgtz to Br1. Then we check to see if mul is ready to execute. Since no other operands use Hi/Lo, it will go to execute state, but this stage makes mflo must wait till mul completes execute which creates RAW hazard. Then, entry 2 is handled by $t4 and entry 3 is by $t3.

cycle 3 Reorder Buffer Entry 1 2 3 4 5 6 7 8 9 10 Busy y y y y y y Instruction mul $t4,$t2 mflo $t4 subi $t3,$t3,1 bgtz $t3,loop mul $t4,$t2 mflo $t4 State exec issue exec issue issue issue Destination $Hi, $Lo $t4 $t3 $Hi,$Lo $t4 Value

Registers Field $t0 $t1 $t2 $t3 $t4 $t5 $t6 $t7 $t8 $t9 Data 5 2 1 Reorder Busy

#3 #6

y y

Reservation Station Name Busy Op Add1 mflo Add 2 y subi Add3 mflo Add4 Mul1 y mul Mul2 mul Br1 bgtz Br2 V1 2 1 V2 1 #5 5 5 #2 #3 S1 #1 S2 Dest #2 #3 #6 #1 #5 #4 A

In cycle 3, subi is executed because of t3 is free. Second mul/mflo instructions are issued.

cycle 4 Reorder Buffer Entry 1 2 3 4 5 6 7 8 9 10 Busy no y n0 y y y y y Instruction mul $t4,$t2 mflo $t4 subi $t3,$t3,1 bgtz $t3,loop mul $t4,$t2 mflo $t4 subi $t3,$t3,1 bgtz $t3,loop State Destination commit $Hi, $Lo exec $t4 done $t3 exec issue $Hi,$Lo issue $t4 issue $t3 issue Value 5 1

Registers Field $t0 $t1 $t2 $t3 $t4 $t5 $t6 $t7 $t8 $t9 Data 5 1 1 Reorder Busy

#7 #6

y y

Reservation Station Name Busy Op Add1 yes mflo Add 2 subi Add3 mflo Add4 Mul1 Mul2 mul Br1 yes bgtz Br2 bgtz V1 5 1 V2 1 #5 5 1 #7 #2 S1 S2 Dest #2 #7 #6 #5 #4 #8 A

In cycle 4, mul is now in commit state and of value 5 is stored. subi is also done and stores value 1.

cycle 5 Reorder Buffer Entry 1 2 3 4 5 6 7 8 9 10 Busy Instruction n n y y y y y y y mflo $t4 subi $t3,$t3,1 bgtz $t3,loop mul $t4,$t2 mflo $t4 subi $t3,$t3,1 bgtz $t3,loop mul $t4,$t2 mflo $t4 State Destination commit $t4 commit $t3 exec exec $Hi,$Lo issue $t4 exec $t3 issue issue $Hi, $Lo issue $t4 Value 5 1

Registers Field $t0 $t1 $t2 $t3 $t4 $t5 $t6 $t7 $t8 $t9 Data 5 1 5 Reorder Busy

#7 #10

y y

Reservation Station Name Busy Op Add1 mflo Add 2 yes subi Add3 mflo Add4 Mul1 mul Mul2 mul Br1 yes bgtz Br2 bgtz V1 5 1 V2 1 #5 5 1 #7 #2 S1 #9 S2 Dest #10 #7 #6 #5 #4 #8 A

In this cycle 5, first mul is cleared in entry 1, and second mul is in execute. third mul/mflo instructions are issued. First subi is commit state, and second subi is executed. Second mflo is waiting for entry 5 to use t4.

cycle 6 Reorder Buffer Entry 1 2 3 4 5 6 7 8 9 10 Busy Instruction State Destination y subi $t3,$t3,1 issue $t3 y bgtz $t3,loop issue n y y n y y y bgtz $t3,loop mul $t4,$t2 mflo $t4 subi $t3,$t3,1 bgtz $t3,loop mul $t4,$t2 mflo $t4 commit exec $Hi,$Lo issue $t4 done $t3 issue issue $Hi, $Lo issue $t4 Value

Registers Field $t0 $t1 $t2 $t3 $t4 $t5 $t6 $t7 $t8 $t9 Data 5 1 5 Reorder Busy

#1 #10

y y

Reservation Station Name Busy Op Add1 mflo Add 2 subi Add3 mflo Add4 Mul1 mul Mul2 yes mul Br1 bgtz Br2 yes bgtz V1 0 V2 1 #5 5 0 5 5 #6 #2 S1 #9 S2 Dest #10 #1 #6 #9 #5 #2 #8 A

Third subi/bgtz is issued in entry 1 and 2. First subi in entry 3 is cleared.

cycle 7 Reorder Buffer Entry 1 2 3 4 5 6 7 8 9 10 Busy Instruction State Destination y subi $t3,$t3,1 issue $t3 y bgtz $t3,loop issue n y n y y y mul $t4,$t2 mflo $t4 subi $t3,$t3,1 bgtz $t3,loop mul $t4,$t2 mflo $t4 commit $Hi,$Lo exec $t4 done $t3 exec issue $Hi, $Lo issue $t4 Value

Registers Field $t0 $t1 $t2 $t3 $t4 $t5 $t6 $t7 $t8 $t9 Data 5 1 5 Reorder Busy

25 0

#1 #10

y y

Reservation Station Name Busy Op Add1 mflo Add 2 subi Add3 y mflo Add4 Mul1 mul Mul2 Br1 bgtz Br2 yes bgtz V1 0 25 V2 1 5 0 #6 #2 S1 #9 S2 Dest #10 #1 #6 #9 #2 #8 A

In cycle 7, mul in entry 5 is committed and value 25 is stored. Seond subi is also done and value 0 is stored.

cycle 8 Reorder Buffer Entry 1 2 3 4 5 6 7 8 9 10 Busy y y y y Instruction subi $t3,$t3,1 bgtz $t3,loop mul $t4,$t2 mflo $t4 State Destination exec $t3 issue issue issue Value

Registers Field $t0 $t1 $t2 $t3 $t4 $t5 $t6 $t7 $t8 $t9 Data 5 0 25 Reorder Busy

#1 #4

y y

n y y

bgtz $t3,loop flush mul $t4,$t2 exec $Hi, $Lo mflo $t4 issue $t4

Reservation Station Name Busy Op Add1 mflo Add 2 y subi Add3 mflo Add4 Mul1 y mul Mul2 Br1 bgtz Br2 V1 0 25 V2 1 #3 5 #2 S1 #9 S2 Dest #10 #1 #4 #9 #2 A

In cycle8, bgtz in entry 8 is flushed due to t3 = 0. Stations are also flushed. And any execute cancelled. No more update! Registers got their final values like t2=5, t3=0 and t4=25.