Hazards in pipelining

Our target in pipelining is to get CPI=1. However, achieving the CPI target is not accessible due to some problems with pipelining. These problems are called Hazards in pipelining. Hazard leads to delay, for which we cannot get CPI=1.

Types of Hazards in Pipelining

The following are the primary hazards in pipelining. 

1. Data Hazards
2. Structural Hazards
3. Control Hazards

1. Data Hazards

The Data hazards occur when one instruction depends on a data value produced by a preceding instruction still in the pipeline.

Types of Data Hazards

Following are the three types of data hazards in pipelining.

I. Read After Write (RAW), a true dependency
II. Write After Read (WAR), an anti-dependency
III. Write After Write (WAW), an output dependency

Let’s explain all these hazards in detail

I. Read-After-Write (RAW) Hazards

A Read-After-Write hazard occurs when an instruction needs the result of some issued instruction, but that instruction is still uncompleted. In the following example of RAW, the second instruction requires the result of R3 to ADD with R4, But the first instruction still needs to produce it..

RAW Example

I1     R3 = R1 + R2 
I2     R5 = R3 + R4

 Five-stage (fetch, decode, execute, memory, feedback) pipelining produces the following result.

How to recognize RAW Hazards

I1 (Range) = R3
I2 (Domain) = R3, R4
I1 (Range) ∩ I2 (Domain) ≠ Ø

II. Write-After-Read (WAR) Hazards

It always reads the correct data. A WAR hazard occurs when an instruction attempts to write to a register before a previously used instruction has read it.  

This problem only occurs sometimes in normal pipelining. It occurs in special cases where the data is written before the read operation.

• Auto-increment/auto-decrement mode, where the register value is incremented/ decremented before fetching the next instruction.
• If both are parallel instructions or one instruction is delayed and the second executed first.

WAR Example

Inst I1   R1 = R2 x R3 
Inst I1   R2 = R4 + R5 
 

How to Recognize WAR Hazards?

Domain (I1) ∩ Range (I2) ≠ Ø

III. Write-After-Write (WAW) Hazards

A WAW hazard occurs when an instruction requires writing its result into the same register as a previously used instruction. In the following example of WAW, both instructions write their results to R3.

WAW Example

Inst I1     R3 = R1 * R2 
Inst I2     R3 = R4 + R5

In a five-stage pipelining, the result should be the following way.

How to Recognize WAW Hazards?

I1 (Range) = R3
I2 (Range) = R3
I1 (Range) ∩ I2 (Range) ≠ Ø

Note: RAR(READ AFTER READ ) is not a hazard.

2. Structural Hazard

Structural Hazard occurs when multiple instructions need the same resource. For example, when various instructions are fetching and writing the data to the main memory simultaneously, it causes a structural hazard.  Memory, cache, registers, Alu, and Common bus may be resources.

Example of Structural Hazard

Suppose the pipelining executes the following four instructions.

Conflict miss may be in the following cases.

• At the clock, pulse 4, instruction number 1, and instruction number 4 are using the same resource, which is main memory (For memory fetching)
• At the clock, pulse 5, instruction number 1, and instruction number 4 are using the same resource, which is registers (for decoding and writing back)

Explanation of structural hazards

Structural Hazard happens due to conflict miss. If the number of resources is limited and the number of instructions increases, then conflict miss will occur. For example, a conflict miss will occur if there are 20 resources and 100 instructions. We can never equalize resources and instructions because resources are too costly. In this way, the system will become too expensive.

Real-life example of Structural Hazards

 If there are 500 students in the student block, there may be 20 to 30 washrooms. Washrooms are always different from the number of students. So, two students cannot use the same washroom simultaneously, which will cause a conflict.

Structural Hazards (Conflict miss) Removal Methods

Conflict miss can be removed through the following methods.

• Creating stall (CPI=1 can’t be achieved through this method)
• By Resource Duplicate (Cost increase)
• Through Resource Pipelining (Complexity increase)
• Using Resource renaming

3. Control Hazard

Control hazards are Occur Due to branches.

Explanation of control hazard

• When we fetch the instruction (before going to the decode stage), the Program counter is incremented by 1.
• At the time of the decode stage, we know the operand (whether it is a branch or not).
• Through the execution stage of ongoing instruction, ALU tells us whether or not the branching is successful. Because ALU compares the branch with zero, if it is zero, then there will be no branching. If it is not equal to zero, then successful branchings occur.
• At the time of the write-back of ongoing instructions, we can change the PC’s value to the branch’s given address.

Suppose the 2nd instruction uses branch instruction as in the following diagram.

In this way, some stages of instructions 3, 4, and 5 are executed in the pipeline, but we get the branch’s address in the program counter after the 6-clock cycle. So, from the 7-clock cycle, the given address in the branch is executed.

All unsuccessful instructions (3, 4, 5) are flushed. It is problematic for CPI. Performance is decreased. So, control Hazard is the most problematic for system performance.

At the time of the 6th clock cycle, the Program counter gets the branch address, and from the 7th clock cycle, the given address in the branch is executed.

Solutions:

• We create stalls for branches that cause problems with system performance and never get CPI=1.
• If we have powerful circuits that detect branches when decoding or executing, then we stop the next instructions by creating stalls to minimize the control hazard effects.

Tip 01: The clock cycle or clock pulse is the same thing. The clock rate is the time to complete the clock cycle. Sometimes, the clock rate is given in Hz terms, which are frequencies we can calculate time through the (1/frequency) formula.

Tip 02: How to read: At second instruction, reading way à = (Read, after Write)

Tip 03: To recognize the type of Data Hazard, Consider Read (R) = Range