Parallel Processing
&
Instruction Pipelining
Parallel Processors
Levels of Parallel Processing
Instruction Level
Loop Level
Procedure Level
Program Level
Classification of Parallel Processing
• Flynn’s Classification (1966)
• It is based on the multiplicity of instruction stream and data streams in a
computer system.
• SISD, SIMD, MISD, MIMD
Flynn’s Classification
Types of Flynn’s Taxonomy
+
Multiple Processor Organization
• Single instruction, single data (SISD) stream • Multiple instruction, single data
• Single processor executes a single instruction (MISD) stream
stream to operate on data stored in a single • A sequence of data is
memory transmitted to a set of
processors, each of which
• Uniprocessors fall into this category executes a different instruction
sequence
• Not commercially implemented
• Single instruction, multiple data • Multiple instruction, multiple data (MIMD)
(SIMD) stream stream
• A single machine instruction • A set of processors simultaneously execute
controls the simultaneous
execution of a number of different instruction sequences on different
processing elements on a data sets
lockstep basis • SMPs, clusters and NUMA systems fit this
• Vector and array processors fall category
into this category
© 2016 Pearson Education, Inc., Hoboken, NJ. All rights
reserved.
Processor Organizations
Single Instruction, Single Instruction, Multiple Instruction, Multiple Instruction,
Single Data Stream Multiple Data Stream Single Data Stream Multiple Data Stream
(SISD) (SIMD) (MISD) (MIMD)
Uniprocessor
Vector Array Shared Memory Distributed Memory
Processor Processor (tightly coupled) (loosely coupled)
Clusters
Symmetric Nonumiform
Multiprocessor Memory
(SMP) Access
(NUMA)
Figure 17.1 A Taxonomy of Parallel Processor Architectures
© 2016 Pearson Education, Inc., Hoboken, NJ. All rights
reserved.
IS DS DS
CU PU MU PU1 LM1
(a) SISD DS
PU2 LM2
IS
CU
IS DS DS
CU1 PU1 PUn LMn
IS DS (b) SIMD (with distributed memory)
CU2 PU2
Memory
Shared
IS DS
CU1 PU1 LM1
Interconnection
IS DS IS DS
Network
CUn PUn CU2 PU2 LM2
(c) MIMD (with shared memory)
CU = control unit SISD = single instruction,
IS = instruction stream single data stream IS DS
PU = processing unit SIMD = single instruction, CUn PUn LMn
DS = data stream multiple data stream
MU = memory unit MIMD = multiple instruction, (d) MIMD (with distributed memory)
LM = local memory multiple data stream
Figure 17.2 Alternative Computer Organizations
© 2016 Pearson Education, Inc., Hoboken, NJ. All rights
reserved.
SISD Computers
Contd…
SIMD Computers
Contd…
MISD Computers
Contd…
MIMD Computers
Contd…
Parallel Processing in Memory
Shared Memory Architecture
Contd…
Uniform Memory Access
UMA Multiprocessor Model
Non-Uniform Memory Access (NUMA)
Contd…
Cache-Only Memory Architecture (COMA)
Shared Memory Architecture
Distributed Memory Architecture
Distributed Memory System
Contd…
Hybrid Architecture
Instruction Pipelining
• In this a stream of instructions can be executed by overlapping
fetch, decode and execute phases of an instruction cycle.
• This type of technique is used to increase the throughput of the
computer system.
• An instruction pipeline reads instruction from the memory
while previous instructions are being executed in other
segments of the pipeline.
• Thus we can execute multiple instructions simultaneously.
• The pipeline will be more efficient if the instruction cycle is
divided into segments of equal duration.
Contd…
Pipelining Case: Laundry
Non Pipelined Laundry
Pipelined Laundry
Instruction Pipeling
• In the most general case computer needs to process each
instruction in following sequence of steps:
1. Fetch the instruction from memory (FI)
2. Decode the instruction (DA)
3. Calculate the effective address
4. Fetch the operands from memory (FO)
5. Execute the instruction (EX)
6. Store the result in the proper place
Instruction Pipelining without no branch
operations
Instruction Pipelining with branches
Advantages
Can pipelining be a trouble? Why?