Type Architectures, Shared Memory, and the Corollary of Modest Potential

Manabrea' s remark, referring to a design option for Babbage' s Analytical Engine, has been cited (Hockney & Jesshope 198 1) as the earliest reference to parallelism in computer design. The fact that Babbage considered parallelism allows us to conj ecture that nearly a century and a half ago he understood the obvious, but nevertheless, Fundamental Law of Parallel Computation: A parallel solution utilizing p processors can improve the best sequential solu­ tion by at most a factor of p. T his law's truth follows from the observation that a speedup greater than a factor of p implies the existence of a better sequential solution. It provides an upper limit on achievable performance that has been difficult to approach in practice, much less to achieve. After only two decades of serious study (Hockney & Jesshope 198 1) and only preliminary analysis of the limits to speedup (Hwang & Briggs 1984 , p. 28) , it is certainly premature to be pessimistic about our ultimate success at attaining the maximum predicted benefits of parallelism. Still, there are reasons to be cautious. As a practical matter the scientific and commercial problems that are most in need of speedup are the so-called compute-bound problems (Bardon & Curtis 1983) since the I/O-bound problems would yield to better data transmission technology not more processing capability (Boral & DeWitt