Handling Data Hazards

Handling Data Hazards

1. Operand Forwarding

• A simple hardware technique which can handle data hazard is called operand forwarding or register by passing.

• In this technique, ALU results are fed back as ALU inputs. When the forwarding logic detects the previous ALU operation has the operand for current instruction, it forwards ALU output instead of register file.

• This is illustrated in Fig. 3.11.1. Fig. 3.11.1 (a) shows a portion of the processor datapath involving the ALU and the register file.

• The source and result register constitute the interstage buffers needed for pipelined operation, as shown in Fig. 3.11.1 (b).

• The data forwarding mechanism is indicated by dashed lines.

• The two multiplexers select the data for ALU either from destination bus or from source 1 and source 2 registers.

• When the forwarding logic detects data dependency, it forwards ALU output available in the result register using data forwarding path to the ALU for the next operation. Hence the execution of next (dependent) instruction proceeds without interruption.

• Fig. 3.11.2 shows the hardware necessary to support forwarding for operations that use results during the EX stage.

• Compared to data path shown in Fig. 3.11.7, the multiplexers are added to provide inputs to the ALU along with the forwarding unit.

2. Handling Data Hazards in Software

• In this approach, software (compiler) detects the data dependencies. If data dependencies are found it introduces necessary delay between two instructions by inserting NOP (no‒operation) instructions as follows:

I₁ :  MUL R₂, R₃, R₄

NOP

NOP

ADD R₄, R₅, R₆

Disadvantages of adding NOP instructions

■ It leads to larger code size.

■ A given processor may have several hardware implementations. NOP instructions inserted to satisfy the requirements of one implementation may not be needed and hence would lead to reduce performance on a different implementation.

• To achieve better performance, the compilers are designed such that they can reorder instructions to perform useful task in the NOP slots.

Example: 1

Convert the following code segment in C to MIPS instructions, assuming all variables are in memory and are addressable as offsets from $t0 :

a = b+e ;

c = b+f ;

Solution :

lw $t1, 0($t0)

lw $t2, 4($t0)

add $t3, $t1,$t2

sw $t3, 12($t0)

lw $t4, 8($t0)

add $t5, $t1,$t4

sw $t5, 16($t0)

Example: 2

Find the hazards in the code segment of the previous example and reorder the instructions to avoid any pipeline stalls.

Solution:

Both add instructions have a hazard because of their respective dependence on the immediately preceding lw instruction. It is important to note that bypassing eliminates several other potential hazards, including the dependence of the first add on the first lw and any hazards for store instructions. Moving up the third lw instruction to become the third instruction eliminates both hazards:

lw $t1, 0($t0)

lw $t2, 4($t0)

lw $t4, 8($t0)

add $t3, $t1,$t2

sw $t3, 12($t0)

add $t5, $t1,$t4

sw $t5, 16($t0)

3. Side Effects

• When destination register of the current instruction is the source register of the next instruction there is a data dependency. Such data dependency is explicit and it is identified by register name. There are some instruction that change the contents of a register other than the one named as the destination. For example, instruction (stack instructions: push or pop) that uses an autoincrement or autodecrement addressing mode.

• In autoincrement or autodecrement addressing mode, the instruction changes the contents of a source register used to access one of its operands. In such cases, we need to check data dependencies for registers affected by an autoincrement or autodecrement operation along with the destination register.

• When a location other than one explicitly named in an instruction as a destination operand is affected, the instruction is said to have a side effect.

• Another possible side effect involves the condition code flags, which are used by instructions such as conditional branches and add‒with‒carry. Let us assume that, R₁ and R₂ holds a double‒precision integer number and R₃ and R₄ holds another double‒precision integer number.

• The addition of these two numbers may be accomplished as follows:

ADD R₁, R₃

ADD with Carry R₂, R₄

• Even though register names are different, the dependency (implicit) exists between these two instructions through the carry flag. This flag is Set/Reset by the first instruction and used in the second instruction, which performs the operation

R₄ ← [R₂] + [R₄] + Carry

Important Note

• Instructions that have side effects give rise to multiple data dependencies, which lead to a substantial increase in the complexity of the hardware or software needed to resolve them. For this reason, instructions designed for execution on pipelined hardware should have less side effects.

Example: 3

The following sequence of instructions are executed in the basic 5 ‒ stage pipelined processor.

or rl, r2, r3

or r2, rl, r4

or rl, rl, r2

a) Indicate dependences and their type.

b) Assume there is no forwarding in this pipelined processor. Indicate hazards and add NOP instructions to eliminate them.

c) Assume there is full forwarding. Indicate hazards and add NOP instructions to eliminate them.

Solution:

a) Dependences and their type

• Read After Write (RAW) dependency in rl between Instructions 1, 2 and 3.

• Read After Write (RAW) dependency in r2 between Instructions 2 and 3.

• Write After Read (WAR) in r2 from Instruction 1 to 2.

• Write After Read (WAR) in rl from Instruction 2 to 3.

• Write After Read (WAR) in rl from Instruction 1 to 3.

b) No hazards from write after read and write after write, since there are 5 stages. Read after writes cause data hazards.

or rl, r2, r3

NOP

NOP

or r2, r1, r4

NOP

NOP

or rl, rl, r2

c) In full forwarding the data hazards above are eliminated, thus there is no need for NOP instructions.

Review Questions

1. Describe the methods for dealing with data hazards.

2. Explain the ways and means of handling data hazard.

3. List the conditions to overcome data hazard.

4. What is a data hazard? How do you overcome it? And discuss its side effects.

5. Explain data hazard in detail.

6. Describe operand forwarding in a pipeline processor with a diagram.

7. Discuss the modified data path to accommodate pipelined executions with a diagram.