Computer Architecture
• Dr. Abdul Khaliq
• Asst Professor (FCIT)
• University of The Punjab, Lahore
Chapter No 9 : Pipelining
• Laundry Example
• Ann, Brian, Cathy, Dave A B C D
each have one load of clothes
to wash, dry, and fold
• Washer takes 30 minutes
• Dryer takes 40 minutes
• “Folder” takes 20 minutes
Sequential Laundry
6 PM 7 8 9 10 11 Midnight
Time
30 40 20 30 40 20 30 40 20 30 40 20
T
a A
s
k
B
O
r
d C
e
r
D
• Sequential laundry takes 6 hours for 4 loads
• If they learned pipelining, how long would laundry take?
Pipelined Laundry: Start work ASAP
6 PM 7 8 9 10 11 Midnight
Time
30 40 40 40 40 20
T
a A
s
k
B
O
r
d C
e
r
D
• Pipelined laundry takes 3.5 hours for 4 loads
Pipelining Lessons
6 PM 7 8 9
Time
30 40 40 40 40 20
T
a A
s
k
B
O
r
d C
e
r
D
Can pipelining get us into trouble?
• Yes: Pipeline Hazards
– structural hazards: attempt to use the same resource two
different ways at the same time
• E.g., combined washer/dryer would be a structural hazard
or folder busy doing something else (watching TV)
– data hazards: attempt to use item before it is ready
• E.g., one sock of pair in dryer and one in washer; can’t
fold until get sock from washer through dryer
• instruction depends on result of prior instruction still in the
pipeline
– control hazards: attempt to make a decision before condition
is evaulated
• E.g., washing football uniforms and need to get proper
detergent level; need to see after dryer before next load in
• branch instructions
• Can always resolve hazards by waiting
– pipeline control must detect the hazard
– take action (or delay action) to resolve hazards
Pipelining and Vector Processing Pipelining
GENERAL PIPELINE
General Structure of a 4-Segment Pipeline
Clock
Input S1 R1 S2 R2 S3 R3 S4 R4
Space-Time Diagram
1 2 3 4 5 6 7 8 9
Clock cycles
Segment 1 T1 T2 T3 T4 T5 T6
2 T1 T2 T3 T4 T5 T6
3 T1 T2 T3 T4 T5 T6
4 T1 T2 T3 T4 T5 T6
Pipelining and Vector Processing Pipelining
PIPELINE SPEEDUP
n: Number of tasks to be performed
Conventional Machine (Non-Pipelined)
tn: Clock cycle
: Time required to complete the n tasks
= n * tn
Pipelined Machine (k stages)
tp: Clock cycle (time to complete each suboperation)
: Time required to complete the n tasks
= (k + n - 1) * tp
Speedup
Sk: Speedup
Sk = n*tn / (k + n - 1)*tp
tn
lim Sk = ( = k, if tn = k * tp )
n→ tp
Pipelining and Vector Processing Pipelining
PIPELINE AND MULTIPLE FUNCTION UNITS
Example
- 4-stage pipeline
- sub-opertion in each stage; tp = 20nS
- 100 tasks to be executed
- 1 task in non-pipelined system; 20*4 = 80nS
Pipelined System
(k + n - 1)*tp = (4 + 99) * 20 = 2060nS
Non-Pipelined System
n*k*tp = 100 * 80 = 8000nS
Speedup
Sk = 8000 / 2060 = 3.88
Ii I i+1 I i+2 I i+3
4-Stage Pipeline is basically identical to the system
with 4 identical function units
Multiple Functional Units P1 P2 P3 P4
Pipelining and Vector Processing Instruction Pipeline
INSTRUCTION CYCLE
Six Phases* in an Instruction Cycle
[1] Fetch an instruction from memory
[2] Decode the instruction
[3] Calculate the effective address of the operand
[4] Fetch the operands from memory
[5] Execute the operation
[6] Store the result in the proper place
* Some instructions skip some phases
* Effective address calculation can be done in
the part of the decoding phase
* Storage of the operation result into a register
is done automatically in the execution phase
==> 4-Stage Pipeline
[1] FI: Fetch an instruction from memory
[2] DA: Decode the instruction and calculate
the effective address of the operand
[3] FO: Fetch the operand
[4] EX: Execute the operation
Pipelining and Vector Processing Instruction Pipeline
INSTRUCTION PIPELINE
Execution of Three Instructions in a 4-Stage Pipeline
Conventional
i FI DA FO EX
i+1 FI DA FO EX
i+2 FI DA FO EX
Pipelined
i FI DA FO EX
i+1 FI DA FO EX
i+2 FI DA FO EX
Pipelining and Vector Processing Instruction Pipeline
INSTRUCTION EXECUTION IN A 4-STAGE PIPELINE
Segment1: Fetch instruction
from memory
Decode instruction
Segment2: and calculate
effective address
yes Branch?
no
Segment3: Fetch operand
from memory
Segment4: Execute instruction
Interrupt yes
Interrupt?
handling
no
Update PC
Empty pipe
Step: 1 2 3 4 5 6 7 8 9 10 11 12 13
Instruction 1 FI DA FO EX
2 FI DA FO EX
(Branch) 3 FI DA FO EX
4 FI FI DA FO EX
5 FI DA FO EX
6 FI DA FO EX
7 FI DA FO EX
Pipelining and Vector Processing Instruction Pipeline
MAJOR HAZARDS IN PIPELINED EXECUTION
Structural hazards(Resource Conflicts)
Hardware Resources required by the instructions in
simultaneous overlapped execution cannot be met
Data hazards (Data Dependency Conflicts)
An instruction scheduled to be executed in the pipeline requires the
result of a previous instruction, which is not yet available
R1 <- B + C ADD DA B,C + Data dependency
R1 <- R1 + 1
INC DA bubble R1 +1
Control hazards
Branches and other instructions that change the PC
make the fetch of the next instruction to be delayed
JMP ID PC + PC Branch address dependency
bubble IF ID OF OE OS
Hazards in pipelines may make it Pipeline Interlock:
necessary to stall the pipeline Detect Hazards Stall until it is cleared
Pipelining and Vector Processing Instruction Pipeline
DATA HAZARDS
Data Hazards
Occurs when the execution of an instruction
depends on the results of a previous instruction
ADD R1, R2, R3
SUB R4, R1, R5
Data hazard can be dealt with either hardware
techniques or software technique
Hardware Technique
Interlock
- hardware detects the data dependencies and delays the scheduling
of the dependent instruction by stalling enough clock cycles
Forwarding (bypassing, short-circuiting)
- Accomplished by a data path that routes a value from a source
(usually an ALU) to a user, bypassing a designated register. This
allows the value to be produced to be used at an earlier stage in the
pipeline than would otherwise be possible
Software Technique
Instruction Scheduling(compiler) for delayed load
Pipelining and Vector Processing Instruction Pipeline
CONTROL HAZARDS
Branch Instructions
- Branch target address is not known until
the branch instruction is completed
Branch
Instruction FI DA FO EX
Next
FI DA FO EX
Instruction
Target address available
- Stall -> waste of cycle times
Dealing with Control Hazards
* Prefetch Target Instruction
* Branch Target Buffer
* Loop Buffer
* Branch Prediction
* Delayed Branch