Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 8/28/84; site lll-crg.ARPA
Path: utzoo!watmath!clyde!bonnie!akgua!whuxlm!harpo!decvax!genrad!panda!talcott!harvard!seismo!umcp-cs!gymble!lll-crg!brooks
From: brooks@lll-crg.ARPA (Eugene D. Brooks III)
Newsgroups: net.arch,net.math
Subject: Re: topology of highly connected computer systems
Message-ID: <551@lll-crg.ARPA>
Date: Sat, 27-Apr-85 17:45:32 EDT
Article-I.D.: lll-crg.551
Posted: Sat Apr 27 17:45:32 1985
Date-Received: Mon, 29-Apr-85 00:38:26 EDT
References: <2132@sun.uucp> <1447@think.ARPA>
Distribution: net
Organization: Lawrence Livermore Labs, CRG group
Lines: 63
Xref: watmath net.arch:1128 net.math:1963

> out, but for something like the cosmic cube (64 processors?) we are only
> talking about 192 wires, (probably expensive coaxial wires), which is
> not too much of a pain to actually construct in 3-space.

The 64 processor was wired in a single backplane with wire wrap wire and
not coaxial cable.  The wiring was not even twisted pairs.  Of course it
probably would have been a lot less flakey with twisted pairs and appropo
drivers.


> I am much more interested in what happens as $n$ becomes much larger
> (e.g. $n=10^6$).  The wiring problem becomes very hard again.  The
> Connection Machine with 64K processors in the prototype faces an
> engineering challenge on this front.

A million processors not not a problem at all (Well perhaps I am stretching it
a bit.  I don't actually advocate a million processors.  I thing more along the
lines of a few hundred 20 MIP/MFLOP processors as being interesting.).  How to
construct a very large N cube can easily be worked out on the back of an
envelope.  You accomplish the feat by building and wiring the machine in 3
dimensions.  32k processors is a piece of cake (its only 32 processors on a
side) and one million processors is within the realm of possibility.

> if some node or wire fails, the machine might be able to keep running.
> (fault tolerence is important for a million processor machine)).
> Redundancy is also nice because it means that if lots of messages want
> to go from A to B, then we may be able to send more than one at a time
> through the net.
Deadlock free routing requires that a specific path be used for each
sender/reciver pair.

> One bad thing about cube topologies (at least for cubes bigger than
> about 10 dimensions) is that they do not use their bandwidth very
> effectively.  It has been claimed (with proof - references may be
> available on demand) that a 14 cube sending an "average" set of messages
> only uses about one fourth of the bandwidth because of collisions.
I would like to see the reference list, please send it to me via email.
By the same token you might send my your SNAIL MAIL address if you are
interested in a paper describing a solution to the bandwidth problem.
Request the paper titled "Shared Memory Hypercube".
The switching technque gives NlogN bandwidth, tested by simulation to N=1024,
and it adaptively removes conflicts.  My use of the network is to create a
shared memory server for a hypercube machine with CRAY style vector processors.
With simultaneous vector access by all processors the packet conflict problem
is as severe as it can be.  The network provides FULL bandwidth to all
processors simultaneously.
 
> It has been claimed, in this discussion, that cube topologies are nice
> because they can simulate other topologies easily.  Actually, this is
> not really a good argument, since most of the other seriously considered
> topologies are equally good at simulating each other
The cube topology is nice as it has other useful topologies IMBEDDED within it.
We are not talking about easy simulation here, efficient execution is the
target.  The wires is there! 
 
> I suspect that the real reason that people are building N-cubes instead
> of skewed rings, minimum spanning trees, or some other topology, is that
> computer scientists have a bias towards binary representations of
> things, and the cube topology is nice and binary, and because routing is
> so easy.
Admittedly the routing is easy, this is one of the reasons for the cubes
attractiveness.  The real reason for the interest in it however is it has
a genuine bandwidth edge over the other topologies.