Dependencies and Data Hazard in pipeline in Computer Organization
In this section, we will learn about dependencies in a pipelined processor, which is described as follows:
Dependencies in pipeline Processor
The pipeline processor usually has three types of dependencies, which are described as follows:
- Structural dependencies
- Data dependencies
- Control dependencies
Because of these dependencies, the stalls will be introduced in a pipeline. A stall can be described as a cycle without new input in the pipeline. In other words, we can say that the stall will happen when the later instruction depends on the output of the earlier instruction.
Structural dependencies
Because of the resource conflict in the pipeline, structural dependency usually arises. The resource conflict can be described as a situation where there is a cycle containing resources such as ALU (arithmetical logical unit), memory, or register. In resource conflict, more than one instruction tries to access the same resource.
Example:
| Instructions / Cycle | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I1 | IF(Mem) | ID | EX | Mem | |
| I2 | IF(Mem) | ID | EX | ||
| I3 | IF(Mem) | ID | EX | ||
| I4 | IF(Mem) | ID |
The above table contains the four instructions I1, I2, I3, and I4, and five cycles 1, 2, 3, 4, 5. In cycle 4, there is a resource conflict because I1 and I4 are trying to access the same resource. In our case, the resource is memory. The solution to this problem is that we have to keep the instruction on wait as long as the required resource becomes available. Because of this wait, the stall will be introduced in pipelines like this:
| Instructions / Cycle | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| I1 | IF(Mem) | ID | EX | Mem | WB | |||
| I2 | IF(Mem) | ID | EX | Mem | WB | |||
| I3 | IF(Mem) | ID | EX | Mem | WB | |||
| I4 | – | – | – | IF(Mem) |
Solutions for Structural dependency
With the help of a hardware mechanism, we can minimize the structural dependency stalls in a pipeline. The mechanism is known as renaming.
Remaining: In this mechanism, the memory will be divided into two independent modules, which are known as Data memory (DM) and Code memory (CM). Here, all the instructions are contained with the help of CM, and all the operands which are required for the instructions are contained by the DM.
| Instructions / Cycle | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| I1 | IF(CM) | ID | EX | DM | WB | ||
| I2 | IF(CM) | ID | EX | DM | WB | ||
| I3 | IF(CM) | ID | EX | DM | WB | ||
| I4 | IF(CM) | ID | EX | DM | |||
| I5 | IF(CM) | ID | EX | ||||
| I6 | IF(CM) | ID | |||||
| I7 | IF(CM) |
Control Dependency (Branch Hazards)
When we transfer the control instructions, the control dependency will occur at that time. These instructions can be JMP, CALL, BRANCH, and many more. On many instruction architectures, when the processor wants to add the new instruction into the pipeline, the processor does not know the target address of these new instructions. Because of this drawback, unwanted instructions are inserted into the pipeline.
For example:
For this, we will assume a program and take the following sequence of instructions like this:
100: I1 101: I2 102: I3 . . 250: BI1
Expected Output is described as follows:
I1 → I2 → BI1
Note: After the ID stage, the processor is able to know the target address of JMP instruction.
| Instructions / Cycle | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| I1 | IF | ID | EX | MEM | WB | |
| I2 | IF | ID(PC:250) | EX | MEM | WB | |
| I3 | IF | ID | EX | MEM | ||
| BI1 | IF | ID | EX |
The output sequence is described as follows:
I1 → I2 → I3 → BI1
So the above example shows that the expected output and output sequence are not equal to each other. It shows that the pipeline is not correctly implemented.
We can correct that problem with the help of stopping the instruction fetch as long as we get the target address of branch instruction. For this, we will implement the delay slot as long as we get the target address, which is described in the following table:
| Instructions / Cycle | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| I1 | IF | ID | EX | MEM | WB | |
| I2 | IF | ID(PC:250) | EX | MEM | WB | |
| Delay | – | – | – | – | – | – |
| BI1 | IF | ID | EX |
The output sequence is described as follows:
I1 → I2 → Delay (Stall) → BI1
In the above example, we can see that there is no operation performed by the delay slot. That’s why this output sequence and the expected output are not equal to each other. But because of this slot, a stall will be introduced in the pipeline.
Solution for Control Dependency
In the control dependency, we can eliminate the stall in the pipelines with the help of a method known as Branch prediction. The prediction about which branch will be taken is done at the 1st stage of branch prediction. The branch prediction contains the 0 branch penalty.
Branch Penalty: Branch penalty can be described as the number of stalls that are introduced at the time of branch operation in the pipelined.
Data Dependency (Data Hazards)
For this, we will assume an ADD instruction S, and three registers, which are described as follows:
In the following way, the instruction S2 will depend on instruction S1:
The above condition is known as the Bernstein condition. In this condition, there are three cases, which are described as follows:
Flow (data) Dependence: Suppose this dependency contains O(S1) ? I(S2), S1 → S2. In this case, when S2 reads something, only after that, S1 write.
Anti Dependence: Suppose this dependency contains I(S1) ? O(S2), S1 → S2. In this case, before S2 overwrite S1, the S1 will read something.
Output Dependence: Suppose this dependency contains O(S1) ? O(S2), S1 → S2. In this case, both S1 and S2 write on the same memory location.
For example: Here, we will assume that we have two instructions I1, and I2, like this:
I1: ADD R1, R2, R3 I2: SUB R4, R1, R2
The condition of data dependency will occur when the above instructions I1, I2 are executed in a pipelined processor. It shows that before I1 writes the data, the I2 tries to read it. As a result, the instruction I2 incorrectly gets the old value from I1, which is described in the following table:
| Instructions / Cycle | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| I1 | IF | ID | EX | DM |
| I2 | IF | ID (Old value) | EX |
Here we will use the operand forwarding so that we can minimize the stalls in data dependency.
Operand Forwarding: In this forwarding, we will use the interface registers which exist between the stages. These registers are used to contain the intermediate output. With the help of intermediate registers, the dependent instruction is able to directly access the new value.
To explain this, we will take the same example:
I1: ADD R1, R2, R3 I2: SUB R4, R1, R2
| Instructions / Cycle | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| I1 | IF | ID | EX | DM |
| I2 | IF | ID | EX |
Data Hazards
Due to the data dependency, data hazards have occurred. If the data is modified in different stages of a pipeline with the help of instructions that exhibit data dependency, in this case, the data hazard will occur. When the instructions are read/write the registers that are used by some other instructions, in this case, the instruction hazards will occur. Because of the data hazard, there will be a delay in the pipeline. The data hazards are basically of three types:
- RAW
- WAR
- WAW
To understand these hazards, we will assume we have two instructions I1 and I2, in such a way that I2 follows I1. The hazards are described as follows:
RAW:
RAW hazard can be referred to as ‘Read after Write’. It is also known as Flow/True data dependency. If the later instruction tries to read on operand before earlier instruction writes it, in this case, the RAW hazards will occur. The condition to detect the RAW hazard is when On and In+1 both have a minimum one common operand.
For example:
I1: add R1, R2, R3 I2: sub R5, R1, R4
There is a RAW hazard because subtraction instruction reads output of the addition. The hazard for instructions ‘add R1, R2, R3′ and ‘sub R5, R1, R4′ is described as follows:
| Instructions / Cycle | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| I1 | IF | ID | EX | MEM | WB | |
| I2 | IF | ID | EX | MEM | WB |
The RAW hazard is very common.
WAR
WAR can be referred to as ‘Write after Read’. It is also known as Anti-Data dependency. If the later instruction tries to write an operand before the earlier instruction reads it, in this case, the WAR hazards will occur. The condition to detect the WAR hazard is when In and On+1 both have a minimum one common operand.
For example:
The dependency is described as follows:
add R1, R2, R3 sub R2, R5, R4
Here addition instruction creates a WAR hazard because subtraction instruction writes R2, which is read by addition. In a reasonable (in-order) pipeline, the WAR hazard is very uncommon or impossible. The hazard for instructions ‘add R1, R2, R3′ and ‘sub R2, R5, R4′ are described as follows:
| Instructions / Cycle | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| I1 | IF | ID | EX | MEM | WB | |
| I2 | IF | ID | EX | MEM | WB |
When the instruction tries to enter into the write back stage of the pipeline, at that time, all the previous instructions contained by the program have already passed through the read stage of register and read their input values. Now without causing any type of problem, the write instruction can write its destination register. The WAR instructions contain less problems as compared to the WAW because in WAR, before the write back stage of a pipeline, the read stage of a register occur.
WAW
WAW can be referred to as ‘Write after Write’. It is also known as Output Data dependency. If the later instruction tries to write on operand before earlier instruction writes it, in this case, the WAW hazards will occur. The condition to detect the WAW hazard is when On and On+1 both have a minimum one common operand.
For example:
The dependency is described as follows:
add R1, R2, R3 sub R1, R2, R4
Here addition instruction creates a WAW hazard because subtraction instruction writes on the same register. The hazard for instructions ‘add R1, R2, R3′ and ‘sub R1, R2, R4′ are described as follows:
| Instructions / Cycle | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| I1 | IF | ID | EX | MEM | MEM2 | MEM3 | WB |
| I2 | IF | ID | EX | MEM | WB |
In the write back stage of a pipeline, the output register of instruction will be written. The order in which the instruction with WAW hazard appears in the program, in the same order these instructions will be entered the write back stage of a pipeline. The result of these instructions will be written into the register in the right order. The processor has improved performance as compared to the original program because it allows instructions to execute in different orders.
Effects of WAR and WAW
The WAR hazards and WAW hazards occur because the process contains a finite number of registers. Because of this reason, these hazards are also known as the name dependencies.
The processor will use the different registers to generate the output of each instruction if it contains an infinite number of registers. There is no chance of occurring the WAR and WAW hazards in this case.
The WAR and WAW hazards will not cause the delay if a processor uses the same pipeline for all the instructions and executes these instructions in the same order in which they appear in the program. This is all because of the process of instructions flow through a pipeline.