patternMinor
When to free physical registers
Viewed 0 times
physicalregistersfreewhen
Problem
When we do register renaming to avoid WAR and WAW hazards while executing instructions, how can we know that there is no need for a physical register anymore and we can put it back in the free list?
Solution
I find the simplest way to think about this problem is to consider a machine that has two Register Alias Tables (RAT). These tables simply store the physical register identifier associated with each architectural register.
The two tables sit in the retirement stage (the Retirement Register Alias Table or RRAT), and the renaming stage. Retirement and renaming both happen in-order, no matter how the execution stages work. The Retirement-RAT represents the architectural/non-speculative state of the machine. The renaming RAT represents the speculative state of the machine (the state the machine will have if all of the speculative decisions made before the current instruction were to be found to have been correctly predicted).
Think about the state of the Retirement Register Alias Table just before the retirement of an instruction that writes to (architectural) register $R$. At this point the Retirement Register Alias Table contains a mapping from $R$ to $P_0$, the previous physical register that was assigned to architectural register $R$, and the next instruction to retire will have a different assignment from $R$ to $P_1$. Since retirement happens in-order, we know that all instructions that could have referenced physical register $P_0$ have already retired, and thus physical register $P_0$ can be returned to the free list.
Many (most) actual out-of-order designs do something more complicated than what I've described here (instead of Register Alias Tables mapping from architectural to physical registers, there are CAMs mapping from physical to architectural registers which allows quicker recovery from mis-speculations), but the reasoning techniques are the same: renaming and retirement both happen in-order, and you can use that fact to reason about which registers can be returned to the free list.
The two tables sit in the retirement stage (the Retirement Register Alias Table or RRAT), and the renaming stage. Retirement and renaming both happen in-order, no matter how the execution stages work. The Retirement-RAT represents the architectural/non-speculative state of the machine. The renaming RAT represents the speculative state of the machine (the state the machine will have if all of the speculative decisions made before the current instruction were to be found to have been correctly predicted).
Think about the state of the Retirement Register Alias Table just before the retirement of an instruction that writes to (architectural) register $R$. At this point the Retirement Register Alias Table contains a mapping from $R$ to $P_0$, the previous physical register that was assigned to architectural register $R$, and the next instruction to retire will have a different assignment from $R$ to $P_1$. Since retirement happens in-order, we know that all instructions that could have referenced physical register $P_0$ have already retired, and thus physical register $P_0$ can be returned to the free list.
Many (most) actual out-of-order designs do something more complicated than what I've described here (instead of Register Alias Tables mapping from architectural to physical registers, there are CAMs mapping from physical to architectural registers which allows quicker recovery from mis-speculations), but the reasoning techniques are the same: renaming and retirement both happen in-order, and you can use that fact to reason about which registers can be returned to the free list.
Context
StackExchange Computer Science Q#103433, answer score: 4
Revisions (0)
No revisions yet.