Torus-connected cycles: A simple and scalable topology for interconnection networks

Antoine Bossard; Keiichi Kaneko

International Journal of Applied Mathematics and Computer Science (2015)

  • Volume: 25, Issue: 4, page 723-735
  • ISSN: 1641-876X

Abstract

top
Supercomputers are today made up of hundreds of thousands of nodes. The interconnection network is responsible for connecting all these nodes to each other. Different interconnection networks have been proposed; high performance topologies have been introduced as a replacement for the conventional topologies of recent decades. A high order, a low degree and a small diameter are the usual properties aimed for by such topologies. However, this is not sufficient to lead to actual hardware implementations. Network scalability and topology simplicity are two critical parameters, and they are two of the reasons why modern supercomputers are often based on torus interconnection networks (e.g., Fujitsu K, IBM Sequoia). In this paper we first describe a new topology, torus-connected cycles (TCCs), realizing a combination of a torus and a ring, thus retaining interesting properties of torus networks in addition to those of hierarchical interconnection networks (HINs). Then, we formally establish the diameter of a TCC, and deduce a point-to-point routing algorithm. Next, we propose routing algorithms solving the Hamiltonian cycle problem, and, in a two dimensional TCC, the Hamiltonian path one. Correctness and complexities are formally proved. The proposed algorithms are time-optimal.

How to cite

top

Antoine Bossard, and Keiichi Kaneko. "Torus-connected cycles: A simple and scalable topology for interconnection networks." International Journal of Applied Mathematics and Computer Science 25.4 (2015): 723-735. <http://eudml.org/doc/275991>.

@article{AntoineBossard2015,
abstract = {Supercomputers are today made up of hundreds of thousands of nodes. The interconnection network is responsible for connecting all these nodes to each other. Different interconnection networks have been proposed; high performance topologies have been introduced as a replacement for the conventional topologies of recent decades. A high order, a low degree and a small diameter are the usual properties aimed for by such topologies. However, this is not sufficient to lead to actual hardware implementations. Network scalability and topology simplicity are two critical parameters, and they are two of the reasons why modern supercomputers are often based on torus interconnection networks (e.g., Fujitsu K, IBM Sequoia). In this paper we first describe a new topology, torus-connected cycles (TCCs), realizing a combination of a torus and a ring, thus retaining interesting properties of torus networks in addition to those of hierarchical interconnection networks (HINs). Then, we formally establish the diameter of a TCC, and deduce a point-to-point routing algorithm. Next, we propose routing algorithms solving the Hamiltonian cycle problem, and, in a two dimensional TCC, the Hamiltonian path one. Correctness and complexities are formally proved. The proposed algorithms are time-optimal.},
author = {Antoine Bossard, Keiichi Kaneko},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {algorithm; routing; Hamiltonian; supercomputer; parallel},
language = {eng},
number = {4},
pages = {723-735},
title = {Torus-connected cycles: A simple and scalable topology for interconnection networks},
url = {http://eudml.org/doc/275991},
volume = {25},
year = {2015},
}

TY - JOUR
AU - Antoine Bossard
AU - Keiichi Kaneko
TI - Torus-connected cycles: A simple and scalable topology for interconnection networks
JO - International Journal of Applied Mathematics and Computer Science
PY - 2015
VL - 25
IS - 4
SP - 723
EP - 735
AB - Supercomputers are today made up of hundreds of thousands of nodes. The interconnection network is responsible for connecting all these nodes to each other. Different interconnection networks have been proposed; high performance topologies have been introduced as a replacement for the conventional topologies of recent decades. A high order, a low degree and a small diameter are the usual properties aimed for by such topologies. However, this is not sufficient to lead to actual hardware implementations. Network scalability and topology simplicity are two critical parameters, and they are two of the reasons why modern supercomputers are often based on torus interconnection networks (e.g., Fujitsu K, IBM Sequoia). In this paper we first describe a new topology, torus-connected cycles (TCCs), realizing a combination of a torus and a ring, thus retaining interesting properties of torus networks in addition to those of hierarchical interconnection networks (HINs). Then, we formally establish the diameter of a TCC, and deduce a point-to-point routing algorithm. Next, we propose routing algorithms solving the Hamiltonian cycle problem, and, in a two dimensional TCC, the Hamiltonian path one. Correctness and complexities are formally proved. The proposed algorithms are time-optimal.
LA - eng
KW - algorithm; routing; Hamiltonian; supercomputer; parallel
UR - http://eudml.org/doc/275991
ER -

References

top
  1. Al Faisal, F. and Rahman, M. (2009). Symmetric tori connected torus network, Proceedings of the 12th International Conference on Computers and Information Technology (ICCIT), Dhaka, Bangladesh, pp. 174-179. 
  2. Bossard, A. and Kaneko, K. (2012a). Node-to-set disjoint-path routing in hierarchical cubic networks, The Computer Journal 55(12): 1440-1446. 
  3. Bossard, A. and Kaneko, K. (2012b). The set-to-set disjoint-path problem in perfect hierarchical hypercubes, The Computer Journal 55(6): 769-775. 
  4. Bossard, A. and Kaneko, K. (2013). Set-to-set disjoint paths routing in hierarchical cubic networks, The Computer Journal 57(2): 332-337. 
  5. Bossard, A., Kaneko, K. and Peng, S. (2010). Node-to-set disjoint paths routing in metacube, Proceedings of the 22nd International Conference on Parallel and Distributed Computing and Systems (PDCS), Marina del Rey, CA, USA, pp. 289-296. 
  6. Bossard, A., Kaneko, K. and Peng, S. (2011). A new node-to-set disjoint-path algorithm in perfect hierarchical hypercubes, The Computer Journal 54(8): 1372-1381. 
  7. Camara, J.M., Moreto, M., Vallejo, E., Beivide, R., Miguel-Alonso, J., Martinez, C. and Navaridas, J. (2010). Twisted torus topologies for enhanced interconnection networks, IEEE Transactions on Parallel and Distributed Systems 21(12): 1765-1778. 
  8. Duato, J., Yalamanchili, S. and Ni, L. (2003). Interconnection Networks: An Engineering Approach, Morgan Kaufmann, San Francisco, CA. 
  9. Ghose, K. and Desai, K.R. (1995). Hierarchical cubic network, IEEE Transactions on Parallel and Distributed Systems 6(4): 427-435. 
  10. Horiguchi, S. and Ooki, T. (2000). Hierarchical 3d-torus interconnection network, Proceedings of the 5th International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN), Dallas, TX, USA, pp. 50-56. 
  11. Lai, C.-N. (2012). Optimal construction of all shortest node-disjoint paths in hypercubes with applications, IEEE Transactions on Parallel and Distributed Systems 23(6): 1129-1134. 
  12. Li, Y., Peng, S. and Chu, W. (2004). Efficient collective communications in dual-cube, The Journal of Supercomputing 28(1): 71-90. Zbl1101.68340
  13. Li, Y., Peng, S. and Chu, W. (2010). Metacube-a versatile family of interconnection networks for extremely large-scale supercomputers, Journal of Supercomputing 53(2): 329-351. 
  14. Malluhi, Q.M. and Bayoumi, M.A. (1994). The hierarchical hypercube: A new interconnection topology for massively parallel systems, IEEE Transactions on Parallel and Distributed Systems 5(1): 17-30. 
  15. Preparata, F.P. and Vuillemin, J. (1981). The cube-connected cycles: A versatile network for parallel computation, Communications of the ACM 24(5): 300-309. 
  16. Seitz, C. (1985). The cosmic cube, Communications of the ACM 28(1): 22-33. 
  17. Shih, Y.-K., Chuang, H.-C., Kao, S.-S. and Tan, J.J. (2010). Mutually independent Hamiltonian cycles in dual-cubes, Journal of Supercomputing 54(2): 239-251. 
  18. Singh, A., Dally, W., Gupta, A. and Towles, B. (2003). Goal: A load-balanced adaptive routing algorithm for torus networks, SIGARCH Computer Architecture News 31(2): 194-205. 
  19. TOP500 (2013). China's Tianhe-2 supercomputer takes no. 1 ranking on 41st TOP500 list, http://top500.org/blog/lists/2013/06/ press-release/, (last accessed in August 2013). 
  20. Wu, J. and Sun, X.-H. (1994). Optimal cube-connected cube multicomputers, Journal of Microcomputer Applications 17(2): 135-146. 
  21. Xiang, D. and Luo, W. (2012). An efficient adaptive deadlock-free routing algorithm for torus networks, IEEE Transactions on Parallel and Distributed Systems 23(5): 800-808. 
  22. Zhou, S., Chen, L. and Xu, J. (2012a). Conditional fault diagnosability of dual-cubes, International Journal of Foundations of Computer Science 23(8): 1729-1748. Zbl1311.68036
  23. Zhou, S., Lin, L. and Xu, J. (2012b). Conditional fault diagnosis of hierarchical hypercubes, International Journal of Computer Mathematics 89(16): 2152-2164. Zbl1255.68045

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.