Classification of
Parallel
Architecture
Designs
Level of Parallelism
✦ Job level
– between jobs
– between phases of a job
✦ Program level
– between parts of a program
– within do-loops
– between different function invocations
✦ Instruct stream level
✦ Instruction level
– between phases of instruction execution
– between instructions
✦ Arithmetic and bit level
– within ALU units
Job Level
✦ Different job phases
exp: CPU activities - I/O activities the overlapping may
be achieved by programmer visible scheduling of
resources
✦ Different jobs
OS T1 T2
CPU job 1 job 2
I/O job 2 job 1
✦ Architecture requirement:
a balanced set of replicated resources in a computer
installation.
Common
memory
Computational Input/output
processor processor
(stage 1) (stage 2)
Stage
1 Task 1 Task 2 Task 1 Task 3 ...
2 Task 2 Task 1 Task 3 Task1
Time idle time
/
CPU I/O Overlapping
Program Level Parallelism
✦ Different code sections:
– diff. procedure/functions
– diff. code blocks
✦ Different iterations for the same loop
✦ Data-dependencies and program partitioning
Instruction Level Parallelism
(ILP)
✦ Between instructions
– parallel execution of different instructions -
spatial
– key: dependency between instructions
✦ Between phases of instructions
– overlapping different suboperations - pipelining
– pipelining of a suboperations itself, e.g. ALU
pipelining
Overlay vs. Pipeline
Pipeline:
– tightly coupled subfunctions
– fixed basic stage time
– independent basic function evaluation
Overlap
– loosely coupled subfunctions
– variable basic stage time
– dependency between function evaluation
1 2 3 N
1 2 3 N
1 2 3 N
1 2 3 N
1 2 3 N
Time
Hardware design method: RT
Principles of Pipelining
Instruction Fetch
Instruction Decode
Execute
Memory Op
Register Update
Pipelining of an Instruction Execution
Instruction Instruction Instruction Results
fetch decode execution
Stage 1 1 2 3 4 5
Stage 2 1 2 3 4
Stage 3 1 2 3
Time
number i corresponds
to instruction i
Hazards
✦ Any conditions within the pipelined system that
disrupt, delay or prevent smooth flow of tasks
through the pipelines.
✦ The detection and resolution of hazards constitute
a major aspect of pipeline design
✦ Types of hazards
Flynn(72)
✦ Classification of parallel architecture is not based
on the structure of the machine, but based on how
the machine relates its instructions (streams) to the
data (stream) being processed.
A stream:
– a sequence of items { instruction
data
– being executed or operated on by a processor.
SISD + ILP
S I M D + Vector
MISD
MIMD
I L P gains increasing
attention!
SISD
✦ for practical purpose: only one processor is useful
✦ pipelining may or may not be used,
often called as serial scalar computer
SIMD
✦ (single inst stream/multiple data stream)
✦ single processor
✦ vector operations
one v-op includes many ops on a data stream
✦ both pipelined processing or array of processors
are possible
✦ Example:
CRAY -1
ILLIAC-IV
ICL DAP
IS
IS DS
I/O CU PU MU
(a) SISD uniprocessor architecture
PE1 LM1 Data
DS DS sets
IS
...
...
CU loaded
DS DS from
Program loaded host
from host PEn LMn
(b) SIMD architecture (with distributed memory)
Captions:
C = Control Unit IS
CU1 PU1
PU = Processing Unit I/O IS DS
MU= Memory Unit Shard
...
...
...
IS = Instructin Stream Memory
DS = Data Stream IS DS
I/O CU1 PUn
PE = Processing Element IS
LM = Local Memory
(c) MIMD architecture (with shared memory)
Problems of Flynn’s Scheme
✦ too broad
✦ everything in SIMD: vector machines?
✦ MISD?
✦ Relation with Parallel Programming models ?
...
IS
Memory
(program
IS
CU1
IS
CU2
IS
... CU2
IS
and data) DS PU1
DS
PU2 DS
... PU2
DS
I/O
MISD architecture (the systolic array)
Captions:
CU= Control Unit
PU = Processing Unit
MU + Memory Unit
IS = Instructin Stream
DS = Data Stream
PE = Processing Element
LM = Local Memory
Computers
Single I stream Multiple I stream
Single pipelined or
unpipelined multiple
E unit E units
MIMD
Serial Parallel
unicomputers unicomputers
The broad subdivisions in computer architecture
SISD + ILP
Unpipelined Pipelined
Vector
Multiple Only scalar Vector
E unit instructions instructions
Horizontal Issue-when- mem-mem
control ready reg-reg
CDC FPS CDC CRAY-1 CDC
6600 AP-120B 7600 Cyber-205
VLIW IBM
360/91
Parallel unicomputers based on functional
parallelism and pipelining
ILP Architectures
✦ Multiple inst /op issuing + deep-pipelining
✦ Superscalar
– Multiple inst/cycle (Power PC,MIPS10000, Intel Pentium)
✦ VLIW
– Multiple op in one inst/cycle
– ESL/polycyclic or Cydra5
– Multiflow
– Intel iA-64 architecture ?
✦ Superpipelined
– MIPS 4000/8000
– DEC Alpha (earlier versions)
✦ Decoupled Arch
✦ Multithreaded Arch
– EARTH/MTA
– Multiscalar [Sohi]
– etc.
Sources
Guang
Guang R.
R. Gao
Gao
