Unconventional Wisdom: Superlinear Speedup and Inherently Parallel Computations
Selim G. Akl
A number of unconventional computational problems are described in which parallelism plays a fundamental role. These problems highlight two recently uncovered aspects of parallel computation:
- There exist computations for which the running time of a parallel algorithm, compared to that of the best sequential algorithm, shows a speedup that is superlinear in the number of processors used, a feat that was previously believed to be impossible.
- There exist inherently parallel computations, that is, computations that can be carried successfully in parallel, but not sequentially.
A surprising consequence of these discoveries is that the concept of universality in computation, long held as a basic truth, is in fact false.
Keywords: Models of computation; inherently parallel computations; unconventional computations; superlinear speedup; superlinear slowdown; universality