Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!ncrlnk!ncrcae!hubcap!boulder!foobar!grunwald
From: boulder!foobar!grunwald@ncar.UCAR.EDU (Dirk Grunwald)
Newsgroups: comp.parallel
Subject: Re: IPSC Communications
Message-ID: <7210@hubcap.clemson.edu>
Date: 27 Nov 89 20:39:48 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 38
Approved: parallel@hubcap.clemson.edu

>>>>> On 21 Nov 89 19:19:10 GMT, parker@vienna3.tmc.edu (Bruce Parker) said:
Bruce> In article <7142@hubcap.clemson.edu> pase@orville.nas.nasa.gov (Douglas M. Pase) writes:
>
>A lot of Intel's ideas are based (at least initially) on William Dally's PhD.
>thesis.  Grossly simplified, the idea is that one can trade the wire layout
>complexity of an n-cube arrangement for higher bandwidth connections (more +
>shorter wires) in a grid/torus.  Most important, he shows that such trades
>favor the 2d arrangements.  With a simple argument it is easily shown that
>a grid/torus constructed in that way has lower latency and contention than
>an n-cube, *even for problems which prefer an n-cube*.

Bruce> How is it possible for a sqrt(n) by sqrt(n) mesh with
Bruce> O(sqrt(n)) diameter and bisection width to have lower
Bruce> latency and contention than an n-node hypercube with O(lg n)
Bruce> diameter and O(n) bisection?  Is the analysis specialized
Bruce> for certain problems as opposed to examining a worst- or
Bruce> even average-case?

---

In a single phrase, ``fat wires''.  The argument being that 8 wires
transmit the info. of 1 at 8x the speed.  Thus, the latency of the
*last byte* (not first) decreases because of increased bandwidth. The
software setup is the same for 1-wire hypercube or n-wire mesh.

The cut-through time per hop is going to be about the same - fairly small.
You'll get more hops with the torus, but not that many more, on average.
Actually, dally is now advocating a 3-D mesh, not a simple 2-D torus.
A mesh also gets you wire locality. This is important from physical
perspectives of short interconnects, lower cap's & higher bandwidths.

Of course, once you go to optic interconnects with electronic
computers, it doesn't matter & you'll probably see the hypercube win
out again. The entire argument is rooted in extant technology, not
theoretical niceness.

Dirk Grunwald -- Univ. of Colorado at Boulder	(grunwald@foobar.colorado.edu)
						(grunwald@boulder.colorado.edu)


Brought to you by Super Global Mega Corp .com