Multiprocessing

Multiprocessing
An Introduction

Computer Science Department

bernstdh@jmu.edu

Review

Flow of Control:
- A sequence of control transfers (i.e., transitions between instructions/steps)
Concurrent Flows:
- Two flows, $X$ and $Y$ , are said to running concurrently iff $Y$ began after $X$ began and before $X$ finished or $X$ began after $Y$ began and before $Y$ finished
Coordination:
- Solving problems using concurrent flows often involves coordination

Parallel Flows

Parallel Multiprocessing:
- The ability to execute multiple processes simultaneously
Parallel Multithreading:
- The ability to execute multiple threads within a single process simultaneously

Hardware Architectures

Multicore Processing:
- The CPU has multiple distinct processing cores (each with its own instruction control unit, arithmetic and logical unit, and cache) capable of executing instructions
Symmetric Multiprocessing (SMP):
- Multiple interconnected CPUs within a single host sharing the same memory
Cluster Multiprocessing:
- Multiple network-interconnected hosts each with its own memory (including grid computing in which the hosts are heterogenous)

Decomposition Schemes

Tasl/Functional Decomposition:
- The problem is decomposed into different tasks involving different data that can be executed in parallel
Data/Domain Decomposition:
- The data are decomposed and the same task is performed in parallel on different pieces of data

Flynn's Taxonomy

Single-Instruction/Single-Data (SISD):
- One operation is performed on one piece of data
Single-Instruction/Multiple-Data (SIMD):
- One operation is performed on multiple pieces of data
Multiple-Instruction/Single-Data (MISD):
- Multiple operation are performed on a single piece of data
Multiple-Instruction/Multiple-Data (MIMD):
- Multiple operation are performed on multiple pieces of data

Symmetry

Symmetric Systems:
- All processors/hosts are similarly provisioned and execute the same program
Asymmetric Systems:
- Master (Coordination)/Slave (Calculation) Configurations
- Map (Calculation and Filtering)/Reduce (Synthesis) Configurations

Communication Patterns

None:
- Usually only appropriate for "embarrassingly parallel" problems
Send and Receive:
- One or both parties must block while communication takes place
Global Barrier:
- All processors/hosts must use communication to synchronize at one or more points in time
Broadcast/Scatter and/or Reduce/Gather
- One to many and/or many to one communications are used

Libraries

There's Always More to Learn