THE FAT-PYRAMID AND UNIVERSAL PARALLEL COMPUTATION INDEPENDENT OF WIRE DELAY

Authors
Citation
Ri. Greenberg, THE FAT-PYRAMID AND UNIVERSAL PARALLEL COMPUTATION INDEPENDENT OF WIRE DELAY, I.E.E.E. transactions on computers, 43(12), 1994, pp. 1358-1364
Citations number
27
Categorie Soggetti
Computer Sciences","Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture
ISSN journal
00189340
Volume
43
Issue
12
Year of publication
1994
Pages
1358 - 1364
Database
ISI
SICI code
0018-9340(1994)43:12<1358:TFAUPC>2.0.ZU;2-V
Abstract
This paper shows that a fat-pyramid of area Theta(A) requires only O(l og A) slowdown to simulate any competing network of area A under very general conditions. The result holds regardless of the processor size (amount of attached memory) and number of processors in the competing networks as long as the limitation on total area is met. Furthermore, the result is valid regardless of the relationship between wire length and wire delay. We especially focus on elimination of the common simp lifying assumption that unit time suffices to traverse a wire regardle ss of its length, since the assumption becomes more and more untenable as the size of parallel systems increases. This paper concentrates on simulation using transmission lines (wires along which bits can be pi pelined) with the message routing schedule set up offline, but it also discusses the extension to on-line simulation. This paper also examin es the capabilities of a fat-pyramid when matched against a substantia lly larger network and points out the surprising difficulty of doing s uch a comparison without the unit wire delay assumption.