Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/17/84; site think.ARPA
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!ihnp4!think!bradley
From: bradley@think.ARPA (Bradley C. Kuszmaul)
Newsgroups: net.arch,net.math
Subject: topology of highly connected computer systems
Message-ID: <1447@think.ARPA>
Date: Fri, 26-Apr-85 10:27:13 EST
Article-I.D.: think.1447
Posted: Fri Apr 26 10:27:13 1985
Date-Received: Sat, 27-Apr-85 05:20:36 EST
References: <2132@sun.uucp>
Reply-To: bradley@think.UUCP (Bradley C. Kuszmaul)
Distribution: net
Organization: Thinking Machines, Cambridge, MA
Lines: 70
Xref: watmath net.arch:1121 net.math:1956
Summary: 

Of course the "triangular" extensions are totally connected, which
really makes them very interesting or very boring depending on your
point of view.

They are interesting in that it is very easy to do routing, since
everything is connected.  The software for a totally connected computer
is easy, and easy software (being an oxymoron) is interesting.

They are boring in that you can't implement them for very large nets.
In general if you have $n$ processors, you need $n^2$ wires to
completely connect them and $n-1$ connections (ports) at each processor.
The wire milage quickly gets out of hand as $n$ grows, and the layout
becomes tricky also.

In a cube containing $n=2^m$ processors (i.e. an $m$-cube), there are
$m$ ports on each processor, hence $nm/2$ wires (i.e. $O(n\log n)$)
which is much better than $n^2$.  This is still a lot of wires to lay
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.

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.

One nice thing about cube topologies is that they are easy to perform
routing on (the relative address says which dimensions to cross, and
there is a wire crossing every dimension from every node) and they are
fairly redundant (there are lots of ways to get from A to B, so that 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.

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.

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

(Handwaving proof:  Suppose topology X can be easily simulated on a
cube.  There must be an "easy" mapping from the nodes in X to the nodes
in the cube (i.e.  an enumeration, since the nodes in the cube have an
"easy" mapping from themselves to their addresses).  This "easy" mapping
should be bijective, or we will be wasting computational resources.
"Easy" bijective mappings should be easy to invert, so the cube can be
simulated on X "easily".  Thus if X and Y can be simulated easily on
a cube, then X and Y can easily simulate each other.)

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.  (routing is easy because if $a$ is the absolute address of
processor $X$ and $b$ is the absolute address of processor $Y$, then
 $A \xor B$ is the relative address of B from A (and A from B)

-Brad


-- 
bradley@think.uucp  (i.e. {decvax!cca,ihnp4!mit-eddie}!think!bradley)
bradley@THINK.ARPA