Torus–Connected Cycles: A Simple and Scalable Topology for Interconnection Networks
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 t...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2015-12-01
|
| Series: | International Journal of Applied Mathematics and Computer Science |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/amcs-2015-0052 |
| _version_ | 1818727747687546880 |
|---|---|
| author | Bossard Antoine Kaneko Keiichi |
| author_facet | Bossard Antoine Kaneko Keiichi |
| author_sort | Bossard Antoine |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-17T22:19:01Z |
| format | Article |
| id | doaj.art-56fe868e7e2a43deb1e3f2f88d7f72ac |
| institution | Directory Open Access Journal |
| issn | 2083-8492 |
| language | English |
| last_indexed | 2024-12-17T22:19:01Z |
| publishDate | 2015-12-01 |
| publisher | Sciendo |
| record_format | Article |
| series | International Journal of Applied Mathematics and Computer Science |
| spelling | doaj.art-56fe868e7e2a43deb1e3f2f88d7f72ac2022-12-21T21:30:31ZengSciendoInternational Journal of Applied Mathematics and Computer Science2083-84922015-12-0125472373510.1515/amcs-2015-0052amcs-2015-0052Torus–Connected Cycles: A Simple and Scalable Topology for Interconnection NetworksBossard Antoine0Kaneko Keiichi1Graduate School of Science, Kanagawa University, Tsuchiya 2946, Hiratsuka, Kanagawa, 259-1293 JapanGraduate School of Engineering, Tokyo University of Agriculture and Technology, 2-24-16 Nakacho, Koganei, Tokyo, 184-8588 JapanSupercomputers 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.https://doi.org/10.1515/amcs-2015-0052algorithmroutinghamiltoniansupercomputerparallel |
| spellingShingle | Bossard Antoine Kaneko Keiichi Torus–Connected Cycles: A Simple and Scalable Topology for Interconnection Networks International Journal of Applied Mathematics and Computer Science algorithm routing hamiltonian supercomputer parallel |
| title | Torus–Connected Cycles: A Simple and Scalable Topology for Interconnection Networks |
| title_full | Torus–Connected Cycles: A Simple and Scalable Topology for Interconnection Networks |
| title_fullStr | Torus–Connected Cycles: A Simple and Scalable Topology for Interconnection Networks |
| title_full_unstemmed | Torus–Connected Cycles: A Simple and Scalable Topology for Interconnection Networks |
| title_short | Torus–Connected Cycles: A Simple and Scalable Topology for Interconnection Networks |
| title_sort | torus connected cycles a simple and scalable topology for interconnection networks |
| topic | algorithm routing hamiltonian supercomputer parallel |
| url | https://doi.org/10.1515/amcs-2015-0052 |
| work_keys_str_mv | AT bossardantoine torusconnectedcyclesasimpleandscalabletopologyforinterconnectionnetworks AT kanekokeiichi torusconnectedcyclesasimpleandscalabletopologyforinterconnectionnetworks |