lOMoARcP SD| 35064202
MODULE 5
lOMoAR cP SD| 35064202
lOMoARcP SD| 35064202
MODULE 5
1
lOMoARcP SD| 35064202
MODULE 5
2
lOMoARcP SD| 35064202
MODULE 5
3
lOMoARcP SD| 35064202
MODULE 5
4
lOMoARcP SD| 35064202
MODULE 5
5
lOMoARcP SD| 35064202
MODULE 5
6
lOMoARcP SD| 35064202
MODULE 5
7
lOMoARcP SD| 35064202
MODULE 5
8
lOMoARcP SD| 35064202
MODULE 5
9
lOMoARcP SD| 35064202
MODULE 5
10
lOMoARcP SD| 35064202
MODULE 5
11
lOMoARcP SD| 35064202
MODULE 5
Pipelining
I. Pipelining: Basic concepts
Pipelining is a particularly effective way of organizing concurrent activity in a computer
system.
The processor executes a program by fetching and executing instructions, one after the other.
Let Fi and Ei refer to the fetch and execute steps for instruction Ii .
Execution of a program consists of a sequence of fetch and execute steps, as shown in Figure
8.1a .
Consider a computer that has two separate hardware units, one for fetching instructions and
another for executing them, as shown in Figure 8.1b.
The instruction fetched by the fetch unit is deposited in an intermediate storage buffer, B1.
This buffer is needed to enable the execution unit to execute the instruction while the fetch unit
is fetching the next instruction.
The results of execution are deposited in the destination location specified by the instruction.
The computer is controlled by a clock whose period is such that the fetch and execute steps of
any instruction can each be completed in one clock cycle.
In the first clock cycle, the fetch unit fetches an instruction I1 (step F1) and stores it in buffer
B1 at the end of the clock cycle.
In the second clock cycle, the instruction fetch unit proceeds with the fetch operation for
instruction I2 (step F2).
Meanwhile, the execution unit performs the operation specified by instruction I1, which is
available to it in buffer B1 (step E1). By the end of the second clock cycle, the execution of
instruction I1 is completed and instruction I2 is available. Instruction I2 is stored in B1,
replacing I1, which is no longer needed. Step E2 is performed by the execution unit during the
third clock cycle, while instruction I3 is being fetched by the fetch unit.
In this manner, both the fetch and execute units are kept busy all the time. If the pattern in
Figure 8.1c can be sustained for a long time, the completion rate of instruction execution will
be twice that achievable by the sequential operation depicted in Figure 8.1a.
12
lOMoARcP SD| 35064202
MODULE 5
Four Stage Pipeline:
The processing of an instruction need not be divided into only two steps.
For example, a pipelined processor may process each instruction in four steps, as follows:
F Fetch: read the instruction from the memory.
D Decode: decode the instruction and fetch the source operand(s).
E Execute: perform the operation specified by the instruction. W Write: store the result in the
destination location.
13
lOMoARcP SD| 35064202
MODULE 5
The sequence of events for this case is shown in Figure 8.2a.
Four instructions are in progress at any given time. This means that four distinct hardware units
are needed, as shown in Figure 8.2b.
These units must be capable of performing their tasks simultaneously and without interfering
with one another.
Information is passed from one unit to the next through a storage buffer. As an instruction
progresses through the pipeline, all the information needed by the stages downstream must be
passed along.
II. Role of Cache memory
Each stage in a pipeline is expected to complete its operation in one clock cycle.
Hence, the clock period should be sufficiently long to complete the task being performed in
any stage.
If different units require different amounts of time, the clock period must allow the longest task
to be completed.
A unit that completes its task early is idle for the remainder of the clock period. Hence,
pipelining is most effective in improving performance if the tasks being performed in different
stages require about the same amount of time.
This consideration is particularly important for the instruction fetch step, which is assigned
one clock period in Figure 8.2a.
The clock cycle has to be equal to or greater than the time needed to complete a fetch operation.
However, the access time of the main memory may be as much as ten times greater than the
time needed to perform basic pipeline stage operations inside the processor, such as adding
two numbers.
Thus, if each instruction fetch required access to the main memory, pipelining would be of
little value.
14
lOMoARcP SD| 35064202
MODULE 5
The use of cache memories solves the memory access problem.
In particular, when a cache is included on the same chip as the processor, access time to the
cache is usually the same as the time needed to perform other basic operations inside the
processor.
This makes it possible to divide instruction fetching and processing into steps that are more or
less equal in duration.
Each of these steps is performed by a different pipeline stage, and the clock period is chosen
to correspond to the longest one.
The pipelined processor in above Figure completes the processing of one instruction in each
clock cycle, which means that the rate of instruction processing is four times that of sequential
operation.
The potential increase in performance resulting from pipelining is proportional to the number
of pipeline stages.
15
lOMoARcP SD| 35064202
MODULE 5
III. Pipeline Performance
Pipelined operation in Figure 8.3 is said to have been stalled for two clock cycles.
Normal pipelined operation resumes in cycle 7. Any condition that causes the pipeline to stall
is called a Data hazard.
A data hazard is any condition in which either the source or the destination operands of an
instruction are not available at the time expected in the pipeline.
As a result some operation has to be delayed, and the pipeline stalls.
The pipeline may also be stalled because of a delay in the availability of an instruction.
For example, this may be a result of a miss in the cache, requiring the instruction to be fetched
from the main memory. Such hazards are often called control hazards or instruction
hazards.
The effect of a cache miss on pipelined operation is illustrated in Figure 8.4.
Instruction I1 is fetched from the cache in cycle 1, and its execution proceeds normally.
However, the fetch operation for instruction I2, which is started in cycle 2, results in a cache
miss.
The instruction fetch unit must now suspend any further fetch requests and wait for I2 to arrive.
We assume that instruction I2 is received and loaded into buffer B1 at the end of cycle 5. The
pipeline resumes its normal operation at that point.
16
lOMoARcP SD| 35064202
MODULE 5
An alternative representation of the operation of a pipeline in the case of a cache miss is shown
in Figure 8.4b. This shows the function performed by each pipeline stage in each clock cycle.
Note that the Decode unit is idle in cycles 3 through 5, the Execute unit is idle in cycles 4
through 6, and the Write unit is idle in cycles 5 through 7. Such idle periods are called stalls.
They are also often referred to as bubbles in the pipeline.
Once created as a result of a delay in one of the pipeline stages, a bubble moves downstream
until it reaches the last unit.
A third type of hazard that may be encountered in pipelined operation is structural hazard.
This is the situation when two instructions require the use of a given hardware resource at the
same time. The most common case in which this hazard may arise is in access to memory.
One instruction may need to access memory as part of the Execute or Write stage while another
instruction is being fetched.
If instructions and data reside in the same cache unit, only one instruction can proceed and the
other instruction is delayed.
Many processors use separate instruction and data caches to avoid this delay.
17