Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!shadooby!samsung!uunet!ncrlnk!ncrcae!hubcap!wen-king
From: wen-king@csvax.caltech.edu (Wen-King Su)
Newsgroups: comp.parallel
Subject: Re: IPSC Communications
Message-ID: <7193@hubcap.clemson.edu>
Date: 27 Nov 89 13:31:45 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 42
Approved: parallel@hubcap.clemson.edu

In article <7159@hubcap.clemson.edu> you write:
>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*.
>
<How is it possible for a sqrt(n) by sqrt(n) mesh with
>O(sqrt(n)) diameter and bisection width to have lower
<latency and contention than an n-node hypercube with O(lg n)
>diameter and O(n) bisection?

To make the comparison fair, a channel for a 2d grid has O(sqrt(n))
times more wires than a channel for an n-cube.   Latency goes down
because the tail end of a message reaches the destination O(sqrt(n))
times earlier for the grid than for the n-cube.  Throughput for random
message traffic is at least as good as n-cube's because, for that case,
the throughput is bounded by the number of wires crossing the bisection.

When Bill Dally first proposed the idea of low dimension torus, he
was met with a lot of skeptism among members of the group because we
are all used to one way of thinking about networks.  One major
difficulty at the time was the potential for message-routing deadlock in
a torus network, but he came up with a channel-sharing mechanism to avoid
deadlock.  My first connection to this issue is that I ran several
hundred simulations on Bill Dally's torus networks and on n-cube networks
under various conditions.  The results from the simulation changed the
way the rest of us feel about torus.

The idea of grids did not arise until a little later.  We missed it
because we were only looking for periodic networks (all nodes are
identical).  My second contribution was to point out that grids would
do better than torus because its channels are twice as wide as a torus's,
and because a simpler deadlock-free routing method exists for the grid.
There are other advantages, but this was the spark and the idea of torus 
was quickly dropped in favor of grids.  From that point on, the ideas
of grids began to diffuse into the industry.  Symult was first, than
comes Intel.


Brought to you by Super Global Mega Corp .com