The Embarrassingly Parallel Problem
A problem is embarrassingly parallel when it breaks into pieces that need little or no communication to coordinate. Each piece runs alone, and the results just collect at the end.
What makes it easy
- The pieces are independent, sharing no mutable state.
- There is little or no synchronization during the work.
- Combining results is trivial, often just concatenation or a simple reduction.
Classic examples include rendering separate frames of a movie, applying a filter to each pixel, testing many random seeds, or running the same simulation with different parameters. Because there is almost no serial fraction, these problems scale close to linearly with processors, the dream case for Amdahl and Gustafson alike.
A word of caution
The work may be independent, but input and output can still serialize you. Reading a shared file or writing to one destination can become the bottleneck even when the computation itself is perfectly parallel.
Key idea
Embarrassingly parallel problems split into independent pieces with almost no coordination, so they scale nearly linearly unless input or output gets in the way.