COMPUTER ORGANIZATION PIPELINE

Module 5

Pipeline
Syllabus:
Basic Concepts, Data Hazards, Instruction hazards, Super Scalar operations, Performance
Considerations

Basic Concepts:
Speed of execution of a programs depends on various factors
Speed can be increased by :
i) Using faster technology to build processor and main memory
ii) Arrange hardware so that more than one operation can be performed at the same
time

PIPELINING: It is a way of organizing the concurrent activities in a processor

Fi=Fetch cycle of ith instruction
Ei=Execution cycle of ith instruction
Execution of a program contains a sequence of execute and fetch steps as shown in Fig 8.1a

Consider a computer that contains 2 hardware units: one for fetching the instructions and the
other for executing them as in Fig 8.1 b

The instruction fetched by fetch unit is placed in buffer B1. Execution unit takes the
instruction from this buffer while the fetch unit fetches the next instruction. It is assumed that
one clock cycle each is required to perform fetch and execute.

Department of AI & ML, MITE, Moodabidri 1

COMPUTER ORGANIZATION PIPELINE

From diagram 8.1(c)

I cycle: Fetch unit fetches the instruction I1 (Step F1) and stores it in buffer B at the end of
clock cycle
II cycle: Fetch unit fetches the instruction I2 (Step F2) and execution unit performs the
operation specified by instruction I1 (Step E1)
By the end of 2nd clock cycle, execution of instruction I1 is completed and Instruction I2 is
now in buffer
III cycle: Instruction I3 is fetched by the fetch unit (Step F3) and Execution of I2 is done by
execution unit (Step E2)
In this manner, both fetch and execute units are busy all the time

Fig 8.2 (b) is an example of 2-stage pipeline, where at a time 2 steps are done

4-Stage pipeline:
F-Fetch: Read the instruction from the memory
D-Decode: Decode the instruction and fetch the source operand
E-Execute: Perform the operation specified by the instruction
W-Write: Store the result in the destination

Department of AI & ML, MITE, Moodabidri 2

COMPUTER ORGANIZATION PIPELINE

The sequence of events are as shown in Fig 8.2(a)

4 instructions are in progress at any time. 4 distinct hardware units are needed as shown in
Fig 8.2(b). These units must be capable of performing their tasks simultaneously and without
interfering with one another. Information is passed from one stage to next through a storage
buffer. During clock cycle 4, information available in buffers are as follows:

Department of AI & ML, MITE, Moodabidri 3

COMPUTER ORGANIZATION PIPELINE

5 stage PIPELINE

Compute

Write
Memory
Buffer B1

Buffer B2
Decode

Buffer B3

Buffer B4
Fetch

Fig : 5-Stage Pipeline

It is assumed that it takes 5 clock cycles to execute each instruction

 Interstage buffer B1 feeds the Decode stage with a newly-fetched instruction.

 Interstage buffer B2 feeds the Compute stage with the two operands taken from the
register file, or the immediate values derived from the instruction or the incremented
PC value (required for subroutine return)
 Interstage buffer B3 holds the result of the ALU operation, which may be data to be
written into the register file or an address that feeds the Memory stage. In the case of
a write access to memory, buffer B3 holds the data to be written. These data were
read from the register file in the Decode stage. The buffer also holds the incremented
PC value passed from the previous stage, in case it is needed as the return address
for a subroutine-call instruction
 Interstage buffer B4 feeds the Write stage with a value to be written into the register
file. This value may be the ALU result from the Compute stage, the result of the
Memory access stage, or the incremented PC value that is used as the return address
for a subroutine-call instruction.

Department of AI & ML, MITE, Moodabidri 4

COMPUTER ORGANIZATION PIPELINE

(Fig 6.1)
 The five stages are labeled as Fetch, Decode, Compute, Memory and Write.
 Instruction Ij is fetched in the first cycle and moves through the remaining stages in the
following cycles.
 In the second cycle, instruction Ij+1 is fetched while instruction Ij is in the Decode
stage where its operands are also read from the register file.
 In the third cycle, instruction Ij+2 is fetched while instruction Ij+1 is in the Decode
stage and instruction Ij is in the Compute stage where an arithmetic or logic operation
is performed on its operands.
 Ideally, this overlapping pattern of execution would be possible for all instructions.
 Although any one instruction takes five cycles to complete its execution, instructions
are completed at the rate of one per cycle.

Pipeline Stall
If all the operations specified are completed in 1 clock cycle time, then overall execution
speed will be at the rate of 1 instruction/clock cycle.
But many times, some of the instructions can’t be executed in a given time
For example, if all arithmetic operations are allotted one clock cycle, and if it is not possible to
complete operations like divide, then the problem occurs.
In the example given in Fig 8.3 , below, operation specified by instruction I 2 takes 3 clock
cycles to complete (from Clock 4 to 6). Thus in cycles 5 and 6 Write stage must wait because
it has no data to write. Hence data in buffer B2 should not be changed until it is used for
execution. This means Stage 1 and in turn stage 2 are blocked from accepting new
instructions because information in B1 should not be overwritten. Thus steps D4 and F5 has
to be postponed.
Pipelined operation in this example has been stalled for 2 clock cycles. Normal pipelined
operation resumes in 7 clock cycles
Any condition that causes pipeline to stall is called a hazard

Department of AI & ML, MITE, Moodabidri 5

COMPUTER ORGANIZATION PIPELINE

DATA HAZARD IN 5-STAGE PIPELINE

Consider
Add R2, R3,#100
Subtract R9,R2,#30
Identify number of stall in the pipeline and explain the reason for the same.

 The destination register R2 for the Add instruction is a source register for the Subtract
instruction.
 There is a data dependency between these two instructions, because register R2
carries data from the first instruction to the second.
 The Subtract instruction is stalled for three cycles to delay reading register
R2 until cycle 6 when the new value becomes available.
 The control circuit must first recognize the data dependency when it decodes the
Subtract instruction in cycle 3 by comparing its source register in interstage buffer B1
with the destination register in interstage buffer B2.
 Then, the Subtract instruction must be held in interstage buffer B1 during cycles 3 to 5.
 Meanwhile, the Add instruction proceeds through the remaining pipeline stages.
 In cycles 3 to 5, as the Add instruction moves ahead, control signals can be set in
interstage buffer B2 for an implicit NOP (No-operation) instruction that does not modify
the memory or the register file.
 Each NOP creates one clock cycle of idle time, called a bubble, as it passes through
the Compute, Memory, and Write stages to the end of the pipeline.

Handling data dependency using hardware - OPERAND

FORWARDING

• Pipeline stalls due to data dependencies can be alleviated through the use of operand
forwarding
• The pipeline is stalled for three cycles to enable the Subtract instruction to use the new
value in register R2.
• The desired value is actually available at the end of cycle 3, when the ALU completes
the operation for the Add instruction.

Department of AI & ML, MITE, Moodabidri 6

COMPUTER ORGANIZATION PIPELINE

• This value is loaded into register RZ which is a part of interstage buffer B3.
• Rather than stall the Subtract instruction, the hardware can forward the value from
register RZ to where it is needed in cycle 4, which is the ALU input.
• Figure 6.4 shows pipelined execution when forwarding is implemented.
• The arrow shows that the ALU result from cycle 3 is used as an input to the ALU in
cycle 4.

Handling Data dependencies in software

 When the compiler identifies a data dependency between two successive instructions
Ij and Ij+1, it can insert three explicit NOP (No-operation) instructions between them.
 The NOPs introduce the necessary delay to enable instruction Ij+1 to read the new
value from the register file after it is written.
 For the instructions in Figure 6.4, the compiler would generate the instruction
sequence in Figure 6.6a.
 Figure 6.6b shows that the three NOP instructions have the same effect on execution
time as the stall in Figure 6.3.

Fig 6.6 a

Figure 6.6b shows that the three NOP instructions have the same effect on execution time as
the stall in Figure 6.3.
Advantage in this method is lesser hardware
Disadvantage: Larger code size
Execution time is not reduced in comparison with operand forwarding

Department of AI & ML, MITE, Moodabidri 7

COMPUTER ORGANIZATION PIPELINE

Unconditional Branching (Example of Instruction Hazard)

Case i) When target address is calculated in Compute stage

Department of AI & ML, MITE, Moodabidri 8

COMPUTER ORGANIZATION PIPELINE

 Figure 6.9 shows the pipelined execution of a sequence of instructions, beginning with
an unconditional branch instruction, Ij .
 The next two instructions, Ij+1 and Ij+2, are stored in successive memory addresses
following Ij .
 The target of the branch is instruction Ik .
 It is assumed that the branch instruction is fetched in cycle 1 and decoded in cycle 2,
and the target address is computed in cycle 3.
 Hence, instruction Ik is fetched in cycle 4, after the program counter has been updated
with the target address.
 In pipelined execution, instructions Ij+1 and Ij+2 are fetched in cycles 2 and 3,
respectively, before the branch instruction is decoded and its target address is known.
 They must be discarded.
 Branch Penalty=2 cycles (when target address is determined in Compute Stage
of Pipeline)

Case ii) When target address is calculated in Decode stage

 It is possible to determine the target address and update the program counter in the
Decode stage.
 Thus, instruction Ik can be fetched one clock cycle earlier, reducing the branch
penalty to one cycle, as shown in Figure 6.10.
 This time, only one instruction, Ij+1, is fetched incorrectly, because the target address
is determined in the Decode stage
 When the instruction decoder determines that the instruction is indeed a branch
instruction, the computed target address will be available before the end of the cycle.
 It can then be used to fetch the target instruction in the next cycle.

Department of AI & ML, MITE, Moodabidri 9

COMPUTER ORGANIZATION PIPELINE

HAZARD

Any condition that causes pipeline to stall is called a hazard

3 types:
 Data Hazard: Condition in which source operand or destination operand are not
available at the expected time in pipeline. As a result some of the operations have to
be delayed and the pipeline stalls
 Instruction Hazard (control Hazard): Caused because of the delay in the availability
of the instruction.
 Example: Miss in cache requires getting the instruction from main memory
 Branch instruction also leads in instruction hazard
 Structural Hazard: Situation when 2 instructions requires the use of given hardware
resource at the same time
 Example: Accessing memory: one instruction may require memory operation for
execute/read process, while another instruction is being fetched. This happens if same
cache is used for both data and instruction

INSTRUCTION HAZARD DUE TO CACHE MISS

 Instruction I1 is fetched from cache during cycle 1 and its execution proceeds normally
 For instruction I2 fetch operation started at cycle 2 but resulted in cache miss
 The instruction fetch unit suspends further fetch operations and waits for arrival of Is
 Let us assume that I2 is loaded into buffer B1 at the end of clock cycle 5
 The pipeline resumes its normal operation after that
 Decode unit is idle in cycles 3 to 5
 Execute unit is idle in cycles 4 to 6
 Write unit is idle in cycles 5 to 7
 Such idle periods are called STALLS

Department of AI & ML, MITE, Moodabidri 10

COMPUTER ORGANIZATION PIPELINE

BRANCH PREDICTION

 To reduce the branch penalty, the processor needs to anticipate that an instruction
being fetched is a branch instruction and predict its outcome to determine which
instruction should be fetched in cycle 2.
 Static branch prediction: Assume that branch will not be taken and fetch the next
instruction in the sequential order
 Dynamic branch prediction
In its simplest form, a dynamic prediction algorithm can use the result of the most
recent execution of a branch instruction. The processor assumes that the next time the
instruction is executed, the branch decision is likely to be the same as the last time.
Hence, the algorithm may be described by the two-state machine in Figure 6.12a. The
two states are:
LT - Branch is likely to be taken
LNT - Branch is likely not to be taken

Branch Prediction 2-State Algorithm (State Machine Representation)

LT - Branch is likely to be taken

LNT - Branch is likely not to be taken

Fig. below shows 2-state Branch Prediction

 Suppose that the algorithm is started in state LNT.
 When the branch instruction is executed and the branch is taken, the machine moves
to state LT.
 Otherwise, it remains in state LNT.
 The next time the same instruction is encountered, the branch is predicted as taken if
the state machine is in state LT.

Department of AI & ML, MITE, Moodabidri 11

COMPUTER ORGANIZATION PIPELINE

 Otherwise it is predicted as not taken.

 This is a simple scheme

 It requires only a single bit to represent the history of execution for a branch
instruction, works well inside program loops.
 Once a loop is entered, the instruction that controls the looping is always the same
except for the last pass through the loop.
 Hence, each prediction for the branch instruction will be correct except in the last
pass. The prediction in the last pass will be incorrect, and the branch history state
machine will be changed to the opposite state. (LNT)
 But when this same loop is entered again, the state machine will lead to the wrong
prediction for the first pass.
 Thus, repeated execution of the same loop results in mispredictions in the first pass
and the last pass.

Branch Prediction 4-State Algorithm (State Machine Representation)

An algorithm that uses four states is shown in Figure 6.12b. The four states
are:
ST - Strongly likely to be taken
LT - Likely to be taken
LNT - Likely not to be taken
SNT - Strongly likely not to be taken

Previous state Present state Next State

LNT branch taken ST
LNT branch not taken SNT

 Assume that the state of the algorithm is initially set to LNT.

 After the branch instruction is executed, and if the branch is actually taken, the state is
changed to ST; otherwise, it is changed to SNT.
 As program execution progresses and the same branch instruction is encountered
multiple times, the state of the prediction algorithm changes as shown.
 The branch is predicted as taken if the state is either ST or LT.

Department of AI & ML, MITE, Moodabidri 12

COMPUTER ORGANIZATION PIPELINE

If the state is either SNT or LNT, the branch is predicted as not taken

 Let us reconsider what happens when executing a program loop.

 Assume that the branch instruction is at the end of the loop and that the processor
sets the initial state of the algorithm to LNT.
 In the first pass, the prediction (not taken) will be wrong, and hence the
 state will be changed to ST.
 In all subsequent passes, the prediction will be correct, except for the last pass.
 At that time, the state will change to LT.
 When the loop is entered a second time, the prediction in the first pass will be to take
the branch, which will be correct if there is more than one iteration.
 Thus, repeated execution of the same loop now results in only one misprediction in the
last pass

SUPERSCALAR OPERATION

 A processor with multiple execution units each of which may be pipelined –

superscalar processors
 A superscalar processor has a more elaborate fetch unit that fetches two or more
instructions per cycle before they are needed and places them in an instruction queue.
 The dispatch unit, takes two or more instructions from the front of the queue, decodes
them, and sends them to the appropriate execution units.
 At the end of the pipeline, another unit is responsible for writing results into the register
file.
 Figure 6.13 shows a superscalar processor with this organization.

Department of AI & ML, MITE, Moodabidri 13

COMPUTER ORGANIZATION PIPELINE

 It incorporates two execution units, one for arithmetic instructions and another for Load
and Store instructions.
 Arithmetic operations normally require only one cycle, hence the first execution unit is
simple.
 Because Load and Store instructions involve an address calculation for the Index
mode before each memory access, the Load/Store unit has a two-stage pipeline

 An arithmetic instruction and a Load or Store instruction must obtain all their operands
from the register file when they are dispatched in the same cycle to the two execution
units.
 The register file must now have four output ports instead of the two output ports
needed in the simple pipeline.
 Similarly, an arithmetic instruction and a Load instruction must write their results into
the register file when they complete in the same cycle.
 Thus, the register file must now have two input ports instead of the single input port for
the simple pipeline.
 There is also the potential complication of two instructions completing at the same
time with the same destination register for their results.
 This complication is avoided, if possible, by dispatching the instructions in a manner
that prevents its occurrence.
 Otherwise, one instruction is stalled to ensure that results are written into the
destination register in the same order as in the original instruction sequence of the
program

Department of AI & ML, MITE, Moodabidri 14

COMPUTER ORGANIZATION PIPELINE

EXAMPLE

Add R2,R3,#100
Load R5, 16(R6)
Subtract R7,R8,R9
Store R10,24(R11)

Develop the instruction flow for the above instruction in a super scalar processor with two
execution units

 The fetch unit fetches two instructions every cycle.

 The instructions are decoded and their source registers are read in the next cycle.
 Then, they are dispatched to the arithmetic and Load/Store units.
 Arithmetic operations can be initiated every cycle.
 A Load or Store instruction can also be initiated every cycle, because the two-stage
pipeline overlaps the address calculation for one Load or Store instruction with the
memory access for the preceding Load or Store instruction.
 As instructions complete execution in each unit, the register file allows two results to
be written in the same cycle because the destination registers are different

Department of AI & ML, MITE, Moodabidri 15