Data Hazards
Introduction:
Data hazards occur when the pipeline changes the order of read/write accesses to operands so that the order differs from the order seen sequentially executing instructions on the pipelined machine. Also, data hazards occur if dependencies exist between any pair of instructions which are close enough in the pipeline to cause overlap. Dependencies on operands between instructions cause data hazards. If a pair of instructions shares the same register or memory location, there are data hazards. A data hazard arises if one operand is not yet available when needed by another instruction in the pipeline.
Data hazards are also known as data dependency. Data dependency is the condition in which the outcome of a previous instruction that has not been executed to completion because of the effect of the pipeline.
Data hazards arise because of the need to preserve the order of the execution of instructions.
Example:
    Add R2, R1, R0               [R2] <-- [R1] + [R0]
    Sub R1, R5, R6               [R1] <-- [R5] - [R6]
Data hazards are classified into three types:
  • RAW - Read After Write (also known as True Data Dependency)
  • WAW - Write After Write (also known as Output Dependency)
  • WAR - Write After Read (also known as Anti Data Dependency)
There are two instructions i and j. Instruction i begins execution before instruction j.
RAW (Read After Write):
RAW hazard is most common hazard that occurs when a read operation takes place after a write.
Instruction j tries to read a source operand before instruction i writes it. Thus, instruction j gets the old value.
Example:
    Add R1, R2, R3
    Sub R4, R1, R5
Sub instruction tries to read R1 (ID stage of Sub) before it is written by Add instruction (WB stage of Add). This hazard can be solved by data forwarding or stalling.
Add R1, R2, R3 IF ID EX MEM WB  
Sub R4, R1, R5    IF ID EX MEM WB
Data Forwarding:
The problem with data hazards, introduced by this sequence of instructions can be solved with a simple hardware technique called forwarding.
  1 2 3 4 5 6 7
ADD R1, R2, R3 IF ID EX MEM WB    
SUB R4, R5, R1   IF IDsub EX MEM WB  
AND R6, R1, R7     IF IDand EX MEM WB
The key insight in forwarding is that the result is not really needed by SUB until after the ADD actually produces it. The only problem is to make it available for SUB when it needs it.
If the result can be moved from where the ADD produces it (EX/MEM register), to where the SUB needs it (ALU input latch), then the need for a stall can be avoided.
Using this observation , forwarding works as follows:
  • The ALU result from the EX/MEM register is always fed back to the ALU input latches.
  • If the forwarding hardware detects that the previous ALU operation has written the register corresponding to the source for the current ALU operation, control logic selects the forwarded result as the ALU input rather than the value read from the register file.
Data Forwarding
Figure 2.2: Data Forwarding
Forwarding of results to the ALU requires the additional of three extra inputs on each ALU multiplexer and the addtion of three paths to the new inputs.
The paths correspond to a forwarding of:
(a) the ALU output at the end of EX,
(b) the ALU output at the end of MEM, and
(c) the memory output at the end of MEM.
Without forwarding our example will execute correctly with stalls:
  1 2 3 4 5 6 7 8 9
ADD R1, R2, R3 IF ID EX MEM WB        
SUB R4, R5, R1   IF stall stall IDsub EX MEM  WB  
AND R6, R1, R7     stall stall IF IDand EX MEM  WB
As our example shows, we need to forward results not only from the immediately previous instruction, but possibly from an instruction that started three cycles earlier. Forwarding can be arranged from MEM/WB latch to ALU input also.  Using those forwarding paths the code sequence can be executed without stalls:
  1 2 3 4 5 6 7
ADD R1, R2, R3 IF ID EXadd MEMadd WB    
SUB R4, R5, R1   IF ID EXsub MEM WB  
AND R6, R1, R7     IF ID EXand MEM WB
The first forwarding is for value of R1 from EXadd to EXsub .
The second forwarding is also for value of
R1 from MEMadd to EXand.

This code now can be executed without stalls.
Forwarding can be generalized to include passing the result directly to the functional unit that requires it: a result is forwarded from the output of one unit to the input of another, rather than just from the result of a unit to the input of the same unit.


WAW (Write After Write):
WAW hazard is the hazard that occurs when a write operation follows another write operation. This hazard is present only in pipelines that write in more than one pipe stage or allow an instruction to proceed even when a previous instruction is stalled.
The writes are performed in the wrong order.
Instruction j tries to write its result to a location before it has been written to by instruction i.
Example:
    Load R1, O(R2)
    Add R1, R2, R3
Load R1, O(R2) IF ID EX MEM1 MEM2 WB
Add R1, R2, R4   IF ID EX WB   
On the example, loads take two memory cycles and Add skip the memory cycle. Instruction j (Add) writes (WB stage of j) before instruction i writes (WB stage of i).
The WAW hazards can be avoided by doing following changes in the pipelining:

WAR (Write After Read):
WAR hazard is the hazard that occurs when write operation follows read operation.
Instruction j tries to write its result to a location before instruction i can read it as a source operand. The source operand is replaced before it can be read.
Example:
    Store R1, O(R2)
    Add R1, R2, R3

Store R1, O(R2) IF ID EX MEM1 MEM2 WB
Add R1, R2, R3   IF ID EX WB  
If the Store reads R2 during the second half of its MEM2 stage and the Add writes during first half of its WB stage, the Store will incorrectly read R2. Write by Add to R2 happens before the read to R2 by Store.
The WAR hazards can be avoided by internal forwarding, stalling, and pipelining scheduling. Also this kind of hazards can be avoided by modifying pipeline architecture such that consecutive Write and Read occur after few clock cycles.
Load R1, O(R2) IF ID EX MEM WB         
Sub R4, R1, R5   IF ID EX MEM WB   
 
And R6, R1, R7     IF ID EX MEM WB  
Or R8, R1, R9       IF ID EX MEM WB
  • Load instruction computes the effective address in EX stage and fetches the data in MEM stage.
  • R1 cannot be forworded until the end of the MEM stage, but Sub needs R1 at the beginning of its EX stage.
  • This hazards requires stall because R1 does not available until the end of MEM stage. The Sub instruction must stall prior to its EX stage.
  • With a stall, load instruction can forward R1 to Sub instruction on time.
  • Neither And nor Or instruction must be stalled because R1 value can be forwarded by Load to And or Or in their EX stages. However, since Sub stalls, And and Or must  stall.
Load R1, O(R2) IF ID EX MEM WB            
Sub R4, R1, R5   IF ID Stall EX  
 
 
  
And R6, R2, R7     IF Stall ID EX MEM WB   
Or R8, R1, R9       Stall IF ID EX MEM WB
Pipelining Scheduling:
Changing the order of instruction can eliminate stalls caused by data hazards.
  • Many instructions will use operand immediately after it has been loaded into a register. To eliminate stall, it can be done by moving a load further to the beginning of a set of code or instruction that uses the loaded value further to the end of a set of code.
  • Pipeline schduling try to use other instructions in the same blosk of code to fill in a stall by organizing instructions without dependencies in an interleaved maner.
Example:
Load R1, 0(R2) IF ID EX MEM WB            
Add R1, R3, R4   IF Stall ID EX MEM WB        
Load R5, 4(R2)          
IF ID EX MEM WB      
Add R5, R1, R5  
    
 
IF Stall ID EX MEM WB  
Store R5, 8(r2)  
       
  
  IF ID EX MEM WB
There are two stalls resulting from Load followed by using the loaded values. The code can be scheduled by moving independent instructions between the load and when it is needed.
Load R1, 0(R2) IF ID EX MEM WB        
Load R5, 4(R2)   IF ID EX MEM WB      
Add R1, R3, R4     IF ID EX MEM WB    
Add R5, R1, R5       IF ID EX MEM WB  
Store R5, 8(r2)         IF ID EX MEM WB
After scheduling the two stalls are eliminated.

Previous    Content       Next