A Routing Algorithm Solving the Container Problem in a Hypercube with Bit Constraint

DOI

10.2991/ijndc.2015.3.4.1How to use a DOI?

Keywords

Supercomputer, parallel system, network, disjoint paths, dependable system, node-to-node.

Abstract

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.

Copyright

© 2017, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - JOUR
AU  - Antoine Bossard
AU  - Keiichi Kaneko
PY  - 2015
DA  - 2015/11/01
TI  - A Routing Algorithm Solving the Container Problem in a Hypercube with Bit Constraint
JO  - International Journal of Networked and Distributed Computing
SP  - 202
EP  - 213
VL  - 3
IS  - 4
SN  - 2211-7946
UR  - https://doi.org/10.2991/ijndc.2015.3.4.1
DO  - 10.2991/ijndc.2015.3.4.1
ID  - Bossard2015
ER  -