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

to complete m tasks.

Time using sequential processing
Time using pipeline processing ¼

m n t
(n þ m

Speed-up S(n) ¼

1) t

m n
n þ m

¼

1

Lim
m !1

S(n) ¼ n (i e , n-fold increase in speed is theoretically possible)

: :

2. Throughput U(n)

m
(n þ m

Throughput U(n) ¼ no of tasks executed per unit time ¼

:

1) t

Lim
m !1

U(n) ¼ 1 assuming that t ¼ 1 unit time

3. Efficiency E(n)

Efficiency E(n) ¼ Ratio of the actual speed-up to the maximum speed-up

Speed-up
n ¼

m
n þ m

¼

1

Lim
m !1

E(n) ¼ 1

9.2. INSTRUCTION PIPELINE

The simple analysis made in Section 9.1 ignores an important aspect that can affect
the performance of a pipeline, that is, pipeline stall. A pipeline operation is said to
have been stalled if one unit (stage) requires more time to perform its function, thus
forcing other stages to become idle. Consider, for example, the case of an instruction
fetch that incurs a cache miss. Assume also that a cache miss requires three extra
time units. Figure 9.3 illustrates the effect of having instruction I 2 incurring a
cache miss (assuming the execution of ten instructions I 1 to I 10 ).

U 4
U 3
U 2
U 1

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

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 3 I 4 I 5 I 6 I 7 I 8 I 9 I 10

123456789012 4 13 15 16

Figure 9.3 Effect of a cache miss on the pipeline