Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!ll-xn!mit-eddie!husc6!endor!reiter
From: reiter@endor.harvard.edu (Ehud Reiter)
Newsgroups: comp.arch
Subject: Re: Connection Machine Argument
Message-ID: <833@husc6.UUCP>
Date: Sat, 6-Dec-86 16:16:04 EST
Article-I.D.: husc6.833
Posted: Sat Dec  6 16:16:04 1986
Date-Received: Sun, 7-Dec-86 03:45:59 EST
References: <745@husc6.UUCP> <246@think.COM> <827@husc6.UUCP> <1157@ucbcad.BERKELEY.EDU>
Sender: news@husc6.UUCP
Reply-To: reiter@endor.UUCP (Ehud Reiter)
Distribution: na
Organization: Aiken Computation Lab, Harvard University
Lines: 22

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)