Parallelism: An Overview
Parallelism runs many operations at once; the three broad forms are data, task, and pipeline parallelism, each suited to different workloads.
Concurrency versus parallelism
Concurrency is structuring a program as independent activities that may make progress in overlapping time windows. Parallelism is actually executing multiple activities simultaneously on separate hardware. A program can be concurrent without being parallel (time-sliced on one core) and parallel without much explicit concurrency (a vectorized loop).
Three broad patterns
- Data parallelism: apply the same operation to many data elements at once
- Task parallelism: run different operations on different processors
- Pipeline parallelism: stream data through a chain of stages, each running concurrently
Levels of parallelism
Parallelism exists at several granularities. At the finest, instruction-level parallelism lets a CPU issue several instructions per cycle. Above that, SIMD vector units apply one instruction to many data lanes. Thread-level parallelism uses multiple cores in shared memory, and process-level parallelism spans nodes with message passing. Large applications combine all of these.
Where speedup comes from and where it stops
The maximum speedup is bounded by the fraction of work that must run serially, formalized by Amdahl's law. When problem size grows with processor count, the more optimistic Gustafson's law applies. Communication, synchronization, and load imbalance all erode ideal speedup.
Choosing a pattern
The right pattern follows the structure of the problem. Grid-based physics maps naturally to data parallelism with domain decomposition; independent parameter scans map to task parallelism; and staged workflows such as read-transform-write map to pipelines. Real codes mix patterns and hierarchies to match the machine.