Mesh Muddling Madness^{1}
The theory of six degrees of separation is the idea that any living person is only six introductions away. In other words, the graph with nodes being people and edges being their friendships has a very low maximumshortestpathlength (or diameter) compared to the number of nodes. Networks such as these are known as 'smallworld networks' and this article explores what properties a supercomputer wired up in this manner might have.
Making SmallWorld Networks
Watts and Strogatz proposed an
algorithm for generating
random smallworld networks. The algorithm starts with a ring network of
To turn this network into a smallworld network, a small percentage of the edges
are randomly rewired^{2}. In the example below, edges are rewired
with a probability
The modified graph now exhibits various smallworld properties, notably a reduced average pathlength.
Making SmallWorld SuperComputers
For certain computing tasks reducing the average pathlength in the network may
be desirable as it would potentially reduce the latency between arbitrary pairs
of nodes in the system. Supercomputer interconnection systems tend not to use
ring networks but instead a
The network above is a 2D torus (a 6ary 2cube), in this network the average
path length (in terms of hops) is
If the network shown above has been rewired with
With larger networks the effect becomes more significant. Below shows the results for a 40ary 2cube^{4}. Here the average path length drops by almost 50% when just 1% of edges are rewired.
Practical Wiring
Unfortunately, adding wires at random like we have done in the previous examples could be problematic for realworld systems. It isn't practical to have wires above a certain length and when laid out naively as shown above you can see that long wires crossing the whole system appear.
Folding Long Wires
In order to keep wirelengths manageable, the whole network should be folded in half. For example, this ring network:
Can be folded in half to yield this arrangement containing no wires which cross the whole system:
Or, drawn flattened:
This process can be generalised to minimise the maximum wirelength required for 2cubes as well:
Keeping RandomlyCreated Wires Short
Of course, things start to get interesting when we start rewiring the edges as
long wires can start to reappear. For example, here is the same network with
rewiring of edges with
As you can see there are several long wires including one that crosses nearly the longest jump in the system (bottom left to nearlytop right).
In an attempt to combat this problem we can change the rewiring algorithm to only create new links whose links are relatively short.
The rewiring above constrains the maximum wire to be 3 units long (where a unit is the spacing between each node in a given dimension). We still see that the maximum path length still drops, this time to 2.73, but now there are no long wires.
To test the effects of limiting wire lengths when rewiring, a parameter sweep was carried out for a 40ary 2cube both with and without folding:
For very short wire length limits, folding provides improved average pathlengths, presumably because it is betterable to insert links to nodes topologically far away using only short wires. This is due to the fact that each folding moves the furthest nodes much closer at the expense of slightly increasing the wire length between topologically close nodes.
The other interesting effect visible in the graph is that allowing wires longer
than about 25 units has no significant effect on the average path length. I
hypothesise that there is some small benefit hidden by noise) which eventually
disappears when wires reach 40 units long. This is due to the fact that wires of
a maximum length of 40 allow packets to jump beyond the length of the maximum
shortestpath possible in the system which would never be useful: a wire which
travels the equivalent distance of
Remaining Work
Much work remains to be done in this analysis. In particular:
 A formula which calculates the expected average path length in the case of rewiring and wirelength limited rewiring.
 An analysis of the use of edgeadding variation on the Watts Strogatz model
 An analysis of how this effects the bisectionbandwidth of the network
 An analysis of routing challenges

This piece could alternatively be titled "Torus Twiddling Tedium", depending on your level of enthusiasm. ↩

In Watts and Strogatz's original algorithm it is also defined that the random rewirings shouldn't create selfloops or duplicate edges. ↩

The ring network shown in the first example can be described as a 12ary 1cube. ↩

Because a 40ary 2 cube relatively slow to exhaustively search many times (and I'm impatient), the average path lengths in that experiment were calculated by sampling from 10 random starting nodes. ↩