Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!amdcad!sun!pitstop!sundc!seismo!uunet!mcvax!ukc!harrier.ukc.ac.uk!eagle.ukc.ac.uk!icdoc!inmos!conor From: conor@inmos.co.uk (Conor O'Neill) Newsgroups: comp.sys.transputer Subject: Sigma networks Message-ID: <729@brwa.inmos.co.uk> Date: 26 Jan 89 10:56:13 GMT Reply-To: conor@inmos.co.uk (Conor O'Neill) Organization: INMOS Limited, Bristol, UK. Lines: 77 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.