next up previous
Next: Parallel Models of Computation Up: A Brief Overview of Previous: A Brief Overview of

Parallel Algorithms

As more computers have incorporated some form of parallelism, the emphasis in algorithm design has shifted from sequential algorithms to parallel algorithms, i.e., algorithms in which multiple operations are performed simultaneously. As a consequence, our understanding of parallel algorithms has increased remarkably over the past ten years. The most important developments in the field have occurred in three broad areas: parallel models of computation, parallel algorithmic techniques, and parallel complexity theory. This chapter surveys these three areas. So many parallel algorithms have now been designed that a chapter of this length cannot cover even a small fraction of them. Hence, this chapter does not discuss individual algorithms in any detail. The interested reader should consult the following texts: [2, 3, 4, 5, 6, 7].

Guy Blelloch,