HAZARDS (Pipelining)

•   Hazards are problems with the instruction pipeline in CPU micro architecture that potentially result in incorrect  computation.

·              There are three types of hazards:

Ø  Data Hazard:

o   Occurs when instructions exhibit data dependence modify data in different stages of a pipeline.

o   There are three situations in which the data hazards can occur:

§  Read after write (RAW)-true dependency

§  Write after read (WAR)-anti-dependency

§  Write after write (WAW)-output dependency

o   RAW:

§  A situation where an instruction refers to a result that has not been yet calculated or retrieved

§  Occurs when an instruction is executed after a previous instruction has not yet been completely processed through the pipeline.

§  Eg:

ü  I1.R2<- R1+R3

ü  I2.R4<- R2+R3

ü  First instruction (i1)is calculating a value to be saved in register R2 and second instruction is going use that value to compute a result for register R4

ü  However, in pipeline, when we fetch the operand for the 2^nd operation, result from the first is not yet been saved and hence we have data dependency…

 

Diagram for data hazards…

o   WAR

§  Occur when instruction 2 tries to write destination before it is read by instruction 1.

§  Represent a problem with concurrent execution.

§  Eg:

ü  I1.R4 <- R1+R3

ü  I2.R3<- R1+R2

ü  If I2 is completed earlier than I1 ,ensure that do not store the result of register R3 befreI1 has had a chance to fetch an operand.

o   WAW

§  I2 tries to read write an operand before written by I1

§  May occur in concurrent execution environment

§  Eg:

ü  I1.R2<- R3+R4

ü  I2.R2<- R1+R2

ü  Delay the WB(Write Back) of I2 until the execution of I1…

o   There are 3 ways to handle the data hazards:

o   Software: insert independence instruction(or no-ops)

o   Hardware: insert bubbles (stall the pipeline)

                   :data forwarding

Diagram of handling data hazards through software…

Diagram of handling data hazards through hardware(insert bubbles/stall the pipeline)…

Note: Pipeline stall

          To insure proper pipeline execution in light of register dependences, we must:

1.      Detect the hazards

2.      Stall the pipeline:

--prevent IF (do not want to lose any instructions) and ID (can’t continue until the dependent instruction complete correctly) stages from making progress

=do not write the PC (PCWrite=0);

=do not rewrite IF/ID register (IF/IDWrite =0);

 --inserts “no-ops” into later stages

=set all control signals propagating to EX/MEM/WB=0;

Diagram of eliminating data hazards via forwarding with stalling pipeline after loading….

Note:

Data forwarding…

=forwarding handles 2 types of data hazards which are EX HAZARDS & MEM HAZARDS.

=The third type hazards (WB HAZARDS)is already handled by using a transparent reg file in which this reg file allow the write data to be forwarded to the output if the register file is asked to read and write the same register in the same cycle…

=Forwarding method only is NOT enough to eliminate all the data hazards therefore it must works with pipeline stall just like the diagram shown above.

Ø  Structural Hazards…

o   Occur when a part of processor’s hardware is needed by two or more instructions at the same time.

o   Eg:

o   A memory unit that is accessed both in the fetch stage where data is written and/or read from memory.

o   Can be resolved by :

o   Separating the component into orthogonal unit (eg: separate cache)

o   Bubbling the pipeline

Diagram of resolving structural hazards via bubbling the pipeline…

Ø  Control hazards (branch hazards)

o   Occurs with branches

o   Can cause greater performance lost than data hazards

o   When a branch is executed it may or may not change the PC (to other value than its value+4)

o   It is said taken branch if the branch is changing to its target address and vice versa…

o   If the instruction I is a taken branch, then the value will not change until the end of MEM stage of the instruction execution in the pipeline

o   A branch causes 3 cycle stall in processor pipeline:

=One cycle repeated IF (IF is redundant if branch is not taken)

=Two idle cycle

o   The three clock cycle lost for every branch is a significance loss and the machine with branch stall with 30% branch frequency   only achieve half of the speedup of pipelining

o   Reducing the branch penalty becomes critical…

o   To avoid the control hazards :

=insert pipeline bubble which guaranteed to increase latency

=use branch prediction and make educated guesses about which instruction to insert

Chong Cai Ning

B031210080