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
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.