PIPELINING

INTRODUCTION
vWhy?

vPipelining is an effective way of organizing concurrent activity in a

computer system to improve the speed of execution of programs.

vSequential execution

vWhat if the execution of one instruction is overlapped with the

fetching of the next one?
HARDWARE UNITS
vComputer has two separate hardware units, one for fetching
instructions and one for executing instructions.
vInstruction is fetched by instruction fetch unit and deposited in an
intermediate buffer B1.
vBuffer enables the instruction execution unit to execute the instruction
while the fetch unit is fetching the next instruction.
vResults of the execution are deposited in the destination location
specified by the instruction.
Continued…
vComputer is controlled by a clock whose period is such that the fetch
and execute steps of any instruction can be completed in one clock
cycle.

vFirst clock cycle: Fetch unit fetches I1 (F1) and stores it in B1.

vSecond clock cycle:

vThird clock cycle:

vFourth clock cycle:

INTERSTAGE BUFFER
vIn each clock cycle, the fetch unit fetches the next instruction, while
the execution unit executes the current instruction stored in the
interstage buffer.
vIf this pattern of fetch and execute can be sustained for a long time,
the completion rate of instruction execution will be twice that
achievable by the sequential operation.
vFetch and execute units constitute a two-stage pipeline.
qEach stage performs one step in processing of an instruction.
qInterstage storage buffer holds the information that needs to be
passed from the fetch stage to execute stage.
qNew information gets loaded into the buffer every clock cycle.
4 – STAGE PIPELINE

vSuppose the processing of an instruction is divided into four steps:

qFetch; Decode; Execute and Write
vAs an instruction progresses through the pipeline, the information
needed by the downstream units must be passed along (using interstage
buffers).
EXAMPLE

Clock cycle
1: F1 2: D1, F2 3: E1, D2, F3

Q: Identify the information in buffers in clock cycle 4.

Continued…
vDuring clock cycle #4:
1. Buffer B1 holds
instruction I3,
Instruction I3 was
fetched in cycle 3.

2. Buffer B2 holds the source and destination operands for instruction I2.
It also holds the information needed for the Write step (W2) of
instruction I2.
3. Buffer B3 holds the results produced by the execution unit and the
destination information for instruction I1.
ROLE OF CACHE MEMORY
vEach stage in the pipeline is expected to complete its operation in one
clock cycle:

qClock period should be sufficient to complete the longest task.

qUnits which complete the tasks early remain idle for the
remaining clock period.

qTasks being performed in different stages should require about

the same amount of time for pipelining to be effective.

vTime required to fetch the instruction:

qIf instructions are to be fetched from the main memory

qif instructions are to be fetched from the cache memory

PIPELINE PERFORMANCE
vPotential increase in performance achieved by using pipelining is
proportional to the number of pipeline stages.

vFor example, if the number of pipeline stages is 4, then the rate of

instruction processing is 4 times that of sequential execution of
instructions.

vPipelining does not cause a single instruction to be executed faster, it is

the throughput that increases.

vIf a pipelined operation cannot be sustained without interruption, the

pipeline is said to “stall” à condition called a “hazard”.
DATA HAZARD
vExecution of the instruction occurs in the E stage of the pipeline.

vExecution of most
arithmetic and logic
operations would take only
one clock cycle; but some
operations such as division
would take more time to
complete.
EXAMPLE
vIf the operation specified in instruction I2 takes three cycles to
complete from cycle 4 to cycle 6.
vCycles 5 and 6, the Write stage is idle, because it has no data to work
with.
vInformation in buffer B2 must be retained till the execution of the
instruction I2 is complete.
vStage 2, and by extension stage 1 cannot accept new instructions
because the information in B1 cannot be overwritten.
vSteps D6 and F5 must be postponed.
vA data hazard is a condition in which either the source or the
destination operand is not available at the time expected in the pipeline.
CONTROL / INSTRUCTION HAZARD
vPipeline may be stalled because an instruction is not available at the
expected time.
vFor example, while fetching a cache miss may occur
vFor example, the fetching of instruction I2 results in a cache miss.
vThus, F2 takes 4 clock cycles instead of 1.
EXAMPLE
vFetch operation for instruction I2 results in a cache miss

vSuppose fetching instruction I2 from the main memory takes 4 clock cycles.
Instruction I2 will be available in buffer B1 at the end of clock cycle 5.

vDecode unit is idle in cycles 3 through 5.

vExecute unit is idle in cycles 4 through 6.

vWrite unit is idle in cycles 5 through 7.

vSuch idle periods are called as stalls or bubbles.

vOnce created in one of the pipeline stages, a bubble moves downstream unit it
reaches the last unit.
PIPELINE STALLS
STRUCTURAL HAZARD
vTwo instructions require the use of a hardware resource at the same
time.
vMost common case is in access to the memory:
qOne instruction needs to access the memory as part of the
Execute or Write stage.
qOther instruction is being fetched.
qIf instructions and data reside in the same cache unit, only one
instruction can proceed and the other is delayed.
vMany processors have separate data and instruction caches to avoid this
delay.
vIn general, structural hazards can be avoided by providing sufficient
resources on the processor chip.
EXAMPLE
OBSERVATIONS
vPipelining does not cause an individual instruction to be executed faster,
rather, it increases the throughput.

vWhen a hazard occurs, one of the stages in the pipeline cannot

complete its operation in one clock cycle.

vThe pipeline stalls causing a degradation in performance.

vPerformance level of one instruction completion in each clock cycle is

the upper limit for the throughput that can be achieved in a pipelined
processor.
DATA HAZARD
vData hazard is a situation in which the pipeline is stalled because the
data to be operated on are delayed.

vConsider two instructions: I1: A = 3 + A I2: B= 4 x A

vIf A = 5, and I1 and I2 are executed sequentially, B=32.

vIn a pipelined processor ?

vResults obtained using sequential execution of instructions should be

the same as the results obtained from pipelined execution.
EXAMPLE

vMul instruction: results à register R4 at the end of clock cycle 4.

vRegister R4 is used as a source operand in the Add instruction. Hence the
Decode Unit decoding the Add instruction cannot proceed until the Write
step of the first instruction is complete.
vData dependency
OPERAND FORWARDING
vData hazard occurs because the destination of one instruction is used
as the source in the next instruction.

vHence, instruction I2 has to wait for the data to be written in the

register file by the Write stage at the end of step W1.

vHowever, these data are available at the output of the ALU once the
Execute stage completes step E1.

vDelay can be reduced or even eliminated if the result of instruction I1

can be forwarded directly for use in step E2.
Continued… vThree-Bus organization.

vSRC1, SRC2 and RSLT are

interstage buffers for
pipelined operation.

vSRC1 and SRC2 are part of

buffer B2.

vRSLT is part of buffer B3.

vData forwarding mechanism

is shown by the two blue
lines.
Continued…
I1: Mul R2, R3, R4
I2: Add R5, R4, R6

vClock cycle 3

vClock cycle 4

vInstruction I2 proceeds
without interruption.
DATA DEPENDENCY IN SOFTWRAE
vData dependency may be detected by the hardware while decoding the
instruction

vDetecting data dependencies and handling them can also be

accomplished in software.
qCompiler can introduce the necessary delay by introducing an
appropriate number of NOP instructions. Example
I1: Mul R2, R3, R4
NOP

NOP
I2: Add R5, R4, R6
SIDE EFFECTS
vData dependencies are explicit easy to detect if a register specified as
the destination in one instruction is used as a source in the subsequent
instruction.

vHowever, some instructions also modify registers that are not specified
as the destination.

qExample: autoincrement and autodecrement addressing mode

vWhen a location other than the one explicitly specified in the

instruction as a destination location is affected, the instruction is said
to have a “side effect”.
Continued…
vAnother example of a side effect is condition code flags
I1: Add R3, R4
I2: AddWithCarry R2, R4

vInstruction I1 sets the carry flag and instruction I2 uses the carry
flag leading to an implicit dependency between the two instructions.

vInstructions with side effects can lead to multiple data dependencies.

vResults in a significant increase in the complexity of hardware or

software needed to handle the dependencies.

vSide effects should be kept to a minimum in instruction sets designed

for execution on pipelined hardware.
INSTRUCTION HAZARDS
vInstruction fetch units fetch instructions and supply the execution units
with a steady stream of instructions.

vIf the stream is interrupted then the pipeline stalls.

vStream of instructions may be interrupted because of a cache miss or a

branch instruction.
EXAMPLE: 2 – STAGE PIPELINE
vConsider a two-stage pipeline. Instructions I1, I2 and I3 are stored at
successive memory locations. I2 is a branch instruction with branch target as
instruction Ik. I2 is an unconditional branch instruction.

vClock cycle 3: Fetch unit à fetches instruction I3.

Execute unit à decodes I2 and computes the branch target address

vClock cycle 4: Processor must discard I3 which has been incorrectly fetched and
fetch Ik.

Execution unit is idle, and the pipeline stalls for one clock cycle.
Continued…

vPipeline stalls for one clock cycle.

vTime lost as a result of a branch instruction is called as branch penalty.
vBranch penalty is one clock cycle.
IF 4 – STAGE PIPELINE ? vBranch penalty depends on
the length of the pipeline,
may be higher for a longer
pipeline.
vFor a four-stage pipeline:
qBranch target address is
computed in stage E2.
qInstructions I3 and I4
have to be discarded.
qExecution unit is idle for
2 clock cycles.
qBranch penalty is 2 clock
cycles.
Branch Penalty Reduction?
vComputing the branch target address
earlier in the pipeline.
vInstruction fetch unit has special
hardware to identify a branch
instruction after the instruction is
fetched.
vBranch target address can be
computed in the Decode stage (D2),
rather than in the Execute stage
(E2).
vBranch penalty is only one clock
cycle.
INSTRUCTION QUEUE
Instruction Queue
F: Fetch
Instruction ...

D: Dispatch/ E: Execute W: Write

Decode Unit Instruction Results

v Fetch unit fetches instructions before they are needed & stores them
in a queue à Instruction Queue can hold several instructions
v Dispatch unit takes instructions from the front of the queue and
dispatches them to the Execution unit. Dispatch unit also decodes the
instruction.
Continued…
vFetch unit must have sufficient decoding and processing capability to
recognize and execute branch instructions.

vPipeline stalls because of a data hazard:

qDispatch unit cannot issue instructions from the queue.

qFetch unit continues to fetch instructions and add them to the

queue.

vDelay in fetching because of a cache miss or a branch:

qDispatch unit continues to dispatch instructions from the instruction

queue.
 How queue length changes and how it affects the
QUEUE LENGTH relationship between different pipeline stages.

Clock Cycle 1 2 3 4 5 6 7 8 9 10
Queue Length 0 1 1 1 2 3 2 1 1 1
I1 F1 D1 E1 E1 E1 W1
I2 F2 D2 E2 W2
I3 F3 D3 E3 W3
I4 F4 D4 E4 W4
I5(Branch) F5 D5
I6 F6 X
Ik FK DK EK WK
Ik+1 FK+1 DK+1 EK+1
BRANCH FOLDING
vPreviously, I2, I3, I4 and Ik are executed in successive clock cycles.
Fetch unit computes the branch address concurrently with the execution
of other instructions. This is called as branch folding.

vBranch folding can occur if there is at least one instruction available in

the queue other than the branch instruction.

vInstruction queue also mitigates the impact of cache misses.

CONDITIONAL BRANCHES and BRANCH PREDICTION
vConditional branch instructions depend on the result of a preceding
instruction.
qDecision on whether to branch cannot be made until the execution of
the preceding instruction is complete.

vBranch instructions represent 20% of the dynamic instruction count of most

programs.

vBranch instructions may incur branch penalty reducing the performance

gains expected from pipelining.

vSeveral techniques to mitigate the negative impact of branch penalty on

performance.
DELAYED BRANCH
vBranch target address is computed in
stage E2.
vInstructions I3 and I4 have to be
discarded.
vLocation following a branch
instruction is called a branch delay
slot.
vIn this case, there are two branch
delay slots.
vThe instructions in the delay slot are
always fetched and at least partially
executed before the branch decision
is made and the branch address is
computed.
Continued…
vDelayed branching can minimize the penalty incurred as a result of
conditional branch instructions.

vSince the instructions in the delay slots are always fetched and
partially executed, it is better to arrange for them to be fully executed
whether or not branch is taken.

vIf we are able to place useful instructions in these slots, then they will
always be executed whether or not the branch is taken.

vIf we cannot place useful instructions in the branch delay slots, then
we can fill these slots with NOP instructions.
EXAMPLE vRegister R2 is used as a counter to
determine how many times R1 is to be
shifted.

vProcessor has a two stage pipeline or

one delay slot.

vInstructions can be reordered so that

the shift left instruction appears in the
delay slot.

vShift left instruction is always

executed whether the branch condition
is true or false.
OBSERVATIONS
vLogically, the program is executed as if the branch instruction were
placed after the shift instruction.
vBranching takes place one instruction later than where the branch
instruction appears in the instruction sequence (with reference to
reordered instructions).
vHence, this technique is termed as “delayed branch”.
Delayed branch requires reordering as many instructions as the number
of delay slots.
vUsually possible to reorganize one instruction to fill one delay slot.
vDifficult to reorganize two or more instructions to fill two or more
delay slots.
BRANCH PREDICTION
vTo reduce the branch penalty associated with conditional branches, we
can predict whether the branch will be taken.

vSimplest form of branch prediction:

qAssume that the branch will not take place.
qContinue to fetch instructions in sequential execution order.
qUntil the branch condition is evaluated, instruction execution
along the predicted path must be done on a speculative basis.

v“Speculative execution” implies that the processor is executing

instructions before it is certain that they are in the correct sequence.
Continued…
vIf branch outcomes were random, then the simple approach of always
assuming that the branch would not be taken would be correct 50% of
the time.

vHowever, branch outcomes are not random and it may be possible to

determine a priori whether a branch will be taken or not depending on
the expected program behavior. For example:
qBranch instruction at the end of the loop à this branch is
always predicted as taken.
qBranch instruction at the beginning of the loop à this branch is
always predicted as not taken.
PREDICT RESULT OF BRANCH INSTRUCTION
vWhich way to predict the result of the branch instruction (taken or
not taken) may be made in the hardware, depending on the target
address of the branch instruction in comparison to the address of
branch instruction.
qIf the target address is lower, then the branch is predicted as
taken.
qIf the target address is higher, then the branch is predicted as
not taken.
vBranch prediction can also be handled by the compiler.
qSet the branch prediction bit to 0 or 1 to indicate the desired
behavior.
qInstruction fetch unit checks the branch prediction bit
STATIC / DYNAMIC BRANCH PREDICTION
vBranch prediction decision is the same every time an instruction is
executed à “static branch prediction”.

vBranch prediction decision may change depending on the execution

history à “dynamic branch prediction”.

vBranch prediction algorithms should minimize the probability of making

a wrong branch prediction decision.
DYNAMIC BRANCH PREDICTION
vProcessor hardware assesses the likelihood of a given branch being
taken by keeping track of branch decisions every time that instruction
is executed.
vSimplest form of execution history used in predicting the outcome of a
given branch instruction is the result of the most recent execution of
that instruction.
qProcessor assumes that the next time the instruction is
executed, the result is likely to be the same.
qFor example, if the branch was taken the last time the
instruction was executed, then the branch is likely to be taken
this time as well.
BRANCH PREDICTION ALGORITHM
v Algorithm described as a two-state machine with 2 states:
q LT : Branch is likely to be taken
q LNT: Branch is likely not to be taken
v Initial state of the machine be LNT
v When the branch instruction is executed, and if the branch is taken, the
machine moves to state LT.
v If the branch is not taken,
it remains in state LNT.
Continued…
vRequires only one bit of history information for each branch instruction.

vWorks well inside loops:

qOnce a loop is entered, the branch instruction that controls the looping
will always yield the same result until the last pass.
qIn the last pass, the branch prediction will turn out to be incorrect.
qThe branch history state machine will be changed to the opposite state.
qHowever, if the same loop is entered the next time, and there is more
than one pass, the branch prediction machine will lead to wrong branch
prediction.

vBetter performance may be achieved by keeping more execution history.

ALGORITHM USING 4 - STATES
vInitial state of the algorithm is LNT.
vIf the branch is taken à ST
vIn state SNT:
qPrediction à branch is not taken.
qIf the branch is actually taken, the
state changes to LNT
qNext time the branch is encountered,
the prediction again is that it is not
taken.
qIf the prediction is wrong the second
time, the state changes to ST.
qAfter that, the branch is predicted as
taken.
EXAMPLE:
vConsider a loop with a branch instruction at the end.
vInitial state of the branch prediction algorithm à LNT.
vIn the first pass, the algorithm will predict that the branch is not
taken.
qThis prediction will be incorrect; state of the algorithm à ST.
vIn the subsequent passes, prediction will be that the branch is taken:
qPrediction will be incorrect, except for the last pass.
vIn the last pass, the branch is not taken:
qThe state will change to LT from ST.
vWhen the loop is entered the second time, the algorithm will predict
that the branch is taken:
qThis prediction will be correct.
CONCLUSION:
vBranch prediction algorithm wrongly predicts the outcome in the first
pass.
vThe prediction in the first pass depends on the initial state
vIf the initial state can be set correctly, then wrong prediction can be
avoided
vInformation necessary to set the initial state of the branch prediction
algorithm can be provided by static prediction schemes.
vComparing branch target address with address of branch instruction
vChecking the branch prediction bit set by the compiler.
vBranch instruction at the end of the loop, initial state is LT.
vBranch instruction at the start of the loop, initial state is LNT.
vWith this, the only incorrect prediction that occurs is on the final pass
through the loop. This is unavoidable.
SUPERSCALAR OPERATION
vPipelining enables multiple instructions to be executed concurrently by
dividing the execution of an instruction into several stages:

qInstructions enter the pipeline in strict program order.

qIf the pipeline does not stall, one instruction enters the pipeline and
one instruction completes execution in one clock cycle.

qMaximum throughput of a pipelined processor is one instruction per

clock cycle.

vAn alternative approach is to equip the processor with multiple

processing units to handle several instructions in parallel in each stage.
Continued…
vIf a processor has multiple processing units then several instructions
can start execution in the same clock cycle.

vProcessor is said to use “multiple issue”.

vThese processors are capable of achieving instruction execution

throughput of more than one instruction per cycle.

vThese processors are known as “superscalar processors”.

PERFORMANCE OBSERVATIONS
vVarious hazards cause a even greater deterioration in performance in case
of a superscalar processor.

vCompiler can avoid many hazards by careful ordering of instructions:

qFor example, the compiler should try to interleave floating- point and
integer instructions.

qDispatch unit can then dispatch two instructions in most clock cycles,
and keep both integer and floating point units busy most of the time.

vIf the compiler can order instructions in such a way that the available
hardware units can be kept busy most of the time, high performance can
be achieved.
SUPERSCALAR OPERATION

v Identify the operations in every clock cycle.

v What will be the final order of completion for above instructions?
OUT – OF – ORDER EXECUTION
vInstructions are dispatched in the same order as they appear in the
program, however, they complete execution out-of-order.

qDependencies should be handled correctly

vWhat if during the execution of an instruction an exception occurs and

one or more of the succeeding instructions have been executed to
completion?

vIf a processor permits succeeding instructions to complete execution

and write to the destination locations, before knowing whether the prior
instructions cause exceptions, it is said to allow “imprecise exceptions”.
PRECISE EXCEPTION
To guarantee a consistent
state when exceptions occur,
the results of execution must
be written to the destination
locations strictly in the
program order.

vStep W2 must be delayed until cycle 6, when I1 enters the write stage.
vInteger unit must retain the results of I2 until cycle 6, and cannot accept
another instruction until then.
vIf an exception occurs during an instruction, then all subsequent
instructions that may have been partially executed are discarded.
EXECUTION COMPLETION
vIt is beneficial to allow out-of-order execution, so that the execution
unit is freed up to execute other instructions.

vHowever, instructions must be completed in program order to allow

precise exceptions.

vThese requirements are conflicting.

vIt is possible to resolve the conflict by allowing the execution to

proceed and writing the results into temporary registers.

vThe contents of the temporary registers are transferred to permanent

registers in correct program order.
EXAMPLE:
vStep TW à
write into a
temporary
register.
vStep W is
called the
“commitment
step”

vBefore the commitment step, if any instruction causes an exception,

then the results of the succeeding instructions that are still in the
temporary registers can be safely discarded.
REGISTER RENAMING

vTemporary register à permanent register whose data it is holding.

vExample: if the destination register of I2 is R5, then the temporary register

used in step TW2 is treated as R5 in the clock cycles 5 and 6.

vIf any succeeding instruction refers to R5 during clock cycles 5 and 6, then
the contents of the temporary register are forwarded.
OBSERVATIONS
vA special control unit called “commitment unit” is needed to ensure in-order
commitment when out-of-order execution is allowed.

vCommitment unit has a queue called “reorder buffer” to determine which

instructions should be committed next.

vWhen an instruction reaches the head of the queue and its execution has
been completed:
qResults are transferred from temporary registers to permanent
registers.
qAll resources assigned to this instruction are released à “retired”.

vInstructions are retired strictly in program order, though they may be

complete execution out-of-order.
PROBLEMS
1. Consider the given sequence of instructions:
ADD #20, R0, R1
MUL #3, R2, R3
AND #$3A, R2, R4
ADD R0, R2, R5
Initially, R0 and R2 contains 2000 and 50, respectively. These instructions are
executed in a 4-stage pipeline computer. Assume that 1st instruction is fetched in
clock cycle 1, and that instruction fetch requires only 1 clock cycle.
a) Draw the timing pipeline diagram. Describe the operation being performed by
each pipeline stage during each of clock cycles 1 through 4.
b) Give the contents of the interstage buffers, B1, B2 and B3 during clock cycles
2 to 5.
2. Instruction I2 is delayed because it depends on the results of I1. By
occupying the decode stage, instruction I2 blocks I3, which in turn blocks I4.
Assuming that I3 and I4 do not depend on either I1 or I2 and that the register
file allows two Write steps to proceed in parallel, how would you use the
additional storage buffers to make it possible for I3 and I4 to proceed earlier
than in previous solution. Redraw the diagram, showing the new order of steps.

3. The delay bubble due to data dependency arises because I2 is delayed in the
Decode stage. As a result, instructions I3 and I4 are delayed even if they do not
depend on either I1 or I2. Assume that decode stage allows two decode steps to
proceed in parallel. Show that the delay bubble can be completely eliminated if
the register file also allows two write steps to proceed in parallel.
4. A program loop ends with a conditional branch to the beginning of the loop.

How would you implement this loop on a pipelined computer that uses delayed

branching with one delay slot? Under what conditions would you be able to put a

useful instruction in the delay slot?

5. Assume that 20% of the dynamic count of the instructions executed on a

computer are branch instructions. Delayed branching is used, with one delay slot.

Estimate the gain in performance if computer is able to use 85% of the delay

slots.
6. A pipelined processor has two branch delay slots. An optimizing

compiler can fill one of these slots 85% of the time and can fill the

second delay slots only 20% of the time. What is the percentage

improvement in performance achieved by this optimization, assuming that

20% of the instructions executed are branch instructions.