HORIZONS OF PARALLEL COMPUTATION

This paper considers the ultimate impact of fundamental physical limit ations-notably, speed of light and device size-on parallel computing m achines. Although we fully expect an innovative and very gradual evolu tion to the limiting situation, we take here the provocative view of e xploring the consequences of the accomplished attainment of the physic al bounds. The main result is that scalability holds only for neighbor ly interconnections, such as the square mesh, of bounded-size synchron ous modules, presumably of the area-universal type. We also discuss th e ultimate infeasibility of latency hiding, the violation of intuitive maximal speedups, and the emerging novel processor-time tradeoffs. (C ) 1995 Academic Press, Inc.