SHRI G.S.
INSTITUTE OF TECHNOLOGY
AND SCIENCE
Computer Architecture and Organisation (CO-24009)
Session : 2019-2020
Pipelining
Presented by:
Presented To:
Mahak Mandlecha
Miss. Himani Mishra
Mradul Rathore 1
(Assistant Professor)
Contents
1. Pipelining
2. Types of Pipelining
3. Advantages of Pipelining
4. Hazards
5. Numericals
10th Sept 2019 2
Pipelining Case : Laundry
❖ 4 loads of laundry that need to
washed , dried and folded.
➢ 30 minutes to wash, 40
minutes to dry , and 20
minutes to fold.
➢ We have 1 washer , 1 drier ,
and 1 folding station.
❖ What’s the most efficient way to
get the 4 loads of laundry
done???
3
10th Sept 2019
4
10th Sept 2019
5
10th Sept 2019
What is Pipelining?
● Pipelining is a technique where multiple
instructions are overlapped during execution.
Pipeline is divided into stages and these
stages are connected with one another to form
a pipe like structure. Instructions enter from
one end and exit from another end.
10th Sept 2019 6
Stages of Pipelining
● Consider the following decomposition for processing the
instructions
○ Fetch instruction – Read into a buffer
○ Decode instruction – Determine opcode, operands
○ Calculate operands – Indirect, Register indirect, etc.
○ Fetch operands – Fetch operands from memory
○ Execute instructions – Execute
○ Write result – Store result if applicable
10th Sept 2019 7
8
10th Sept 2019
Types of Pipelining
9
INSTRUCTION PIPELINE
10
10th Sept 2019
ARITHMETIC PIPELINE
11
10th Sept 2019
Advantages of Pipelining
● Instruction throughput increases.
● Increase in the number of pipeline stages increases the
number of instructions executed simultaneously.
● Faster ALU can be designed when pipelining is used.
● Pipelined CPU works at higher clock frequencies than the
RAM.
● Pipelining increases the overall performance of the CPU.
10th Sept 2019 12
Pipeline Hazards
● These are the situations that prevent the next instruction in the instruction
stream from executing its designated cycle.
● There are three classes of hazards
○ Structural hazard : Attempt to use the same resources by two different
instruction at the same time.
○ Data hazards : Attempt to use the data before it is ready.
■ An instruction’s source operands are produced by a prior
instruction still in the pipeline.
○ Control hazards : Attempt to make a decision about program control
flow before the condition has been evaluated and the new PC targets
address calculated
10th Sept 2019 ■ Branch instruction 13
14
10th Sept 2019
Some Important Terms
1. Speed-up Ratio(Sk) : It is the ratio of non-pipelined
execution time to pipelined execution time.
2. Throughput(Hk): Number of Instructions executed per
unit time.
10th Sept 2019 15
Pipeline Performance: Clock & Timing
Clock Cycle of the Pipeline : 𝜏
Latch Delay : d
𝜏 = max{ 𝜏m} +d
Pipeline Frequency: f f = 1/𝜏 16
10th Sept 2019
Speedup and Efficiency
K-stage pipeline processes n tasks in k+(n-1) clock cycles:
K cycles for the first task and n-1 cycles for the remaining n-1 tasks.
Total time to process n tasks
Tk = [ k + (n-1) ] 𝜏
For the non-pipelined processor
T1 = n k 𝜏
Speed up factor
Sk = T1 / Tk = n k 𝜏 / [ k+ (n-1) ] 𝜏 = n k / k + (n-1)
17
10th Sept 2019
18
10th Sept 2019
● Speed up factor : Sk = n k / k + (n-1)
● Efficiency: Ek = n / (n+k-1)
19
Numerical
Consider a pipeline having 4 phases with duration 60, 50, 90
and 80 ns. Given latch delay is 10 ns. Calculate-
1. Pipeline cycle time
2. Non-pipeline execution time
3. Speed up ratio
4. Pipeline time for 1000 tasks
5. Sequential time for 1000 tasks
6. Throughput
20
10th Sept 2019
Given-
● Four stage pipeline is used
● Delay of stages = 60, 50, 90 and 80 ns
● Latch delay or delay due to each register = 10 ns
Part-01: Pipeline Cycle Time-
Cycle time
= Maximum delay due to any stage + Delay due to its register
= Max { 60, 50, 90, 80 } + 10 ns
= 90 ns + 10 ns
= 100 ns
21
10th Sept 2019
Part-02: Non-Pipeline Execution Time-
Non-pipeline execution time for one instruction
= 60 ns + 50 ns + 90 ns + 80 ns
= 280 ns
Part-03: Speed Up Ratio-
Speed up
= Non-pipeline execution time / Pipeline execution time
= 280 ns / Cycle time
= 280 ns / 100 ns
= 2.8
22
10th Sept 2019
Part-04: Pipeline Time For 1000 Tasks-
Pipeline time for 1000 tasks
= Time taken for 1st task + Time taken for remaining 999 tasks
= 1 x 4 clock cycles + 999 x 1 clock cycle
= 4 x cycle time + 999 x cycle time
= 4 x 100 ns + 999 x 100 ns
= 400 ns + 99900 ns
= 100300 ns
Part-05: Sequential Time For 1000 Tasks-
Non-pipeline time for 1000 tasks
= 1000 x Time taken for one task
= 1000 x 280 ns
23
10th Sept 2019 = 280000 ns
Part-06: Throughput-
Throughput for pipelined execution
= Number of instructions executed per unit time
= 1000 tasks / 100300 ns
10th Sept 2019 24
References
Book:
1. William Stallings , Computer Organisation and
Architecture Ninth Edition, 2009
Some Websites:
1. https://simple.wikipedia.org/wiki/Instruction_pi
pelining
2. https://www.elprocus.com/pipelining-
architecture-hazards-advantages-
disadvantages/
3. https://www.slideshare.net/siddiqueibrahim37/pi
25
10th Sept 2019 pelining-41608675
ANY QUESTIONS
26
27
