Information Technology Reference
In-Depth Information
I
1
I
2
I
3
F1 D1 E1 W1
F2 D2 E2 W2
F3 D3 E3 W3
(
a
) Sequential Processing
I
1
F1 D1 E1 W1
I
2
I
3
F2 D2 E2 W2
F3
123456789012
D3 E3 W3
Time
(
b
) Pipelining
Figure 9.1 Pipelining versus sequential processing
It is clear from the figure that the total time required to process three instruc-
tions (I
1
, I
2
, I
3
) is only six time units if four-stage pipelining is used as compared
to 12 time units if sequential processing is used. A possible saving of up to 50%
in the execution time of these three instructions is obtained. In order to formulate
some performance measures for the goodness of a pipeline in processing a series of
tasks, a space time chart (called the Gantt's chart) is used. The chart shows the suc-
cession of the subtasks in the pipe with respect to time. Figure 9.2 shows a Gantt's
chart. In this chart, the vertical axis represents the subunits (four in this case) and
the horizontal axis represents time (measured in terms of the time unit required
for each unit to perform its task). In developing the Gantt's chart, we assume
that the time (T) taken by each subunit to perform its task is the same; we call
this the unit time.
As can be seen from the figure, 13 time units are needed to finish executing 10
instructions (I
1
to I
10
). This is to be compared to 40 time units if sequential proces-
sing is used (ten instructions each requiring four time units).
In the following analysis, we provide three performance measures for the good-
ness of a pipeline. These are the Speed-up S(n), Throughput U(n), and Efficiency
E(n). It should be noted that in this analysis we assume that the unit time T
¼
t
units.
1. Speed-up S(n) Consider the execution of m tasks (instructions) using
n-stages (units) pipeline. As can be seen, n
þ
m
1 time units are required
I
1
I
2
I
3
I
4
I
5
I
6
I
7
I
8
I
9
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
1
I
2
I
3
I
4
I
5
I
6
I
7
I
8
I
9
I
10
1
2
3
4
5
6
7
8
9
10
11
12
13
Time
Figure 9.2 The space-time chart (Gantt chart)
Search WWH ::
Custom Search