An Effective Design of Deadlock-Free Routing Algorithms Based on 2D Turn Model for Irregular Networks Export

@article{citeulike:1106658, abstract = {System area networks (SANs), which usually accept arbitrary topologies, have been used to connect hosts in PC clusters. Although deadlock-free routing is often employed for low-latency communications using wormhole or virtual cut-through switching, the interconnection adaptivity introduces difficulties in establishing deadlock-free paths. An up*/down* routing algorithm, which has been widely used to avoid deadlocks in irregular networks, tends to make unbalanced paths as it employs a one-dimensional directed graph. The current study introduces a two-dimensional directed graph on which adaptive routings called left-up first turn (L-turn) routings and right-down last turn (R-turn) routings are proposed to make the paths as uniformly distributed as possible. This scheme guarantees deadlock-freedom because it uses the turn model approach, and the extra degree of freedom in the two-dimensional graph helps to ensure that the prohibited turns are well-distributed. Simulation results show that better throughput and latency results from uniformly distributing the prohibited turns by which the traffic would be more distributed toward the leaf nodes. The L-turn routings, which meet this condition, improve throughput by up to 100 percent compared with two up*/down*-based routings, and also reduce latency.}, author = {Jouraku, A. and Koibuchi, M. and Amano, H.}, citeulike-article-id = {1106658}, citeulike-linkout-0 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4079532}, journal = {Parallel and Distributed Systems, IEEE Transactions on}, keywords = {2d, deadlock, networks, routing}, number = {3}, pages = {320--333}, posted-at = {2007-02-14 10:51:24}, priority = {2}, title = {An Effective Design of Deadlock-Free Routing Algorithms Based on 2D Turn Model for Irregular Networks}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4079532}, volume = {18}, year = {2007} }

TY - JOUR ID - citeulike:1106658 L3 - citeulike-article-id:1106658 N2 - System area networks (SANs), which usually accept arbitrary topologies, have been used to connect hosts in PC clusters. Although deadlock-free routing is often employed for low-latency communications using wormhole or virtual cut-through switching, the interconnection adaptivity introduces difficulties in establishing deadlock-free paths. An up*/down* routing algorithm, which has been widely used to avoid deadlocks in irregular networks, tends to make unbalanced paths as it employs a one-dimensional directed graph. The current study introduces a two-dimensional directed graph on which adaptive routings called left-up first turn (L-turn) routings and right-down last turn (R-turn) routings are proposed to make the paths as uniformly distributed as possible. This scheme guarantees deadlock-freedom because it uses the turn model approach, and the extra degree of freedom in the two-dimensional graph helps to ensure that the prohibited turns are well-distributed. Simulation results show that better throughput and latency results from uniformly distributing the prohibited turns by which the traffic would be more distributed toward the leaf nodes. The L-turn routings, which meet this condition, improve throughput by up to 100 percent compared with two up*/down*-based routings, and also reduce latency. IS - 3 JF - Parallel and Distributed Systems, IEEE Transactions on EP - 333 TI - An Effective Design of Deadlock-Free Routing Algorithms Based on 2D Turn Model for Irregular Networks VL - 18 SP - 320 KW - 2d KW - deadlock KW - networks KW - routing AU - Jouraku, A AU - Koibuchi, M AU - Amano, H PY - 2007/// UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4079532 ER -