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].

- Parallel Models of Computation
- Algorithmic Techniques
- Parallel Complexity Theory
- Current and Future Directions

Guy Blelloch, blelloch@cs.cmu.edu