High-performance routing in networks of workstations with irregular topology

Networks of workstations are rapidly emerging as a cost-effective alternati ve to parallel computers. Switch-based interconnects with irregular topolog y allow the wiring flexibility, scalability, and incremental expansion capa bility required in this environment. However, the irregularity also makes r outing and deadlock avoidance on such systems quite complicated. In current proposals, many messages are routed following nonminimal paths, increasing latency and wasting resources, in this paper, we propose two general metho dologies for the design of adaptive routing algorithms for networks with ir regular topology. Routing algorithms designed according to these methodolog ies allow messages to follow minimal paths in most cases, reducing message latency and increasing network throughput. As an example of application, we propose two adaptive routing algorithms fo r AN1 (previously known as Autonet). They can be implemented either by dupl icating physical channels or by splitting each physical channel into two Vi rtual channels. In the former case, the implementation does not require a n ew switch design. It only requires changing the routing tables and adding l inks in parallel with existing ones, taking advantage of spare switch ports . In the latter case, a new switch design is required, but the network topo logy is not changed. Evaluation results for several different topologies an d message distributions show that the new routing algorithms are able to in crease throughput for random traffic by a factor of up to 4 with respect to the original up*/down* algorithm, also reducing latency significantly. For other message distributions, throughput is increased more than seven times . We also show that most of the improvement comes from the use of minimal r outing.