The Divide And Conquer Parallelism
Many parallel algorithms share one shape: divide the problem into smaller independent pieces, conquer each piece, then combine the results. The independence of the pieces is exactly what makes them parallelizable.
Why it parallelizes well
Each recursive split creates subproblems that share no data, so they can run as separate tasks at the same time:
- The recursion tree is wide, exposing many tasks quickly.
- Sibling subproblems carry no dependency on each other.
- Only the combine step joins their results.
The span follows the depth of the recursion, often logarithmic, while the work matches the serial algorithm. This gives high parallelism for sorting, prefix sums, and tree traversals.
The combine step
The combine often decides the span. A cheap combine keeps the span shallow, while an expensive serial combine, like a serial merge, can dominate and must itself be parallelized for the best results.
Key idea
Divide and conquer exposes many independent subproblems that run in parallel, and the cost of the combine step often sets the span.