PARALLEL COMPUTERS AND PARALLEL ALGORITHMS

RICHARD P. BRENT

Abstract

The era of serial computation, typified by Von Neumann computers and Turing machines, is coming to an end. Parallel computation is now central to Computer Science, and its importance will increase in the future.

We discuss the motivation for parallel computation (physical constraints on serial computation, biological examples of parallel computation). We describe some practical parallel computer architectures – tightly coupled synchronous machines, loosely coupled asynchronous networks, shared memory and local memory machines, hypercubes and systolic arrays. Concepts such as the speedup and efficiency of parallel algorithms are defined and illustrated by some examples.

Comments

Presented as a Forsythe memorial lecture, Department of Computer Science, Stanford University, February 1990; and as an invited lecture at the fourteenth Australian Computer Science Conference, Sydney, February 1991. Related papers are [1, 2, 3].

References

1. R. P. Brent, “Parallel algorithms in linear algebra”, Proceedings Second NEC Research Symposium (Tsukuba, Japan, August 1991), invited paper, to appear. Available as Report TR-CS-91-06, CSL, ANU, August 1991, 17 pp. rpb128.

2. R. P. Brent, “The Linpack benchmark on the AP 1000”, Proc. Frontiers ’92 (McLean, Virginia, October 1992), IEEE Press, 1992, 128–135. ISBN 0-8186-2772-7. rpb130.

3. R. P. Brent and P. E. Strazdins, “Implementation of the BLAS level 3 and Linpack benchmark on the AP 1000”, Fujitsu Scientific and Technical Journal 29, 1 (March 1993), 61–70. rpb136.

Computer Sciences Laboratory, Australian National University, Canberra, ACT 0200 E-mail address: rpb@cslab.anu.edu.au

1991 Mathematics Subject Classification. Primary 65Y05; Secondary 65F05, 65F15, 65Y10, 65Y20, 68M07, 68Q05, 68Q22, 68Q35.

Key words and phrases. Parallel computation, parallel algorithms, parallel computers, SIMD, MIMD, shared memory, local memory, hypercube, systolic array, linear algebra, Linpack benchmark.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1990, 1993, R. P. Brent.

rpb125a typeset using AMS-L^{A}TEX