[net.arch] Cube designs vs. x,y,z bus. What is it?

jerry@oliveb.UUCP (Jerry Aguirre) (03/02/85)

An explaination of what we are talking about was requested so I will
include it here.  Other readers can skip this article.

This series of articles is discussing buss verses hypercube designs.
What are they?  Well they are ways of connecting large numbers of
processors (computers) together so that they can work together on some
problem that is to big for a single computer.  A buss topology connects
many processors to a common communications medium (like an ethernet) and
looks like this:

	p1	p2	p3	p4	p5	...
	|	|	|	|	|	|
	=========================================

The buss must be shared by all the processors as it can only handle 1
message at a time.  Accesses to it must be arbitrated by some sort of
scheduling algorithm.  Simply put this means that if processor 1 (p1)
needs to send a message to p3 it may have to wait until p2 is done using
the bus.

The hyper-cube design uses dedicated channels to connect each processor
to another.  It looks something like this:

	p1-----p2-----p3
	| \  / | \   /|
	|  \/  |  \ / |
	|  /\  |  /\  |
	| /  \ | /  \ |
	p4-----p5-----p6

There is no need to arbitrate a channel because it is not shared.
However you can see that connecting every processor to every other
processor can use a lot of wires.  In this example p1 is not connected
to p3 and p6 because it would have been to hard to show.  In a real
computer it would also be hard to do.  In practice only some of the
connections are made and the rest are forwarded thru intermediate
machines.  So, if p1 wishes to communicate with p6 it sends the message
to p5 with a request to forward it to p6.  It turns out that there is a
way of connecting the processors where 2**N processors only need N
connections each.  This is the Hyper-cube design.

				Jerry Aguirre @ Olivetti ATC
{hplabs|fortune|idi|ihnp4|tolerant|allegra|tymix}!oliveb!jerry

brooks@lll-crg.ARPA (Eugene D. Brooks III) (03/06/85)

If you are going to explain what a hypercube is you should get the topology
correct.  This topology is very important.

A hypercube is composed of { 2 sup n } processors.  n is called the order of
the hypercube.  A hypercube of order n+1 is constructed by taking two of
order n and placing them side by side connecting pairs of processors like so.

order 0		p0		/* Bet you didn't that there are a lot of
				hypercubes out there already *?

order 1		p0---p1

order 2		p0---p1
		|    |
		|    |
		p2---p3

order 3		p0-----p1
		| \    | \
		|  p4--|--p5
		|  |   |  |
		p2-----p3 |
		  \|     \|
		   p6-----p7

By inspection of the processor numbers you can discover the master plan.
The processors run from 0 to N-1 where N is some power of 2.  Each processor
is connected to all of the processors whose index differs in one and only
bit.  The position of the differing bit is the port which the two processors
are connected with.