Pipelining Design Techniques - Fundamentals of Computer Organization and Architecture - page 189

9.2.2. Pipeline “Stall” Due to Data Dependency

Data dependency in a pipeline occurs when a source operand of instruction
I i depends on the results of executing a preceding instruction, I j , i . j. It should
be noted that although instruction I i can be fetched, its operand(s) may not be avail-
able until the results of instruction I j are stored. The following example shows the
effect of data dependency on a pipeline.

Example 2

Consider the execution of the following piece of code:

ADD

R 1 , R 2 , R 3 ; R 3 R 1 þ R 2

SL R 3 ; R 3 SL(R 3 )

SUB R 5 , R 6 , R 4 ; R 4 R 5 2 R 6

†

In this piece of code, the first instruction, call it I i , adds the contents of two registers
R 1 and R 2 and stores the result in register R 3 . The second instruction, call it I i þ 1 ,
shifts the contents of R 3 one bit position to the left and stores the result back
into R 3 . The third instruction, call it I i þ 2 , stores the result of subtracting the content
of R 6 from the content of R 5 in register R 4 . In order to show the effect of such data
dependency, we will assume that the pipeline consists of five stages, IF, ID, OF, IE,
and IS. In this case, the OF stage represents the operand fetch stage. The functions of
the remaining four stages remain the same as explained before. Figure 9.5 shows the
Gantt's chart for this piece of code. As shown in the figure, although instruction I i þ 1
has been successfully decoded during time unit k þ

2, this instruction cannot pro-

ceed to the OF unit during time unit k þ 3. This is because the operand to be fetched

by I i þ 1 during time unit k þ 3 should be the content of register R 3 , which has been

modified by execution of instruction I i . However, the modified value of R 3 will
not be available until the end of time unit k þ 4. This will require instruction I i þ 1

to wait (at the output of the ID unit) until k þ

5. Notice that instruction I i þ 2 will

I i +1

IS

I i I i +2

IE

I i I i +1 I i +2

OF

I i I i +1 I i +2

I i I i +1 I i +2

ID

I i I i +1 I i +2

IF

kk + 1 k + 2 k + 3 k + 4 k + 5 k + 6 Time

Figure 9.5 The write-after-write data dependency