I’ll bet nobody, except some people I’ve told about it before, could identify what this is.
Give up? OK, it’s a string-art representation of three disjoint Hamiltonian cycles in a degree-3 diameter-3 Kautz graph. A what? Unfortunately, a Kautz graph is not an inherently easy thing to grasp or describe, and the Wikipedia article does a particularly lousy job. (Yeah yeah, I know, I could write my own, but I’ve had enough of Wikipedia politcs already.) We have some decent descriptions that we’ve used for presentations at work (it’s the topology used in our machines), but what’s on the website doesn’t seem that great. So, here are some of the basics.
A degree-N Kautz graph consists of nodes which each have N input and N output links (arcs, edges, whatever terminology you prefer) arranged in a particular order. Specifically, each node has a number expressed in base N+1, such that no two adjacent digits are the same. The node’s output links are defined by shifting its number left and filling on the right with one of the three eligible digits; its input links are defined by shifting right and filling on the left likewise. So, for example, node 132 (in a degree-3 graph) will have output links to 320/321/323 and input links from 013/213/313). Why on Earth is any of this interesting or useful to anyone but a graph theorist? Because it turns out that Kautz graphs have a lot of interesting properties. For example, a degree-3 diameter-6 Kautz graph guarantees that any two nodes out of 972 have three completely separate paths each involving no more than six hops between them. For the same number of nodes, a hypercube would require ten hops and a torus fifteen. That’s why SiCortex uses Kautz graphs to connect nodes, with the SC072/SC648/SC5832 being degree-3 networks of diameter 2/4/6 respectively. The number of nodes in a Kautz graph of degree k and diameter d is (k+1)*kd-1. For k=3 and d=6, that’s 4*35 or 972, times 6 cores per node = 5832, hence the name of the system.
Kautz graphs are interesting to work with. For one thing, it’s almost impossible to conceptualize which nodes are connected to which others, through which paths. Can you tell me how to get from node 3101 to node 0321? Uhhh. Well, there’s always one obvious path formed by simply shifting in the digits of the destination one by one (in this case 3101 to 1010 to 0103 to 1032 to 0321), but there may be shorter paths and by the way good luck finding the other two that are guaranteed to exist. In practical effect, the connections and routes seem just as random as those in some arbitrary collection of nodes on the internet. Then there’s the issue of tiling a Kautz graph, or breaking it down into topologically-equal pieces so (for example) you can make a diameter-4 or diameter-6 system using the same pieces. That’s some of SiCortex’s secret sauce, but I don’t need to worry about giving away our methods because I don’t know them and even if I did I doubt that I’d understand them. Basically we just have a few guys who are really smart and have studied this a lot, and they seem to know how to do it.
Of course, none of this explains why I went to the effort of creating a string-art manifestation of a Kautz graph. Mostly it’s just because I felt like the versions on slides and such were all a bit disappointing. There’s just something about this version’s physical reality that makes it more compelling. As it turns out, actually wrapping the strings around the posts made me more acutely aware of some of the Kautz graph’s strange symmetries than I had been before. There was also a bit of an intellectual challenge involved. Pretty early I hit on the idea of dividing the links into three cycles and using different colors to represent them, and then I had to figure out how to find those cycles. In fact, I spent more time writing the program to do that than I did physically building the thing, and one of our local Kautz gurus was actually a bit surprised to find that there even were three disjoint Hamiltonians in a diameter-3. Lastly, of course, I did it because it’s unique. I’m pretty darn sure nobody else has one, and in today’s mass-produced world the idea that I have something that would not exist if I hadn’t made it myself is pretty satisfying.
UPDATE: one of the aforementioned smart people offered the following corrections and graciously gave permission for me to include them here.
In the second paragraph, you say that any pair of nodes will have three separate paths with no more than 6 hops between them. In fact, the first (shortest) path has no more than 6 hops, the second typically has 7, and the third in a few cases requires 8 hops.
All paths can be thought of as shifting in the destination node number. Short paths arise when the trailing digits of the origin node number correspond to leading digits of the destination node number, so fewer shifts are required than the diameter.
The alternate paths to a destination arise by shifting in a “wrong” digit (one which does not take you on the shortest path to the destination), followed by shifting in the correct digits of the destination address.
In a way, that underscores the point I made about how hard it is to conceptualize Kautz graphs. Consider the “shifting in a wrong digit” part. It’s fairly obvious that doing so will give you a new path, but considerably less obvious that the paths thus derived will be totally separate from one another. Kautz graphs are full of little surprises like this, which is what gives them their charm.
That’s really cool, actually. Seems like it would be really good for network redundancy. If a single node goes down, to circumvent any paths that include it, simply move one step in the “wrong” direction, then proceed. Also, I like the string art. +1
Interesting to find that in 1922 LF richardson came up with parallel supercomputing, theater of human computing or some such title for the book with a wonderful bit of artwork to go along with it.64,000 humans invisioned working symbiotically. Earth simulator home page has the artwork reminicent of Dali. Interesting to note that he was one of the keys behind fractals as well. Looks like we have 85 years to catch up on, too bad the us chose to keep vaccume tubes over transistors until the 60s then where would we be…u can thank sony and rca for that.
Larry Stewart (another of those really smart people at SiCortex) sent me a link to a paper about disjoint Hamiltonian cycles in a de Bruijn graph (which is very closely related to a Kautz graph). Had we known of this earlier, the result represented above might have been a little less surprising.
I might be missing something but here’s my take: I doubt that the routing problem is so obscure. For any degree k graph there are certainly k exits from any node – however only one of them will be the shortest path. Let’s say I have degree=3, diameter = 6 like your SC5832 system w/ 972 nodes. I need a 6-digit base-4 node ID. If I want to go from 313201 to 212032 – the shortest route is:
313201 –> 132012 –> 320121 –> 201212 –> 012120 –> 121203 –> 212032
but if I want to go from 313201 to 201323 then the shortest path is
313201 –> 132013 –> 320132 –> 201323
Seems to me that it’s all about how many digits in the source suffix match the prefix of the destination. If this number is m then the shortest path is diameter – m hops.
Given your definitions I just don’t see any other choice – granted if you have a bad link or intermediate node then routing will be less deterministic and the path length will be longer since you’ll have to deroute and take a non-shortest path link
Can you send me a counter example??
From a hardware perspective the routing decision is not simple but would depend on the routing choice – source routing or absolute are reasonable options. For source routing: either you need a 972*972 entry table of 2 bit entries (ceil(log2(diameter))) given a perfect hash function (a bit problematic given the non-power-of-2 entries) OR you could build the route table as a tree which would take more time but less space OR you’d need hardware to match the suffix vs. prefix, then the non matched digits could be easily converted into exit paths for each node along the way.
For absolute addressing you’d just have to do the match with the node ID vs. the destination ID – take the first non-matched digit and take that exit path for the shortest route – if that’s not available take one of the other available paths.
What am I missing?
Well, Al, you’re sort of right and sort of wrong. What you’ve just described is a slightly more detailed algorithm for finding what I previously described as the obvious path between two nodes. Even people who didn’t have a Kautz graph described to them in terms of shifting digits (one of the shortcomings of the Wikipedia version IMO) generally figure out the whole prefix/suffix thing pretty quickly. Clearly it’s not that difficult to find the first path between two nodes. Does that mean it’s easy to comprehend or visualize the graph as a whole, rather than as a set of distinct connections in what might as well be in an arbitrary-topology network such as is studied in the internet/P2P world? How do you route around failures? How do you find cycles or closely-connected groups? How do you partition the graph to form groups with no links in common? Given a certain set of links that have either failed or stopped passing traffic, how do you find the one that actually failed and caused the others to back up? How do you cast any of the answers into a form that’s useful to a switch element that has to forward a packet in nanoseconds? Sometimes the answers to these questions turn out to be surprisingly simple, such as the “first hop in the wrong direction” way of routing around failures, but simple doesn’t mean obvious. Contrast with a hypercube or torus, for which most of these answers are both simple and obvious. Even calculating the bisection bandwidth of a Kautz network, a trivial exercise for these other kinds, leads one quickly into confusion.
Hello,
Recently I got very interested in the Kautz graph, and I find this article by Google. The artwork is really amazing! But I also notice that it seems that you (and the Sicortex company) are the only one(s) who place the nodes on the four sides of a square. I’m not yet sure, but it seems to have some special properties with this arrangement. Can you kindly tell me where is this node arrangement from (e.g. some papers, or the Sicortex company’s patent)?
Many thanks!
C. Tsai
I don’t think there’s anything special about the square, actually. The physical structure of the SiCortex machines was certainly not that way. I used a square only because it was the first shape that occurred to me. Putting all of the nodes around the edge allows all of the lines to be straight, which is necessary for string art. Similarly, a polygon was easier in this medium than a circle, and for a graph of degree N a polygon with either N or N+1 sides allows the nodes to be divided evenly among sides. Since I was using degree=3 either a triangle or a square probably would have worked. In fact, a triangle might have highlighted some of the internal symmetry better, but I didn’t think of doing it that way. If I ever build another string-art Kautz graph I’ll do it that way.