Friday, September 2, 2011

Register Renaming

Register renaming is the action of replacing the registers used by an instruction with different registers.

When register renaming is used, there are more physical registers (actual hardware registers) than there are logical registers.  A logical register is a register which is defined to exist by the architecture, but this is purely an "on-paper" existence.  The actual meat of the register, what's called the physical register, can be different from the logical register the programmer works with.

The extra registers are used to solve the WAW and WAR data dependencies by rewriting the instructions to use an unused register for storing results, and updating which registers are used as inputs (because they could be depending on the result of another instruction which has had its result register moved somewhere else).

As an example, lets say you have the following code:
move   r1, r2
move   r2, r3

These instructions have a WAR data dependency.  Lets say that "r" represents a logical register, and "R" represents a physical register.  After renaming, the code might look like this:
move   R7, R3
move   R4, R5

Alright, so lets explain what happened to the first instruction.  It takes as an input the value in the logical register r2.  The last instruction to store a value in r2 (which is the value we want) stored it into the physical register R3 (because that was an unused register at the time), so the instruction is rewritten to take the value in R3 as the input.  The instruction also has an output/result value, which is stored in the logical register r1.  In order to ensure that this instruction does not overwrite a value that another instruction is depending on, an unused register is selected, in this case R7.

The explanation for the second instruction is pretty much the same as for the first.  However, notice what happens to the result register for the second instruction; it is different than the register used as an input in the first instruction.  This means that there is no longer a WAR data dependency between the two instructions!  The register written to by the second instruction is physically different (even though it appears to be logically the same from the perspective of the program code) from the register the second instruction reads from.

WAW data dependencies are solved by renaming as well because both write instructions are changed to write to different physical registers, even though they are writing to the same logical register; so it doesn't matter in which order they are executed.

This is probably a good place to confuse you by saying that there are different methods of renaming.  The methods I am familiar with all work basically the way I described, so you should be able to take this general overview and learn the nittier-grittier details.

No comments:

Post a Comment