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

The figure shows that due to the extra time units needed for instruction I 2 to be
fetched, the pipeline stalls, that is, fetching of instruction I 3 and subsequent instruc-
tions are delayed. Such situations create what is known as pipeline bubble (or pipe-
line hazards). The creation of a pipeline bubble leads to wasted unit times, thus
leading to an overall increase in the number of time units needed to finish executing
a given number of instructions. The number of time units needed to execute the 10
instructions shown in Figure 9.3 is now 16 time units, compared to 13 time units if
there were no cache misses.
Pipeline hazards can take place for a number of other reasons. Among these are
instruction dependency and data dependency. These are explained below.

9.2.1. Pipeline “Stall” Due to Instruction Dependency

Correct operation of a pipeline requires that operation performed by a stage MUST
NOT depend on the operation(s) performed by other stage(s). Instruction depen-
dency refers to the case whereby fetching of an instruction depends on the results
of executing a previous instruction. Instruction dependency manifests itself in the
execution of a conditional branch instruction. Consider, for example, the case of a
“branch if negative” instruction. In this case, the next instruction to fetch will not
be known until the result of executing that “branch if negative” instruction is
known. In the following discussion, we will assume that the instruction following
a conditional branch instruction is not fetched until the result of executing the
branch instruction is known (stored). The following example shows the effect of
instruction dependency on a pipeline.

Example 1 Consider the execution of ten instructions I 1 -I 10 on a pipeline con-

sisting of four pipeline stages: IF (instruction fetch), ID (instruction decode), IE
(instruction execute), and IS (instruction results store). Assume that the instruction
I 4 is a conditional branch instruction and that when it is executed, the branch is
not taken, that is, the branch condition(s) is(are) not satisfied. Assume also that
when the branch instruction is fetched, the pipeline stalls until the result of executing
the branch instruction is stored. Show the succession of instructions in the pipeline;
that is, show the Gantt's chart. Figure 9.4 shows the required Gantt's chart. The
bubble created due to the pipeline stall is clearly shown in the figure.

I 2 I 10

I 1 I 3 I 4 I 5 I 6 I 7 I 8 I 9

IS
IE
ID
IF

I 1 I 2 I 3 I 4 I 5 I 6 I 7 I 8 I 9 I 10

I 2 I 10

I 1 I 3 I 4 I 5 I 6 I 7 I 8 I 9

I 1 I 2 I 5 I 6 I 7 I 8 I 9 I 10

I 3 I 4

123456789012 4 13 15 16

Figure 9.4 Instruction dependency effect on a pipeline