Parallel Processing
Why use one processor when you can use many? Parallel processing uses multiple processors to solve problems faster. From your smartphone's multi-core CPU to massive supercomputers, parallelism is everywhere!
Flynn's Taxonomy
Computer architectures are classified based on how they handle instruction and data streams:
Flynn's Taxonomy
+---------------------------------------------+
| |
| 1. SISD (Single Instruction, Single Data) |
| Traditional single-core processor |
| [CPU]--->[Memory] |
| |
| 2. SIMD (Single Instruction, Multiple Data)|
| One instruction operates on many data |
| [CPU]--->[D1][D2][D3][D4] |
| |
| 3. MISD (Multiple Instruction, Single Data)|
| Rare - multiple processors on one data |
| [CPU1]--->[D] |
| [CPU2]--->[D] |
| |
| 4. MIMD (Multiple Instruction, Multiple Data)|
| Independent processors on different data|
| [CPU1]--->[D1] |
| [CPU2]--->[D2] |
+---------------------------------------------+
Types of Parallelism
- Bit-Level Parallelism: Increasing word size (8-bit → 16-bit → 32-bit → 64-bit)
- Instruction-Level Parallelism: Pipelining, superscalar, VLIW
- Data-Level Parallelism: SIMD, vector processing, GPUs
- Task-Level Parallelism: Multiple threads/processes running simultaneously
Amdahl's Law
How much speedup can we expect from parallelism? Amdahl's Law gives us the answer:
Amdahl's Law
+---------------------------------------------+
| |
| 1 |
| Speedup = ------------------------- |
| (1 - f) + (f / p) |
| |
| Where: |
| f = fraction of code that is parallelizable|
| p = number of processors |
| |
| Example: If 90% of code can be parallelized|
| with 100 processors: |
| Speedup = 1 / (0.1 + 0.9/100) |
| = 1 / 0.109 = 9.17x |
| |
| Even with infinite processors, max speedup |
| is limited by the serial portion! |
+---------------------------------------------+
Challenges of Parallelism
- Synchronization: Coordinating access to shared resources
- Communication Overhead: Processors need to exchange data
- Load Balancing: Keeping all processors busy
- Programmability: Parallel programming is harder than serial
- Amdahl's Law: Speedup limited by serial portion