🚀 go-pugleaf

In article <1157@ucbcad.BERKELEY.EDU> faustus@ucbcad.BERKELEY.EDU (Wayne A. Christopher) writes:
>Maybe I'm missing something, but why is the cost of interconnect in a 
>hypercube O(n^2) instead of O(n log n)?  I can understand that in 2D
>you can't just connect each processor to its log n "nearest neighbors"
>because they aren't so near anymore, but why should the cost be quadratic?

See Ullman's COMPUTATIONAL ASPECTS OF VLSI for a real proof.  In very crude
terms, the idea is to consider a box containing N processors and a hypercube
network.  Draw a vertical line splitting the box, with half the processors on
one side and half on the other.  Now, the hypercube is a "global parallel"
interconnect, which allows each processor on one side of the dividing line to
have a circuit to a processor on the other side of the line.  Thus, we must
have N/2 circuits crossing the dividing line.  Since there are only a small
finite number of levels in which wires can run, this means the the length of
the splitting vertical line is O(n) - ie the height of the box is O(n).  A
similar argument shows that the width of the box is O(n).  Thus, the size of
the box is O(n^2).

This is of course just a crude sketch - again, see Ullman's book for a real
proof.
						Ehud Reiter
						reiter@harvard	(ARPA,UUCP)