Lecture 15a: Out-of-Order Execution

for example, we are trying to excute the red instruction "Add R3 R4".

we need R3 so we check reorder buffer whether it is valid or not

if not valid we stall the instruction. if valid we can take bypass and take value from reorder buffer.

 

 

notice below red instruction there are no depdency.

but since in red instruction R3 has to wait for IMUL instrction (8 cycles) , other 3 blue line instruction still has to wait.

to solve this we need Out of Order Execution 

 

 

Out of Order Execution (Dynamic Scheduling)

Move the dependent instructions out of the way of independent ones.

notice we are still using reorder buffer to seqeuntially exectue instruction so programmer don't get confused.

in out of order execution we don't stall instruction we put it somewherer else and continue executing independent instructions.

 

Enableling Out of Order Execution

1. need to link the consumer of a value to the producer ,  to track when value is ready we can fire instruction

• register renaming  = associate a "tag" with each data value

 

2. need to buffer instruction until they are ready to execute

• insert instruction into rservation stations afater renaming

 

3. instructions need to keep track of readiness of source values

• broadcast the "tag" when the value is produced
• instructions compare their "source tags" to the broadcast tag = if match source value becomes ready

 

4. when all source values of an instruction are ready , need to dispatch the instruction to its functional unit 

• instruction wakes up if all sources are ready
• if mutiple instructions are awake , need to select one per FU

 

 

Tomasulo's algorithm : Renaming

first we initialize our adder or mutiplier with given regster alias table row. for example , MUL R1 R2 -> R3 is stored in mutiplier table and it's identifier is x and destination register R3 is renamed to x.

other instructions are also initialized and they can be executed only if both sorce1 and source2 are valid. for example , now at add table at a row source 1 is not valid , it is dependent on x and waiting.

now MUL R1 R2 -> R3 instruction has finished. it will broadcast 'x' and every table will check wether they have x or not. for example, inside register alias table R3 was renamed to x with valid 0 , but now it can change to valid state and have real valid value. same for 'a' row in add table.

now 'a' row at add table are ready so it is going to execute on the next cylce (9).