Efficiency in parallel computation: algorithms, emulations, and VLSI pins
Kevin J. Rappoport · 1993
Communication effects seem to be the dominant limiting factor in constructing massively-parallel supercomputers. In this thesis we study the effects of communications on efficient parallel computation and present general methods for obtaining lower bounds on (1) communication-induced slowdown for efficient parallel computations, and (2) pin requirements for efficient redundant VLSI packaging of networks. The methods rely on viewing both communication patterns and network machines as hypergraphs, and measuring the communication content of computations and the communication capability of machines by applying graph invariants with special properties. We introduce three such graph invariants; communication bandwidth, partition cutwidth, and dissemination rate. They are used to obtain lower bounds on the slowdown of efficient emulations between network machines and algorithm executions, and to provide lower bounds on the pin requirements of hardware-efficient real-time VLSI emulations of network machines. Communication bandwidth is used to show intuitive lower bounds on slowdown for efficient emulations of the Cube-Connected-Cycles, DeBruijn Graph, Shuffle-Exchange and other machines, and to present intuitive slowdown results for several algorithms. Partition cutwidth is used to show that the Multibutterfly cannot be efficiently emulated without slowdown on Butterflies, DeBruijn Graphs, and other Hypercube-derived Networks, and to present evidence of an entire hierarchy of machines below expander graphs. Finally, dissemination rate is used to show new slowdown results for efficient emulations of the Mesh of Trees on Meshes and Tori. The partition cutwidth also provides lower bounds on VLSI pin requirements for a particularly strong notion of VLSI packaging of networks. The packaging strategy is more general than simply partitioning the network into chips. Rather, it is based on VLSI emulations in which a single guest processor may be replicated several times throughout the chip set. The only restrictions are that (1) the emulation outputs be tick-for-tick indistinguishable from the actual network machine outputs, and (2) the VLSI emulation uses at most a constant factor more processors than the actual network. Additionally, we show several new matching upper bounds in the form of Universal Building Block constructions.