Handling Data Hazards
AU:
Dec.-08, 11, 12, May-14,17,18
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. 7.10.1. Fig.
7.10.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. 7.10.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. 7.10.2 shows the hardware
necessary to support forwarding for operations that use results during the EX
stage.
• Compared to data path shown in Fig.
7.10.7, the multiplexers are added to provide inputs to the ALU along with the
forwarding unit.
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 :
I1 :MUL R2, R3, R4
NOP
NOP
ADD R4, R5, R6
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 7.10.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; AU May-19, Marks 2
Solution :
lw $t1, 0($t0)
lw $t2, 4($t0)
add $t3, $t1,$t2
sw $t3, 12($t0)
lw $t4, 8($10)
add $t5, $t1,$t4
sw $t5, 16($t0)
Example 7.10.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($10)
lw $t4, 8($t0)
add $t3, $t1,$t2
sw $t3, 12($t0)
add $t5, $t1,$t4
sw $t5, 16($t0)
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, R1and R2
holds a double-precision integer number and R3 and R4
holds another double-precision integer number.
• The addition of these two numbers may
be accomplished as follows:
ADD R1, R3
ADD with Carry R2, R4
• 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
R4← [R2]+[R4]+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 7.10.3
The following sequence of instructions are executed in the basic 5-stage
pipelined processor.
or r1, r2, r3
or r2, r1, r4
or r1, r1, 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. AU: May-18,
Marks 15
Solution: a) Dependences and their type
• Read After Write (RAW) dependency in
r1 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 r1 from
Instruction 2 to 3.
• Write After Read (WAR) in r1 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 r1, r2, r3
NOP
NOP
or r2, r1, r4
NOP
NOP
or r1, r1, 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. AU: Dec.-08, Marks 2, Dec.-12, Marks 16
4. What is a data hazard? How do you
overcome it? And discuss its side effects. AU: Dec.-11, Marks 16
5. Explain data hazard in detail. AU May-14, Marks
16
6. Describe operand forwarding in a
pipeline processor with a diagram. AU: May-17, Marks 6
7. Discuss the modified data path to
accommodate pipelined executions with a diagram. AU May-17, Marks 13