Hazards in Pipelining:

Introduction:

     Pipelining can efficiently increase the performance of a processor by overlapping execution of instructions. But the efficiency of the pipelining depends upon, how the problem encountered during the implementation of pipelining is handled. These problems are known as HAZARDS. 

Types of Hazards: 

a)  Structural Hazards (Resource Bound)
b)  Control Hazards ( Pipelining Bubbles)
c)  Data Hazards ( Data dependencies)

Structural Hazards:
During the pipelining, the overlapped execution of instructions requires pipelining of functional units and duplication of resources to allow all possible combinations of instructions in the pipeline.This type of hazards occurs when two activities require the same resource simultaneously. 

Example:
 If machine has shared a single-memory pipeline for data and instructions. As a result,when an instruction contains a data-memory reference (load-MEM), it will conflict with the instruction reference for a later instruction (instr 3-IF):
   

                            Clock cycle number 

Instr        1       2       3       4           5          6        7         8   

Load       IF    ID   EX   MEM*  WB         

Instr 1             IF   ID      EX       MEM   WB         

Instr2                     IF      ID         EX       MEM  WB    

Instr 3                              IF*       ID         EX      MEM  WB  

 To resolve this, we stall the pipeline for one clock cycle when a data-memory access occurs. The effect of the stall is actually to occupy the resources for that instruction slot. The following table shows how the stalls are actually implemented. 
 

Clock cycle number 

Instr    1  2 3 4  5 6 7 8 9  

Load  IF ID  EX MEM WB        

Instr1       IF ID   EX     MEM WB      

Instr 2           IF   ID       EX     MEM  WB       

Instr 3        stall     IF      ID      EX       MEM W B  

 

Instruction 1 assumed not to be data-memory reference (load or store), otherwise Instruction 3 cannot start execution because of structural hazard.
 We know that introduction of stall reduces the performance of the system but there are following reasons for allowing structural hazard while designing the system:
To reduce cost: For example, machines that support both an instruction and a
cache access every cycle (to prevent the structural hazard of the above example)
require at least twice as much total memory.

A classical way to avoid  hazard at memory access is by providing separate data and instruction cache

Control Hazard:
     This type of hazard is caused by uncertainty of execution path, branch taken or
not taken.It results when we branch to a new location in the program, invalidating
everything we have loaded in our pipeline. They arises from the pipelining of branches and other instruction that change the content of PC (program counter). If a branch instruction enters in the pipeline , the performance would be hampered. 

  CLK        0     1      2      3         4       5       6     7     8     9     10     11     12

 I1             IF    ID    EX    W  

 I2                     IF    ID     EX    W

 I3                             IF     ID      EX     W 

 I4                                      IF       ID      EX    W 

                                         overlapped execution without branching

I1              IF    ID     EX    W

I2                      IF      ID     EX    W 

I3                                                      IF  ID      EX    W

I4                                                             IF     ID      EX    W 

                                         overlapped execution with branching

Data Hazards:

￿  Data hazards occur when the pipeline changes the order of read/write accesses to operands so that the order differs from the order seen by sequentially executing instructions on the unpipelined machine.
￿  Data hazards are also known as data dependency. Data dependency is the condition in which the outcome of the current operation is dependent on the outcome of a previous instruction that has not yet 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.
The following example shows the data hazards: 
          Add R2, R1, R0           [R2]     [R1] + [R0]
             
          Sub R1, R5, R6            [R4]     [R5] – [R6] 

Data hazards are classified into three types:

1.  RAW-  Read After Write      (also known as True Data Dependency)
2.  WAW- Write After Write      (also known as Output Dependency)
3.  WAR – Write After Read      (also known as Anti Data Dependency)

￿  RAW hazard is most common hazard that occurs when a read operation takes place after a write. The following example shows the possible RAW hazards: 

             Add  t1, A, B
        
             Sub   t2, t1, C

Solution: Internal forwarding (this can be used for all types of Data hazards) 

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. 
￿   This following example shows the possible WAW hazard:

                        Add  t1, A, B
         
                        Sub  t1, C,  D

Solution: The WAW hazards can be avoided by doing following changes in the pipelining:

                 -  Move write back for an ALU operation into the MEM stage , since                           ..                   the data value is available be then.    

                 -  By assuming that the data memory access takes place in 2 pipelining     .            ..                   stages. 
 
￿  WAR hazard is the hazard that occurs when write operation follows read operation.
This following example shows the possible WAR hazard:

                       Add   R1, R2, R3


                       Sub    R2, R2, R5

Solution: The WAR hazard can be avoided by internal forwarding and by modifying pipeline architecture such that consecutive Write and Read occur after few clock  cycles