Hazards in pipelining
As our target in pipelining is to get CPI=1. But there are some problems with pipelining due to which CPI target does not achieved. These problems are called Hazards. Hazard leads towards delay due to which we cannot get CPI=1.
Types of 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, which will be produced by a preceding instruction which is still in the pipeline
Data hazards are of three types
I. Read After Write (RAW), a true dependency II. Write After Read (WAR), an anti-dependency III. Write After Write (WAW), an output dependency
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 till uncompleted. In the following example of RAW, the second instruction requires the result of R3 to ADD with R4 But it has not yet been produced by the first instruction.
I1 R3 = R1 + R2
I2 R5 = R3 + R4
In a five stage (fetch, decode, execute, memory, feedback) pipelining the result should the following g way
How to recognize RAW Hazards
I1 (Range) = R3 I2 (Domain) = R3, R4 I1 (Range) ∩ I2 (Domain) ≠ Ø
II. Write-After-Read (WAR) Hazards
It always read the correct data. A WAR hazard occurs when an instruction needs to write to a register which is not still been read by a previously used instruction.
This problem does not occur generally in normal pipelining. It occurs in special cases where the data is writing before the read operation
- e. auto-increment/auto-decrement mode where the register value is incremented/ decremented before to fetch the next instruction.
- If both are parallel instruction or one instruction is delayed and the second executed first.
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.
Inst I1 R3 = R1 * R2
Inst I2 R3 = R4 + R5
In a five stage pipelining the result should the following g 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, the case when multiple instructions are fetching and writing the data to the main memory at a time cause the structural hazard. Resources may be Memory, cache, registers, Alu, Common bus.
Suppose there are four instructions which are executing in the pipelining
Conflict miss may be in the following cases
- At clock pulse 4, instruction 1 and instruction 4 are using the same resource which is main memory (For memory fetching)
- At clock pulse 5, instruction 1 and instruction 4 are using the same resource which is registers (for decoding and write back)
Structural Hazard happens due to conflict miss. If no of resources are limited and higher the no of instructions then conflict miss will occur. For example, if 20 resources and 100 instructions then conflict miss will occur. We can never equalize resources and instructions because resources are too costly. In this way, system will become too costly.
If there are 500 students in the block then there may be 20 to 30 washrooms. Washrooms never are equal to no. of students. So, two students cannot use the same washroom at the same time due to which conflict miss will occur.
Structural Hazard (Conflict miss) can be removed through
- Creating stall (CPI=1 can’t be achieve 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.
- When we fetch the instruction (before to go to decode stage) Program counter is incremented by 1.
- At the time of decode stage, we have knowledge about operand (weather it is a Branch or not).
- Through the execution stage of on-going instruction, ALU tells us about successful branching or not. 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 on-going instruction we can change the value of PC to the given address of the branch.
Let suppose the 2nd instruction use branch instruction as in the following diagram.
In this way, some stages of instruction 3, 4, 5 are executed in the pipeline but we get the address of the branch in the program counter after 6 clock cycle. So from 7 clock cycle the given address in the branch is executed.
All unsuccessful instruction (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 Program counter get the branch address and from 7th clock cycle given address in the branch is executed.
- We create stall for branches that cause problems for system performance and never get CPI=1.
- If we have powerful circuits that detect branch at the time of decode or at the time of executing then we stop the next instructions by creating stalls to minimize the control hazard effects.
Tip 01: Clock cycle or clock pulse is a same thing. And clock rate is the time to compete the clock cycle. Sometimes clock rate is given in Hz terms which are frequency we can calculate time through (1/frequency) formula.
Tip 02: How to read: At second instruction reading way à = (Read, after Write)
Tip03: To recognize the type of Data Hazard Consider Read (R) = Range