Non-Cartesian Networks

  Not all networks are as easy to route for as the Cartesian network; there, the e-cube algorithm easily achieves 100% of the bisection bandwidth on random traffic (consider two random nodes on opposite sides of a bisection; the probability of a message between them using any particular link in the bisection is equal to that for any other bisection link). Irregular networks may be convenient to build based on component availability or, for dedicated nodes, for predicted bandwidth needs among nodes. Such networks are extremely difficult to handle using online routing algorithms, since the route from one node to another may not lead through any obvious path.

Even regular topologies may be hard to get maximum performance from with online algorithms. For example, the diamond lattice network [63,52] is an appealing network topology, with isomorphic 3D connectivity but only four neighbors for each node; this allows a simpler crossbar and more pins per I/O port for pin-limited packages. However, the diamond lattice suffers from the fact that using exclusively shortest path connections prevents the network from achieving 100% of its bisection bandwidth. In fact, no known online algorithm is able to provide full bandwidth across the bisection on the diamond lattice. Accordingly, scheduled routing can serve as an enabling factor for exploring the potential of non-Cartesian networks.

Figure 1.4 shows the difference in achievable bandwidth in a diamond-lattice network between traditional online routing and a version of scheduled routing. The graph depicts random traffic; the diamond-lattice mesh simulated is of size 455 (a 7-ary 4-diamond), with length-4 messages. The online algorithm is a suitably modified version of the Cartesian network's oblivious e-cube algorithm. As before, cycle counts are gathered by simulation of dynamic algorithms and a simple computation from scheduled bandwidths for the schedule router.

  

Figure 1.4: Diamond-lattice scheduled routing

The graph shows that the dynamic routing algorithm hits a maximum throughput limit around 0.04 mean offered messages per node (that is, the point when each node has a 4% chance of injecting a message on each cycle). By contrast, the scheduled algorithm continues to provide throughput (though with growing latency) up to 0.07, the largest mean offered rate per node shown.