2003 International Conference on Parallel Processing (ICPP'03)
Descending Layers Routing: A Deadlock-Free Deterministic Routing using Virtual Channels in System Area Networks with Irregular Topologies
Kaohsiung, Taiwan
October 06-October 09
ISBN: 0-7695-2017-0
System Area Networks (SANs), which usually accept irregular topologies, have been used to connect nodes in PC/WS clusters or high-performance storage systems. Since wormhole or virtual cut-through transfer is used for low latency communication, deadlock-free routings are essential in SANs. In this paper, we propose a novel deadlock-free deterministic routing called descending layers (DL) routing for SANs. In order to reduce both non-minimal paths and traffic congestion, the network is divided into layers of sub-networks with the same topology using virtual channels, and a large number of paths across multiple subnetworks are established. The DL routing is implemented on a real PC cluster called RHiNET-2, and execution results show that its throughput is improved up to 33% compared with that of up*/down* routing. Its execution time of a barrier synchronization is also improved 29% compared with that of up*/down* routing. Simulation results of various sizes and topologies also show that the DL routing achieves up to 266% improvement on throughput compared with up*/down* routing.
Index Terms:
Deterministic routing, System Area Networks, deadlock avoidance, RHiNET, irregular topologies, virtual channels, interconnection networks, PC clusters
Citation:
Michihiro Koibuchi, Akiya Jouraku, Konosuke Watanabe, Hideharu Amano, "Descending Layers Routing: A Deadlock-Free Deterministic Routing using Virtual Channels in System Area Networks with Irregular Topologies," icpp, pp.527, 2003 International Conference on Parallel Processing (ICPP'03), 2003