Segment-based routing: an efficient fault-tolerant routing algorithm for meshes and tori

Computers get faster every year, but the demand for computing resources seems to grow at an even faster rate. Depending on the problem domain, this demand for more power can be satisfied by either, massively parallel com-puters, or clusters of computers. Common for both ap-proaches is the dependence on high performance intercon-nect networks such as Myrinet, Infiniband, or 10 Giga-bit Ethernet. While high throughput and low latency are key features of interconnection networks, the issue of fault-tolerance is now becoming increasingly important. As the number of network components grows so does the probabil-ity for failure, thus it becomes important to also consider the fault-tolerance mechanism of interconnection networks. The main challenge then lies in combining performance and fault-tolerance, while still keeping cost and complexity low. This paper proposes a new deterministic routing method-ology for tori and meshes, which achieves high performance without the use of virtual channels. Furthermore, it is topol-ogy agnostic in nature, meaning it can handle any topol-ogy derived from any combination of faults when combined with static reconfiguration. The algorithm, referred to as Segment-based Routing (SR), works by partitioning a topol-ogy into subnets, and subnets into segments. This allows us to place bidirectional turn restrictions locally within a seg-ment. As segments are independent, we gain the freedom to place turn restrictions within a segment independently from other segments. This results in a larger degree of freedom when placing turn restrictions compared to other routing strategies. In this paper a way to compute segment-based routing tables is presented and applied to meshes and tori. Evalua-tion results show that SR increases performance by a factor of 1.8 over FX and up*/down * routing. ∗This work was supported by the Spanish CICYT under Gran