Instruction_lifecycle Tomasulo_algorithm

1 instruction lifecycle

1.1 register legend
1.2 stage 1: issue

1.2.1 pseudocode


1.3 stage 2: execute

1.3.1 pseudocode


1.4 stage 3: write result

1.4.1 pseudocode

instruction lifecycle

the 3 stages listed below stages through each instruction passes time issued time execution complete.

register legend

op - represents operation being performed on operands
qj, qk - reservation station produce relevant source operand (0 indicates value in vj, vk)
vj, vk - value of source operands
a - used hold memory address information load or store
busy - 1 if occupied, 0 if not occupied
qi - (only register unit) reservation station result should stored in register (if blank or 0, no values destined register)

stage 1: issue

in issue stage, instructions issued execution if operands , reservation stations ready or else stalled. registers renamed in step, eliminating war , waw hazards.

retrieve next instruction head of instruction queue. if instruction operands in registers, then

if matching functional unit available, issue instruction.
else, there no available functional unit, stall instruction until station or buffer free.


otherwise, can assume operands not in registers, , use virtual values. functional unit must calculate real value keep track of functional units produce operand.

pseudocode

example of tomasulo s algorithm


stage 2: execute

in execute stage, instruction operations carried out. instructions delayed in step until of operands available, eliminating raw hazards. program correctness maintained through effective address calculation prevent hazards through memory.

if 1 or more of operands not yet available then: wait operand become available on cdb.
when operands available, then: if instruction load or store

compute effective address when base register available, , place in load/store buffer

if instruction load then: execute memory unit available
else, if instruction store then: wait value stored before sending memory unit




else, instruction arithmetic logic unit (alu) operation then: execute instruction @ corresponding functional unit

pseudocode

stage 3: write result

in write result stage, alu operations results written registers , store operations written memory.

if instruction alu operation

if result available, then: write on cdb , there registers , reservation stations waiting result


else, if instruction store then: write data memory during step

pseudocode