Pipeline Hazards Part 1
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Pipeline Hazards Part 1 as PDF for free.
More details
- Words: 1,088
- Pages: 5
CS-421 Parallel Processing Handout_6.1
BE (CIS) Batch 2004-05
Pipeline Hazards (Part- I) A pipeline hazard is a situation that prevents an instruction from using a pipeline stage during the designated clock cycle. By designated we mean the cycle in which the instruction could have used the stage, had there been no hazard. There are three types of pipeline hazards: 1. Structural Hazard 2. Data Hazard 3. Control Hazard 1. Structural Hazard –
Arises due to resource conflict
–
Two examples have already been encountered: i. Harvard memory architecture ii. what brought about passage of all instructions through all the pipeline stages in the same order (review the resource conflict in CC5 between lw and add instructions mentioned in the Handout_5.1) iii. We shall see one more example in the discussion on data hazards below.
–
These hazards are typically averted employing replicated resources.
2. Data Hazard –
Arises due to data dependency between instructions
–
As an example consider the following sequence of instructions
Page - 1 - of 5
CS-421 Parallel Processing Handout_6.1
–
BE (CIS) Batch 2004-05
Clearly, there are a number of data dependencies between various pair of instructions as detailed below: One source register $2 of instruction and is the destination register of its
o
predecessor instruction sub. In order to maintain the correctness of program the and instruction must use the value of $2 written by sub instruction. However, sub writes register $2 in CC5 while the and instruction reads it in CC3. Thus, it
reads an incorrect old value. Unless rectified, this is a potential threat for the correctness of the program. o
Similar data hazard exists between sub and or instructions.
o
An interesting observation is to be made regarding the kind of data dependency between sub and add instructions. In its original form, it does represent a data hazard. However, the clocking methodology employed averts this data hazard. The clocking methodology used by MIPS writes a state element in the first half of clock cycle and reads it in the next half. Hence, writing of $2 by sub happens in the first half of CC5 and its reading by add occurs in latter half of CC5. Thus, the add instruction reads the intended value of $2 register.
In addition to avoiding the data hazard, the clocking methodology also prevents the
o
structural hazard between sub and add instructions as they access the same resource i.e. the register file in the same clock cycle. The data dependency between sub and sw instructions is NOT a data hazard (as
o
far as the execution remains in-order) for obvious reason. All the data hazards that were described above are regarded as Read-After-Write
o
(RAW) hazards. Remedy •
The remedy we describe is based on when the data is produced and when it is actually consumed.
•
For instance, in the above sequence of instructions, i.
The sub instruction produces its result (to be written in $2) in its EX stage in the CC3
ii. The and & or instructions need this value in CC4 and CC5 respectively. •
Thus forwarding the value generated in CC3 by sub instruction to the ALU input 1 in CC4 to be consumed by the and instruction obviates the RAW hazard between these two instructions.
•
Similarly, forwarding the value generated in CC3 by sub instruction to the ALU input 2 in CC5 to be consumed by the or instruction obviates the RAW hazard between these two instructions. Page - 2 - of 5
CS-421 Parallel Processing Handout_6.1
•
BE (CIS) Batch 2004-05
Essentially we need to forward the ALU output from sub directly to the and and or instructions, without going through the register file (i.e. bypassing the register file).
•
Where to find the ALU result?
The ALU result generated in the EX stage is passed through the pipeline registers to the MEM and WB stages, before it is finally written to the register file.
Since the pipeline registers already contain the ALU result, we could just forward that value to subsequent instructions, to prevent data hazards.
In CC4, the and instruction can get the value $1 - $3 from the EX/MEM pipeline register used by sub.
Then in cycle 5, the or can get that same result from the MEM/WB pipeline register being used by sub.
•
A forwarding unit selects the correct ALU inputs for the EX stage.
If there is no hazard, the ALU’s operands will come from the register file, just like before.
If there is a hazard, the operands will come from either the EX/MEM or MEM/WB pipeline registers instead.
The ALU sources will be selected by two new multiplexers, with control signals named ForwardA and ForwardB.
Detecting Data Hazards How can the hardware determine if a hazard exists? EX hazard An EX hazard occurs between the instruction currently in its EX stage and the previous instruction if: Page - 3 - of 5
CS-421 Parallel Processing Handout_6.1
BE (CIS) Batch 2004-05
1. The previous instruction will write to the register file, and 2. The destination is one of the ALU source registers in the EX stage.
The first ALU source comes from the pipeline register when necessary. if (EX/MEM.RegWrite = 1 and EX/MEM.RegisterRd = ID/EX.RegisterRs) then ForwardA = 10
The second ALU source is similar. if (EX/MEM.RegWrite = 1 and EX/MEM.RegisterRd = ID/EX.RegisterRt) then ForwardB = 10
MEM hazard A MEM hazard may occur between an instruction in the EX stage and the instruction from two cycles ago. One new problem is if a register is updated twice in a row. add $1, $2, $3 add $1, $1, $4 sub $5, $5, $1 Register $1 is written by both of the previous instructions, but only the most recent result (from the second ADD) should be forwarded.
Here is an equation for detecting and handling MEM hazard for the first ALU source. if (MEM/WB.RegWrite = 1 and MEM/WB.RegisterRd = ID/EX.RegisterRs and (EX/MEM.RegisterRd != ID/EX.RegisterRs or EX/MEM.RegWrite = 0) then ForwardA = 01 The second ALU operand is handled similarly. if (MEM/WB.RegWrite = 1 and MEM/WB.RegisterRd = ID/EX.RegisterRt and (EX/MEM.RegisterRd ! ID/EX.RegisterRt or EX/MEM.RegWrite = 0) then ForwardB = 01 Page - 4 - of 5
CS-421 Parallel Processing Handout_6.1
BE (CIS) Batch 2004-05
The technique just described to combat data hazards is called data forwarding or bypassing (as we bypass register file when supplying data to the following instruction).
Simplified Pipelined Datapath highlighting Forwarding Unit
*****
Page - 5 - of 5
BE (CIS) Batch 2004-05
Pipeline Hazards (Part- I) A pipeline hazard is a situation that prevents an instruction from using a pipeline stage during the designated clock cycle. By designated we mean the cycle in which the instruction could have used the stage, had there been no hazard. There are three types of pipeline hazards: 1. Structural Hazard 2. Data Hazard 3. Control Hazard 1. Structural Hazard –
Arises due to resource conflict
–
Two examples have already been encountered: i. Harvard memory architecture ii. what brought about passage of all instructions through all the pipeline stages in the same order (review the resource conflict in CC5 between lw and add instructions mentioned in the Handout_5.1) iii. We shall see one more example in the discussion on data hazards below.
–
These hazards are typically averted employing replicated resources.
2. Data Hazard –
Arises due to data dependency between instructions
–
As an example consider the following sequence of instructions
Page - 1 - of 5
CS-421 Parallel Processing Handout_6.1
–
BE (CIS) Batch 2004-05
Clearly, there are a number of data dependencies between various pair of instructions as detailed below: One source register $2 of instruction and is the destination register of its
o
predecessor instruction sub. In order to maintain the correctness of program the and instruction must use the value of $2 written by sub instruction. However, sub writes register $2 in CC5 while the and instruction reads it in CC3. Thus, it
reads an incorrect old value. Unless rectified, this is a potential threat for the correctness of the program. o
Similar data hazard exists between sub and or instructions.
o
An interesting observation is to be made regarding the kind of data dependency between sub and add instructions. In its original form, it does represent a data hazard. However, the clocking methodology employed averts this data hazard. The clocking methodology used by MIPS writes a state element in the first half of clock cycle and reads it in the next half. Hence, writing of $2 by sub happens in the first half of CC5 and its reading by add occurs in latter half of CC5. Thus, the add instruction reads the intended value of $2 register.
In addition to avoiding the data hazard, the clocking methodology also prevents the
o
structural hazard between sub and add instructions as they access the same resource i.e. the register file in the same clock cycle. The data dependency between sub and sw instructions is NOT a data hazard (as
o
far as the execution remains in-order) for obvious reason. All the data hazards that were described above are regarded as Read-After-Write
o
(RAW) hazards. Remedy •
The remedy we describe is based on when the data is produced and when it is actually consumed.
•
For instance, in the above sequence of instructions, i.
The sub instruction produces its result (to be written in $2) in its EX stage in the CC3
ii. The and & or instructions need this value in CC4 and CC5 respectively. •
Thus forwarding the value generated in CC3 by sub instruction to the ALU input 1 in CC4 to be consumed by the and instruction obviates the RAW hazard between these two instructions.
•
Similarly, forwarding the value generated in CC3 by sub instruction to the ALU input 2 in CC5 to be consumed by the or instruction obviates the RAW hazard between these two instructions. Page - 2 - of 5
CS-421 Parallel Processing Handout_6.1
•
BE (CIS) Batch 2004-05
Essentially we need to forward the ALU output from sub directly to the and and or instructions, without going through the register file (i.e. bypassing the register file).
•
Where to find the ALU result?
The ALU result generated in the EX stage is passed through the pipeline registers to the MEM and WB stages, before it is finally written to the register file.
Since the pipeline registers already contain the ALU result, we could just forward that value to subsequent instructions, to prevent data hazards.
In CC4, the and instruction can get the value $1 - $3 from the EX/MEM pipeline register used by sub.
Then in cycle 5, the or can get that same result from the MEM/WB pipeline register being used by sub.
•
A forwarding unit selects the correct ALU inputs for the EX stage.
If there is no hazard, the ALU’s operands will come from the register file, just like before.
If there is a hazard, the operands will come from either the EX/MEM or MEM/WB pipeline registers instead.
The ALU sources will be selected by two new multiplexers, with control signals named ForwardA and ForwardB.
Detecting Data Hazards How can the hardware determine if a hazard exists? EX hazard An EX hazard occurs between the instruction currently in its EX stage and the previous instruction if: Page - 3 - of 5
CS-421 Parallel Processing Handout_6.1
BE (CIS) Batch 2004-05
1. The previous instruction will write to the register file, and 2. The destination is one of the ALU source registers in the EX stage.
The first ALU source comes from the pipeline register when necessary. if (EX/MEM.RegWrite = 1 and EX/MEM.RegisterRd = ID/EX.RegisterRs) then ForwardA = 10
The second ALU source is similar. if (EX/MEM.RegWrite = 1 and EX/MEM.RegisterRd = ID/EX.RegisterRt) then ForwardB = 10
MEM hazard A MEM hazard may occur between an instruction in the EX stage and the instruction from two cycles ago. One new problem is if a register is updated twice in a row. add $1, $2, $3 add $1, $1, $4 sub $5, $5, $1 Register $1 is written by both of the previous instructions, but only the most recent result (from the second ADD) should be forwarded.
Here is an equation for detecting and handling MEM hazard for the first ALU source. if (MEM/WB.RegWrite = 1 and MEM/WB.RegisterRd = ID/EX.RegisterRs and (EX/MEM.RegisterRd != ID/EX.RegisterRs or EX/MEM.RegWrite = 0) then ForwardA = 01 The second ALU operand is handled similarly. if (MEM/WB.RegWrite = 1 and MEM/WB.RegisterRd = ID/EX.RegisterRt and (EX/MEM.RegisterRd ! ID/EX.RegisterRt or EX/MEM.RegWrite = 0) then ForwardB = 01 Page - 4 - of 5
CS-421 Parallel Processing Handout_6.1
BE (CIS) Batch 2004-05
The technique just described to combat data hazards is called data forwarding or bypassing (as we bypass register file when supplying data to the following instruction).
Simplified Pipelined Datapath highlighting Forwarding Unit
*****
Page - 5 - of 5
Related Documents
Pipeline Hazards Part 1
June 2020 4
Pipeline Hazards Part 2
June 2020 1
Pipeline
May 2020 70
Natural Hazards 1
May 2020 0
Everyday Hazards
May 2020 14