A Novel Globally Adaptive Load-Balanced Routing Algorithm for Torus Interconnection Networks

ETRI Journal

关键词: deadlock;    traffic pattern;    load-balance;    adaptive routing algorithms;    torus interconnection networks;   

Others  :  1185571
DOI  :  10.4218/etrij.07.0206.0241

【 摘 要 】

A globally adaptive load-balanced routing algorithm for torus interconnection networks is proposed. Unlike previously published algorithms, this algorithm employs a new scheme based on collision detection to handle deadlock, and has higher routing adaptability than previous algorithms. Simulation results show that our algorithm outperforms previous algorithms by 16% on benign traffic patterns, and by 10% to 21% on adversarial traffic patterns.

   

【 参考文献 】

• [1]J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks: An Engineering Approach, revised edition, Morgan Kaufmann, San Francisco, 2002.
• [2]W.J. Dally, "Scalable Switching Fabrics for Internet Routers," Whitepaper, Avici Systems. http://www.avici.com/technology/ whitepapers/
• [3]A. Singh, W.J. Dally, and A.K. Gupta, "GOAL: A Load-Balanced Adaptive Routing Algorithm for Torus Networks," Proc. 30th Annual Int. Symp. Computer Architecture, 2003, pp. 194-205.
• [4]A. Singh, W.J. Dally, and B. Towles, "Globally Adaptive Load-Balanced Routing on Tori," IEEE Computer Architecture Letters, vol. 1, 2004, pp. 2-5.
• [5]K. Bolding, M.L. Fulgham, and L. Snyder, "The Case for Chaotic Adaptive Routing," IEEE Trans. Computers, vol. 12, 1997, pp. 1281-1291.
• [6]A. Singh, W.J. Dally, and A.K. Gupta, "Adaptive Channel Queue Routing on K-ary N-cubes," Proc. 16th ACM Symp. Parallelism in Algorithms and Architectures, 2004, pp. 11-19.
• [7]K.V. Anjan and T.M. Pinkston, "DISHA: A Deadlock Recovery Scheme for Fully Adaptive Routing," Proc. 9th Int’l Parallel Processing Symp., Apr. 1995, pp. 537-543.