Lectures on
Pipeline and Vector
Processing
UNIT 6
Parallel Processing
Simultaneous Data Processing To achieve faster results
Multiple
ALUs
One instr in
ALU other Operand
read from SPEED fetch ready
memory
Multiple
Instruction
in Queue
Throughput: Amount of Processing that can be accomplished during a given interval of Time
Processor With Multiple Functional Units
Flynn’s Classification of Computers
SISD (Single Instruction stream, Single data stream)
SIMD (Single Instruction stream, Multiple data stream)
MISD (Multiple Instruction stream, Single data stream)
MIMD (Multiple Instruction stream, Multiple data stream)
SISD
Contains,
A control Unit
A processor Unit
A memory Unit
Instructions are executed Sequentially (may not have internal
parallel Processing capabilities)
SIMD
Contains
Many Processing Units under a common control
Unit
All processors receive the same instruction from the control unit but
operate on different items of data
MIMD
Multiprocessor
System and Multi
pcomputer System
In this Unit
Pipeline Processing
Vector Processing
Array Processor
Pipelining
It is a technique of decomposing sequential process into
sub-operations
For an Example: Ai*Bi + Ci for i=0,1,2...7
Continue...
General Structure of 4-Segment
Pipeline
Si ==> Combinational Circuits
Ri ==> Registers
i ==> Stages
Space Time Diagram
SpeedUp formula
Where
if n >> (k-1) then formula will be K is segment pipeline
tp Clock Cycle time to
execute n task
If unit time is same for both tn is time required to
pipeline & Non Pipeline unit then complete task in nonpipeline
we can write tn= ktp So including
unit
this assumption
n is task
SIMD revisited
Reason for not achieving the
theoritical rate for pipeline
Different segments may take different time
The clock cycle must be choosen as per propagation
delay. (Waste of time for those which are faster than
others)
Intermidiate registers may not needed
Pipeline
Arithmetic Instruction
divides arithmetic operates on a stream of
operations in to instruction by
suboperations overlapping
Fetch,Decode &
Execute
Already seen in previous
slides
Instruction Pipeline
Sequence/steps to be followed for Example: 4 STAGE INSTRUCTION
Instruction PIPELINE
1. Fetch 1. FI 2. DA 3. FO 4. EX
2. Decode
3. Calculate effective Address
4. Fetch the operands from memory
5. Execute
6. Store the result.
4 STAGE INSTRUCTION
PIPELINE
Pipeline Conflicts
v Resource Conflicts (Same memory access by 2 segments at
same time)
Example : 2 student wants to read same book in library and
only single book is available.
v Data Dependency : an instruction depends on result of
previous Instruction but result is not yet availabe
v Branch Conflicts arise from branch and other instructions that
change the value of PC.
How to deal with Data Dependency &
Branch conflicts?
Data Dependency Branch Conflicts
Prefetch Target
Hardware Interlocks
Instruction
Operand forwarding Branch Targe Buffer
delayed Load loop Buffer
Branch Prediction
Delayed Branch
RISC Pipeline (3-segment struction
Pipeline)
I: Instruction Fetch Example:
(Read from Memory)
A: ALU operation
(Decode first and then operate using
ALU)
E: Execute operation
(Store the result as per the decoded
Instruction)
Risc Pipeline (Data dependency
removal using Delyed Load)
Problem:
Solution:
Look at 4
Risc Pipeline (Delayed Branch)
Solution Using No-Operation Instruction
Example:
Memory Interleaving
Simultanous Access to
Memory
Instruction pipeline may
require to fetch instruction
and operand at the same
time.
Same way for Arithmetic
may require 2 or more
operands
Array Processors
Operates on large arrays of data
Attached array processor is an
auxilliary processor attached to
general purpose processor.
SIMD ARRAY PROCESSOR ORGANIZATION
Questions can be asked
Explain parallel processing.
Elaborate Flynn’s classification for computers
What is speedup? Derive the equation of speedup for k-segment pipeline processing for
task.
Explain instruction fetching, decoding and executing in pipeline processing
Explain pipelining technique. Draw the general structure of four segment pipeline.
Draw space-time diagram for 4-segment pipeline with 7 & 8 tasks
Explain pipeline processing conflict.
Compare SIMD and MIMD.
Describe SIMD array processor.
Write note on memory interleaving.
THANK you
Read Chapter 9 from
Questions?
“Computer System
Architecture” 3rd Edition
By M. Morris Mano
