TY - GEN ID - cogprints4701 UR - http://cogprints.org/4701/ A1 - Wang, Hong A1 - Xu, Du A1 - Jiang, Guo A1 - Yao, Yao A1 - Xu, Shizhong A1 - Li, Lemin TI - Proof of the deadlock-freeness of ALD routing algorithm Y1 - 2006/01// N2 - This is the appendix to the paper Load-Balanced Adaptive Routing for Torus Networks to provide a detailed, formal proof of the deadlock-freeness of the routing algorithm proposed in the paper. The paper is submitted to Electronics Letters, and the abstract of which is as follows: A new routing algorithm for torus interconnection networks to achieve high throughput on various traffic patterns, Adaptive Load-balanced routing with cycle Detection (ALD), is presented. Instead of the -channels scheme adopted in a few recently proposed algorithms of the same category, a cycle detection scheme is employed in ALD to handle deadlock, which leads to higher routing adaptability. Simulation results demonstrate that ALD achieves higher throughput than the recently proposed algorithms on both benign and adversarial traffic patterns. AV - public KW - deadlock KW - routing algorithm KW - torus networks ER -