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

I 1 I 2

I 3

I 3

IS
IE
OF
ID
IF

NOP NOP
NOP NOP

I 1 I 2

I 1 I 2

I 3

I 3

NOP NOP
NOP NOP

I 1 I 2

I 1 I 2 I 3

NOP NOP

1234567890

Figure 9.9 Use of NOP in data dependency

I 2 will fetch the correct value of R 3 . This is the value stored as a result of executing
instruction I 1 during time unit #5.

Methods Used to Reduce Pipeline Stall Due to
Instruction Dependency

Unconditional Branch Instructions In order to be able to reduce the pipeline

stall due to unconditional branches, it is necessary to identify the unconditional
branches as early as possible and before fetching the wrong instruction. It may
also be possible to reduce the stall by reordering the instruction sequence. These
methods are explained below.

REORDERING OF INSTRUCTIONS In this case, the sequence of instructions are reor-
dered such that correct instructions are brought to the pipeline while guaranteeing
the correctness of the final results produced by the reordered set of instructions. Con-
sider, for example, the execution of the following group of instructions I 1 , I 2 , I 3 , I 4 ,
I 5 . , . , I j , I j þ 1 , . , . on a pipeline consisting of three pipeline stages: IF, IE, and IS. In this
group of instructions, I 4 is an unconditional branch instruction whereby the
target instruction is I j . Execution of this group of instructions in the same
sequence as given will lead to the incorrect fetching of instruction I 5 after fetching
instruction I 4 . However, consider execution of the reordered sequence I 1 , I 4 , I 2 , I 3 ,
I 5 . , . , I j , I j þ 1 , . , . . Execution of this reordered sequence using the three-stage pipeline
is shown in Figure 9.10.
The figure shows that the reordering of the instructions causes instruction I j to be
fetched during time unit #5, that is, after instruction I 4 has been executed. Reorder-
ing of instructions can be done using a “smart” compiler that can scan the sequence
of code and decide on the appropriate reordering of instructions that will lead to

I 1 I 4 I 2 I 3 I j I j +1

IS
IE
IF

I 1 I 4 I 2 I 3 I j I j +1

I 1 I 4 I 2 I 3 I j I j +1

1234567

Figure 9.10 Instruction reordering