Just Plane Fast
A small Kautz graph is easy to understand. Each node in a degree three graph has three wires out and three wires back in. There are obvious symmetries, albeit not the traditional ones. For example, the path from node A to node B is not the same as the path from node B back to node A. It is known that the number of nodes in a Kautz graph is exponential in the diameter, but for a true understanding, it helps enormously to be able to see what is going on.
Suggestions for further reading: Bermond, J.-C., and Peyrat, C., “de Bruijn and Kautz Networks: a competitor for the hypercube?” in Andre, F., and Verjus, J.P., eds., Hypercube and Distributed Computers, North Holland, 1989. Banerjee, Subrata, et al, “Regular Multihop Logical Topologies for Lightwave Networks”, in IEEE Communications Surveys, Vol 2, No 1, First Quarter 1999.
Now It Is Your Turn
The SiCortex SC5832 and SC648 are the first clusters to be designed from a clean sheet of silicon, but they could not have been designed on a clean sheet of paper. In a system with thousands of interconnected processors, there is too much going on. You can see that for yourself using the Kautz Graph Viewer on the accompanying CD. Take it all the way up to 972 nodes to see how quickly a Kautz graph can get from anywhere to anywhere. Click on any node to start a broadcast and see how fast it can get from anywhere to everywhere. Treat it as a one-dimensional row of processors or a two-dimensional box. The ability to visualize the backplane topology from a variety of points of view was crucial to the overall systems design, which involved integrating the behavior of the Kautz graph with the behavior of the nodes and the applications software running on those nodes. It was the partnership of experienced architect and computer visualization that made it possible to take this significant step forward in network design. Of course, when it came time to work out the physical wiring of the backplane, the architects had to stand aside. They could not compete with the efficiency of the computer’s genetic algorithm.
