Parallel Processing Basics

Introduction

Sequential processing — executing one instruction after another — has a fundamental speed limit. No matter how fast you make a single processor, there is a point where physics says "no faster." Parallel processing breaks through this barrier by using multiple processors working simultaneously on different parts of a problem. Your laptop already does this with its multi-core CPU, and supercomputers take it to extremes with millions of cores. Understanding parallel processing fundamentals helps you think about problems differently — not "how do I solve this faster?" but "how do I split this into pieces that can be solved simultaneously?"

Flynn's Taxonomy

Michael Flynn (1966) classified computer architectures by how many instruction streams and data streams they process simultaneously:

SISD (Single Instruction, Single Data)

Traditional sequential processor. One instruction operates on one data item at a time. Example: Classic single-core CPU executing instructions one by one.

SIMD (Single Instruction, Multiple Data)

One instruction operates on multiple data items simultaneously. Examples: GPU cores, Intel SSE/AVX, ARM NEON.

MISD (Multiple Instructions, Single Data)

Multiple instructions process the same data — very rare. Potential example: fault-tolerant systems where multiple processors verify the same computation.

MIMD (Multiple Instructions, Multiple Data)

Multiple processors each executing their own instruction stream on their own data. This is the most general and common parallel architecture: multi-core CPUs, clusters, distributed systems.

Measuring Parallel Performance

Speedup

Ideal (linear) speedup: S(p) = p (doubling processors halves time) Reality: Always less than ideal due to serial portions, communication, synchronization.

Efficiency

Amdahl's Law (Fixed Problem Size)

The serial fraction (1-f) is the ultimate bottleneck. Even 10% sequential code limits speedup to 10× regardless of how many processors you add.

Gustafson's Law (Scaled Problem Size)

More optimistic: as we add processors, we typically increase problem size too (more data, finer resolution). The serial portion stays constant while the parallel portion grows.

Parallel Architecture Types

Shared Memory Multiprocessor

• All processors share one address space
• Communication via shared variables (read/write same memory location)
• Challenge: Cache coherence (keeping cached copies consistent)
• Example: Any multi-core laptop or desktop

Distributed Memory (Message Passing)

• Each processor has private memory
• Communication via explicit messages (send/receive)
• No cache coherence problem (no shared memory)
• Scalable to thousands of nodes
• Example: Supercomputers, Hadoop clusters

Types of Parallelism

Data Parallelism

Same operation applied to different data:

Task Parallelism

Different operations on potentially different data:

Pipeline Parallelism

Data flows through stages, each handled by different processor:

Challenges of Parallel Computing

1. Load balancing: All processors should have equal work. If one finishes early, it sits idle.
2. Synchronization: Processors must coordinate (barriers, locks). Overhead reduces speedup.
3. Communication: Data exchange between processors takes time. Minimize it.
4. Race conditions: Two processors modifying shared data simultaneously → incorrect results.
5. Deadlock: Processor A waits for B, B waits for A → both stuck forever.
6. Diminishing returns: Amdahl's Law — adding more processors gives less benefit each time.

Real-World Parallel Processing

Key Takeaways

1. Flynn's taxonomy classifies architectures by instruction and data stream multiplicity — MIMD (multi-core) is the most common parallel architecture today
2. Amdahl's Law sets a hard limit on speedup based on the sequential fraction — optimizing parallel portions has diminishing returns
3. Shared memory is easier to program but harder to scale; distributed memory scales well but requires explicit communication
4. Data parallelism (same operation on many data) is the easiest to exploit and the most common in real applications
5. The challenge of parallel computing is not more processors — it is finding and exploiting parallelism while minimizing synchronization overhead
6. Modern systems are heterogeneous: CPU for sequential logic, GPU for data parallelism, NPU for AI — each processor type handles what it does best