how are the dependencies between instructions determined? also how does the system know how to rearrange the instructions?
bpr
@gogogo, after decoding each instruction, the processor knows which registers supply values used and which register will be updated by the instruction. The processor then has a structure that tracks whether a register is ready (and if so, it's value), as well as what instruction will next update that register. Effectively, this enables the processor to create a graph of dependencies between the instructions based on their registers, and determine when an instruction has satisfied its dependencies and is ready to be issued.
ferozenaina
I found some notes on basic out-of-order Tomasulo algorithm implemented on IBM 360 in 1970s which uses the Reorder Buffer mentioned in slide. Modern processors call this dynamic execution and use a derivative of this algorithm.
A key feature is hardware register renaming - if a value is unavailable to a register during issue, a placeholder is used which is later replaced with the real value from the instruction buffer.
Resources: https://cseweb.ucsd.edu/classes/fa11/cse240A-a/Slides1/09_OutOfOrderExecution.pdf and https://en.wikipedia.org/wiki/Tomasulo_algorithm
how are the dependencies between instructions determined? also how does the system know how to rearrange the instructions?
@gogogo, after decoding each instruction, the processor knows which registers supply values used and which register will be updated by the instruction. The processor then has a structure that tracks whether a register is ready (and if so, it's value), as well as what instruction will next update that register. Effectively, this enables the processor to create a graph of dependencies between the instructions based on their registers, and determine when an instruction has satisfied its dependencies and is ready to be issued.
I found some notes on basic out-of-order Tomasulo algorithm implemented on IBM 360 in 1970s which uses the Reorder Buffer mentioned in slide. Modern processors call this dynamic execution and use a derivative of this algorithm.
A key feature is hardware register renaming - if a value is unavailable to a register during issue, a placeholder is used which is later replaced with the real value from the instruction buffer.
Resources: https://cseweb.ucsd.edu/classes/fa11/cse240A-a/Slides1/09_OutOfOrderExecution.pdf and https://en.wikipedia.org/wiki/Tomasulo_algorithm