A Routing Algorithm Solving the Container Problem in a Hypercube with Bit Constraint
Tóm tắt
As reflected by the TOP500 list, hypercubes are popular interconnection networks for massively parallel systems, the main reason being the simplicity and ease of implementation of this network topology. In order to retain performance high and avoid bottleneck situation, routing algorithms are critical for these high-performance systems. Furthermore, disjoint path routing is a very desirable property of such communication algorithms. Effectively, selecting mutually node-disjoint paths guarantees that notorious parallel processing issues such as deadlocks, livelocks and starvations shall never occur. In this paper, we describe a routing algorithm for hypercubes that, given a bit constraint, selects internally node-disjoint paths between any pair of nodes satisfying the constraint, and such that the selected paths all satisfy the constraint. The introduction of such bit constraint enables the selection of multiple sets of disjoint paths between several node pairs each satisfying a distinct bit constraint, which is impossible with conventional routing algorithms. Selecting simultaneously disjoint paths between different node pairs induces increased communication performance and system dependability. The correctness and complexities of the described algorithm are formally proved, and analysis of the algorithm performance in practice is conducted by empirical evaluation.
Tài liệu tham khảo
Y. Saad and M. H. Schultz, “Topological Properties of Hypercubes,” IEEE Transactions on Computers, 37(7), 867–872 (1988).
C. L. Seitz, “The cosmic cube,” Communications of the ACM, 28(1):22–33 (1985).
TOP500, “TOP500 List November 2014,” http://top500.org/list/2014/11/, November 2014. Last accessed April 2015.
Y. Li, S. Peng and W. Chu, “Efficient collective communications in dual-cube,” The Journal of Supercomputing, 28(1):71–90 (2004).
Y. Li, S. Peng and W. Chu, “Metacube - a versatile family of interconnection networks for extremely large-scale supercomputers,” The Journal of Supercomputing, 53(2):329–351 (2010).
Q. M. Malluhi and M. A. Bayoumi, “The hierarchical hypercube: a new interconnection topology for massively parallel systems,” IEEE Transactions on Parallel and Distributed Systems, 5(1):17–30 (1994).
K. Ghose and K. R. Desai, “The HCN: a versatile interconnection network based on cubes,” In Proceedings of the 1989 ACM/IEEE Conference on Supercomputing, pp. 426–435, Reno, NV, USA, November 12–17 (1989).
S. Gao, B. Novick and K. Qiu, “From Hall’s Matching Theorem to Optimal Routing on Hypercubes,” Journal of Combinatorial Theory, Series B, 74:291–301 (1998).
O. Sinanoglu, M. H. Karaata and B. AlBdaiwi, “An inherently stabilizing algorithm for node-to-node routing over all shortest node-disjoint paths in hyper-cube networks,” IEEE Transactions on Computers, 59(7):995–999 (2010).
A. Bossard and K. Kaneko, “Time optimal node-to-set disjoint paths routing in hypercubes,” Journal of Information Science and Engineering, 30(4):1087–1093 (2014).
Q.-P. Gu, S. Okawa and S. Peng, “Set-to-set fault tolerant routing in hypercubes,” IEICE Transactions on Fundamentals, E79-A(4):483–488 (1996).
Q.-P. Gu and S. Peng, “An efficient algorithm for the k-pairwise disjoint paths problem in hyper-cubes,” Journal of Parallel and Distributed Computing, 60(6):764–774 (2000).
A. Bossard and K. Kaneko, “On hypercube routing and fault tolerance with bit constraint,” In Proceedings of the Second International Symposium on Computing and Networking, pp. 40–49, Shizuoka City, Japan, December 10–12 (2014).
Y. Li, S. Peng and W. Chu, “Disjoint paths in metacube,” In Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems, pp. 43–50, Marina del Rey, CA, USA, November 3–5 (2003).
S. Murugesan, “Harnessing Green IT: Principles and practices,” IT Professional, 10(1):24–33 (2008).
J. Chen, I. A. Kanj and G. Wang, “Hypercube network fault tolerance: a probabilistic approach,” Journal of Interconnection Networks, 6(1):17–34 (2005).
M. Dietzfelbinger, S. Madhavapeddy and I. H. Sudborough, “Three disjoint path paradigms in star networks,” In Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, pp. 400–406, Dallas, TX, USA, December 2–5 (1991).
Y. Suzuki and K. Kaneko, “An algorithm for node-disjoint paths in pancake graphs,” IEICE Transactions on Information and Systems, E86-D(3):610–615 (2003).
K. Kaneko and N. Sawada, “An algorithm for node-to-node disjoint paths problem in burnt pancake graphs,” IEICE Transactions on Information and Systems, E90-D(1):306–313 (2007).
K. Menger, “Zur allgemeinen Kurventheorie,” Fundamenta Mathematicae, 10:96–115 (1927).
R. B. Findler, J. Clements, C. Flanagan, M. Flatt, S. Krishnamurthi, P. Steckler and M. Felleisen, “DrScheme: a programming environment for scheme,” Journal of Functional Programming, 12(2):159–182 (2002).