Data Dependencies and Register Renaming Techniques

Data Dependencies

While executing instructions it is quite possible that an instruction reads a value that the previous instruction changes.  In a pipeline, the first instruction thus, has to wait until the previous instruction finishes it's execution.This dependence of data of an instruction on it's previous instruction is referred to as data dependency. Data dependencies are of two types:

1. True Data Dependency
2. False Data Dependency

Let us now consider each of it with an example.

True Data Dependency

Consider the following example:

1. a = b + c

2. d = a + e

Instruction 2 depends on 'a' before it can start executing. Therefore instruction 1 must complete it's execution before instruction 2 can start. This is an example of true data dependency. Herein the input operands of one instruction directly depends on the output operands of the instruction(s) before or after it. Thus this is further divided into two: (1) Read after Write (RAW) (as shown above) and (2) Write after Read (WAR).

False Data Dependency

Consider the following example:

1. a = b + c

2. a = d + e

In a out-of-order execution type of processor, it may be quite possible that instruction 2 finishes it's execution before instruction 1. Therefore, the final value that we get of 'a' is due to instruction 1. Clearly, this is wrong because if the code were to run sequentially the final value of 'a' would  have been due to instruction 2. This is an example of false data dependency. This arises due to register reuse by the compiler. To avoid this we need to make sure that the instructions complete their execution in-order. The above mentioned example is also called WAW (Write after Write) type of dependency. Re-order buffer is used for solving this problem.

Architectural Register File (ARF)

Architectural register file consists of a set of registers. In our design of mini-superscalar processor, the ARF consists of 8 main registers named from R0-R7. As defined in our ISA, contents of R7 are equal to that contained in the PC (Program  Counter). A standard entry in the ARF is as:

Tag	Validity	Data/Reference-Tag
3 bit	1 bit	16 bit

The structure of the ARF can be understood by the following diagram:

The data_out consists of both validity bit and register data/tag value. The tag value is due to register renaming and it is explained in the Renamed Register File section. The validity bit is used by instruction issue unit, later on, to decide whether to dispatch that particular instruction or not.

Renamed Register File (RRF)

A renamed register file is the solution to true data dependency. Whenever we encounter an instruction, during decoding, which write backs to a register (let Rx), the validity bit of that register is changed to '0' and a register in the RRF is allotted to it. The tag associated with the allocated register is copied to the data/tag field of the original register (Rx) in the ARF. Thus, if a new instruction now arrives and asks for Rx, the information copied to the instruction is the tag value corresponding to the RRF.

Now when the value of Rx gets computed, it is broadcasted throughout and the value gets copied to the registers who store that value of tag with validity '0'. An entry in the RRF can be visualized as:

Tag	Used	Data/Reference-Tag
X  bits	1 bit	16 bit

The used bit is set to '1' whenever it is used by the ARF and it is cleared to '0' whenever it receives the broadcast corresponding to the tag. Number of registers present in the RRF is a design problem which decides the efficiency of the system. The RRF structure can be visualized as:

Note: The enable bit for the corresponding register is embedded with the associated input line.
I have implemented the RRF as a part of the ROB (Reorder Buffer) in my design of the mini-superscalar processor.

Combined Register File

The above described ARF and RRF consists of only basic data structure. There must be some control hardware which translates the requirements from the decoder into corresponding actual register actions. This control hardware along with the ARF and RRF forms the "Register File". This can be visualized as follows: