🚀 go-pugleaf

        In response to the enquiry by C. O'Neill, 30-1-89, I think that these
are a variant of the perfect shuffle inteconnnection first presented by H.S. 
Stone in 1971. This pattern looks a lot more familiar than the graph shown 
in the message, but is topologically equivalent. 
        
        I am using this interconnection at present, with 16 transputers 
mounted on four B012 motherboards, and have found it quite tricky to wire up,
because the motherboards have hardwire connections for some of the links, and
I have had to find four disjoint 'runs' of processors in the interconnection 
pattern. 
        
        As to routing algorithms, I had a rummage through the literature a few
months ago, but apart from the obvious algorithm came up with nothing. However
ther is a vast North American research effort on network topologies, so 
there may well be a paper buried in there somewhere.

        Another way of viewing the topology is as two bi-directional binary
trees, meshed together in a slightly tricky way. The two root nodes are the
the processors, one down from the top, and one up from the bottom of the 
standard diagram. (This diagram is : split the processors into 'fronts' and
'backs', then draw a column of 'fronts' each with two wires emanating from
them, connected to a column of 'backs'. Number the processors from top to 
bottom.) This view suggests clever ways of routing the data, but I haven't
actually managed to produce an appropriate algorithm.

        Your question about optimal graphs for fixed valencies, is also of
interest. I would also love to know if there is an answer.

        The topic appeared to be an unsolved question in graph theory, in the
late 1970s, see Bollobas, 'Extremal Graph Theory', (Chapter 5 I think...), 
but perhaps an answer has been found by now.

        By the way, the problem is cast in Bollobas as finding the best pattern 
of direct flights between a set of airports, in such a way as to minimise the 
average flight time between airports, where indirect flights are defined 
as a concatenation of direct flights, and the number of flights leaving or 
ending at any one airport is limited. Obviously, the airports correspond to 
processors, and direct flights to links! 

Mary Shapcott,
Department of Computing Science,
University of Ulster at Jordanstown,
Co. Antrim BT37 0QB
tel : (0232) 365131 ext. 2671

References :

Stone H.S., 1971. "Parallel Processing with the Perfect Shuffle"
        I.E.E.E. Transactions on Computers, Vol 20, No.2, pp 153-161

Parker D.S., 1980. "Notes on Shuffle/exchange-type Switching Networks"
        I.E.E.E. Transactions on Computers, Vol C-29, pp 213-222.