🚀 go-pugleaf

I'm interested to know if anyone has used Sigma networks for transputers.
I first heard of them at the Occam User Group at Southampton in Sep 88,
but I've forgotten who mentioned them.

Basically, they give you a network of 2-to-the-n processors, with 4 links
each, and a maximum distance between processors of n. This compares with
a hypercube's requirement of n links per processor.
Unfortunately you don't get this for free, because the *average* message
distance is higher, and routing is not so simple.
As a bonus though, the connections leave some links unused so that
you can connect something else to the network!
As you can see, these could be very useful for transputer systems.

I will briefy describe how to create these.
Suppose we have n=4 (i.e. 16 processors). Then each processor is numbered
in binary with n bits: ABCD.  This processor is connected to four other
processors, whose numbers are found by shifting ABCD either right or left,
and adding a 0 or a 1. So ABCD is connected to 0ABC, 1ABC, BCD0, BCD1.

You notice that if ABCD = 0000, then it connects two links back to itself,
which is where the spare links come from.

If you draw out one of these networks, they tend to look pretty irregular,
but here's the n=3 picture:

    001---------011
   / | \       / | \
000  |  010=101  |  111     (both 000 and 111 have their other 2 links
   \ | /       \ | /         connected together)
    100---------110

I haven't attempted to draw a 64 processor network, but you can use the
fact that there's a lot of symmetry in there (vertical, horizontal, and
rotational) to help draw them.

A simplistic way to route a message is to slowly shift the bits of the
destination address into the current address. This will almost always
take n steps, so it is not very efficient.

EG. to get from 000 to 101, shift the 000 right and shift in the rightmost
bit of the destination to get to 100. Then shift in the middle bit of the
destination to get to 010. Finally you get to 101 in 3 steps.
Hence it is easy to see that you can always get from any processor
to any other in n steps. The trick is to make use of the higher
connectivity to reduce the number of hops.
Also this simple method has the disadvantage that it doesn't fully use
all of the links, for example all messages leaving node ABC will go to
either 0AB or 1AB, without using BC0 or BC1. 

There would be a lot of scope for recognising sub-strings within the
addresses and using that to reduce the number of hops, but I haven't
been able to give this a lot of thought. It would become very
important as you increased the number of nodes.
This might also make better use of all four links leaving each processor.
For example, with n=10, sending a message from 1010110101 to 1010111111
would take 10 steps if you did it that simple way, or you could shift
in 11111 from the right instead, in 5 steps. Alternative you could use 
a mixture of shifts, if the common pattern was in the middle of the 
bit-pattern. So you could get from 0111111110 to 1111111111 by going to:
111111110x, 1111111110, 1111111111. (where x is any value)

Anyway, has anyone actually used one of these?

Incidently, they are not restricted to 4-way nodes. If you had 8 links,
simply number the nodes in base 4, ie. ABCD is connected to 
0ABC, 1ABC, 2ABC, 3ABC, BCD0, BCD1, BCD2, BCD3.
Similarly for any *even* number of links.

The person at the Occam User Group was actually discussing his work
on finding other networks with better values for maximum distance verses
number of processors and valency (number of links).
I vaguely remember him reporting a network of distance 10, with over
10,000 processors, but I can't remember whether that was valency 4 or 10.
Does anyone have any similar graph-theoretic results?
-- 
Conor O'Neill, Software Group, INMOS Ltd.    conor@inmos.co.uk
Disclaimer: All views are my own, not those of INMOS.