A Routing Algorithm Solving the Container Problem in a Hypercube with Bit Constraint
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 critic...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer
2015-11-01
|
| Series: | International Journal of Networked and Distributed Computing (IJNDC) |
| Subjects: | |
| Online Access: | https://www.atlantis-press.com/article/25841971.pdf |
| _version_ | 1797936057656803328 |
|---|---|
| author | Antoine Bossard Keiichi Kaneko |
| author_facet | Antoine Bossard Keiichi Kaneko |
| author_sort | Antoine Bossard |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T18:23:44Z |
| format | Article |
| id | doaj.art-b24c8df6e63349b9a9774265420e7226 |
| institution | Directory Open Access Journal |
| issn | 2211-7946 |
| language | English |
| last_indexed | 2024-04-10T18:23:44Z |
| publishDate | 2015-11-01 |
| publisher | Springer |
| record_format | Article |
| series | International Journal of Networked and Distributed Computing (IJNDC) |
| spelling | doaj.art-b24c8df6e63349b9a9774265420e72262023-02-02T06:30:30ZengSpringerInternational Journal of Networked and Distributed Computing (IJNDC)2211-79462015-11-013410.2991/ijndc.2015.3.4.1A Routing Algorithm Solving the Container Problem in a Hypercube with Bit ConstraintAntoine BossardKeiichi KanekoAs 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.https://www.atlantis-press.com/article/25841971.pdfSupercomputerparallel systemnetworkdisjoint pathsdependable systemnode-to-node. |
| spellingShingle | Antoine Bossard Keiichi Kaneko A Routing Algorithm Solving the Container Problem in a Hypercube with Bit Constraint International Journal of Networked and Distributed Computing (IJNDC) Supercomputer parallel system network disjoint paths dependable system node-to-node. |
| title | A Routing Algorithm Solving the Container Problem in a Hypercube with Bit Constraint |
| title_full | A Routing Algorithm Solving the Container Problem in a Hypercube with Bit Constraint |
| title_fullStr | A Routing Algorithm Solving the Container Problem in a Hypercube with Bit Constraint |
| title_full_unstemmed | A Routing Algorithm Solving the Container Problem in a Hypercube with Bit Constraint |
| title_short | A Routing Algorithm Solving the Container Problem in a Hypercube with Bit Constraint |
| title_sort | routing algorithm solving the container problem in a hypercube with bit constraint |
| topic | Supercomputer parallel system network disjoint paths dependable system node-to-node. |
| url | https://www.atlantis-press.com/article/25841971.pdf |
| work_keys_str_mv | AT antoinebossard aroutingalgorithmsolvingthecontainerprobleminahypercubewithbitconstraint AT keiichikaneko aroutingalgorithmsolvingthecontainerprobleminahypercubewithbitconstraint AT antoinebossard routingalgorithmsolvingthecontainerprobleminahypercubewithbitconstraint AT keiichikaneko routingalgorithmsolvingthecontainerprobleminahypercubewithbitconstraint |