William Stallings

Computer
Organization
and Architecture
8th Edition
Chapter 17
Parallel Processing
Multiple Processor
Organization

• Single instruction, single data stream - SISD

• Single instruction, multiple data stream -
SIMD
• Multiple instruction, single data stream -
MISD
• Multiple instruction, multiple data stream-
MIMD
Single Instruction, Single
Data Stream - SISD

• Single processor
• Single instruction stream
• Data stored in single memory
• Uni-processor
 • Single machine instruction
• Controls simultaneous execution
Single • Number of processing elements
Instruction, • Lockstep basis
• Each processing element has associated data
Multiple Data memory

Stream - SIMD • Each instruction executed on different set of data by

different processors
• Vector and array processors
Multiple • Sequence of data
• Transmitted to set of processors
Instruction, • Each processor executes different instruction
sequence
Single Data • Never been implemented
Stream - MISD
Multiple • Set of processors
• Simultaneously execute different instruction
Instruction, sequences
• Different sets of data
Multiple Data • SMPs, clusters and NUMA systems
Stream- MIMD
Taxonomy of
Parallel
Processor
Architectures
 • General purpose processors
MIMD - • Each can process all instructions necessary

Overview • Further classified by method of processor

communication
 • Processors share memory
• Communicate via that shared memory
Tightly Coupled - • Symmetric Multiprocessor (SMP)
• Share single memory or pool
SMP • Shared bus to access memory
• Memory access time to given area of memory
is approximately the same for each processor
Tightly Coupled - • Nonuniform memory access
• Access times to different regions of memory may
NUMA differ
 • Collection of independent uniprocessors or SMPs
Loosely Coupled • Interconnected to form a cluster

- Clusters • Communication via fixed path or network

connections
Parallel Organizations - SISD
Parallel Organizations - SIMD
Parallel Organizations - MIMD Shared
Memory
Parallel Organizations - MIMD
Distributed Memory
 • A stand alone computer with the following
characteristics
• Two or more similar processors of comparable
capacity
• Processors share same memory and I/O
• Processors are connected by a bus or other
internal connection
• Memory access time is approximately the same
Symmetric for each processor
• All processors share access to I/O
Multiprocessors • Either through same channels or different
channels giving paths to same devices
• All processors can perform the same functions
(hence symmetric)
• System controlled by integrated operating system
• providing interaction between processors
• Interaction at job, task, file and data element
levels
Multiprogramming and Multiprocessing
 • Performance
• If some work can be done in parallel
• Availability
• Since all processors can perform the same
functions, failure of a single processor does not
halt the system
SMP Advantages • Incremental growth
• User can enhance performance by adding
additional processors
• Scaling
• Vendors can offer range of products based on
number of processors
Block Diagram of Tightly Coupled
Multiprocessor
 • Time shared or common bus
Organization • Multiport memory
Classification • Central control unit
 • Simplest form
• Structure and interface similar to single processor
system
• Following features provided
• Addressing - distinguish modules on bus
Time Shared Bus • Arbitration - any module can be temporary
master
• Time sharing - if one module has the bus,
others must wait and may have to suspend
• Now have multiple processors as well as multiple
I/O modules
Symmetric Multiprocessor Organization
 Time Share Bus - Advantages

Simplicity Flexibility Reliability

 • Performance limited by bus cycle time

Time Share Bus - • Each processor should have local cache

• Reduce number of bus accesses
Disadvantage • Leads to problems with cache coherence
• Solved in hardware - see later
 • Simultaneous concurrent processes
• Scheduling
Operating • Synchronization
• Memory management
System Issues • Reliability and fault tolerance
 • Problem - multiple copies of same data in different
Cache caches
• Can result in an inconsistent view of memory
Coherence and • Write back policy can lead to inconsistency
MESI Protocol • Write through can also give problems unless caches
monitor memory traffic
 • Compiler and operating system deal with problem
• Overhead transferred to compile time
• Design complexity transferred from hardware to
Software software
• However, software tends to make conservative
Solutions decisions
• Inefficient cache utilization
• Analyze code to determine safe periods for caching
shared variables
 • Cache coherence protocols
• Dynamic recognition of potential problems
• Run time
Hardware • More efficient use of cache
• Transparent to programmer
Solution • Directory protocols
• Snoopy protocols