IJUC Home • Issue Contents

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:

  1. 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.
  2. 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

Full Text (IP)