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

Based on the results obtained above, we can compute the speed-up and the
throughput for executing the piece of code given in Example 3 as:

Time using sequential processing
Time using pipeline processing ¼

7 5

16 ¼

Speed-up S(5) ¼ 2 : 19

7
16 ¼

Throughput U(5) ¼ No of tasks executed per unit time ¼ 0 44

: :

The discussion on pipeline stall due to instruction and data dependencies should
reveal three main points about the problems associated with having such dependen-
cies. These are:

1. Both instruction and data dependencies lead to added delay in the pipeline.
2. Instruction dependency can lead to the fetching of the wrong instruction.
3. Data dependency can lead to the fetching of the wrong operand.

There exist a number of methods to deal with the problems resulting from instruction
and data dependencies. Some of these methods try to prevent the fetching of the
wrong instruction or the wrong operand while others try to reduce the delay incurred
in the pipeline due to the existence of instruction or data dependency. A number of
these methods are introduced below.

Methods Used to Prevent Fetching the Wrong
Instruction or Operand

Use of NOP (No Operation) This method can be used in order to prevent

the fetching of the wrong instruction, in case of instruction dependency, or
fetching the wrong operand, in case of data dependency. Recall Example 1. In
that example, the execution of a sequence of ten instructions I 1 -I 10 on a
pipeline consisting of four pipeline stages: IF, ID, IE, and IS were considered. In
order to show the execution of these instructions in the pipeline, we have assumed
that when the branch instruction is fetched, the pipeline stalls until the result of
executing the branch instruction is stored. This assumption was needed in order to
prevent fetching the wrong instruction after fetching the branch instruction. In
real-life situations, a mechanism is needed to guarantee fetching the appropriate
instruction at the appropriate time. Insertion of “NOP” instructions will help
carrying out this task. A “NOP” is an instruction that has no effect on the status
of the processor.

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

sisting of four pipeline stages: IF, ID, IE, and IS. Assume that instruction I 4 is a con-
ditional branch instruction and that when it is executed, the branch is not taken; that
is, the branch condition is not satisfied.