Node-to-Set Disjoint Paths Problem in Cross-Cubes

Rikuya SASAKI; Hiroyuki ICHIDA; Htoo Htoo Sandi KYAW; Keiichi KANEKO

doi:10.1587/transinf.2023EDP7067

Node-to-Set Disjoint Paths Problem in Cross-Cubes

Rikuya SASAKI, Hiroyuki ICHIDA, Htoo Htoo Sandi KYAW, Keiichi KANEKO

Full Text Views

0

Cite this

Summary :

The increasing demand for high-performance computing in recent years has led to active research on massively parallel systems. The interconnection network in a massively parallel system interconnects hundreds of thousands of processing elements so that they can process large tasks while communicating among others. By regarding the processing elements as nodes and the links between processing elements as edges, respectively, we can discuss various problems of interconnection networks in the framework of the graph theory. Many topologies have been proposed for interconnection networks of massively parallel systems. The hypercube is a very popular topology and it has many variants. The cross-cube is such a topology, which can be obtained by adding one extra edge to each node of the hypercube. The cross-cube reduces the diameter of the hypercube, and allows cycles of odd lengths. Therefore, we focus on the cross-cube and propose an algorithm that constructs disjoint paths from a node to a set of nodes. We give a proof of correctness of the algorithm. Also, we show that the time complexity and the maximum path length of the algorithm are O(n³ log n) and 2n - 3, respectively. Moreover, we estimate that the average execution time of the algorithm is O(n²) based on a computer experiment.

Publication: IEICE TRANSACTIONS on Information Vol.E107-D No.1 pp.53-59

Publication Date: 2024/01/01

Publicized: 2023/10/06

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2023EDP7067

Type of Manuscript: PAPER

Category: Fundamentals of Information Systems

Authors

Rikuya SASAKI
  Tokyo University of Agriculture and Technology
Hiroyuki ICHIDA
  Tokyo University of Agriculture and Technology
Htoo Htoo Sandi KYAW
  Tokyo University of Agriculture and Technology
Keiichi KANEKO
  Tokyo University of Agriculture and Technology

Keyword

high-performance computing, hypercube, interconnection network, massively parallel system, shortest path, topology

Cite this

Copy

Rikuya SASAKI, Hiroyuki ICHIDA, Htoo Htoo Sandi KYAW, Keiichi KANEKO, "Node-to-Set Disjoint Paths Problem in Cross-Cubes" in IEICE TRANSACTIONS on Information, vol. E107-D, no. 1, pp. 53-59, January 2024, doi: 10.1587/transinf.2023EDP7067.
Abstract: The increasing demand for high-performance computing in recent years has led to active research on massively parallel systems. The interconnection network in a massively parallel system interconnects hundreds of thousands of processing elements so that they can process large tasks while communicating among others. By regarding the processing elements as nodes and the links between processing elements as edges, respectively, we can discuss various problems of interconnection networks in the framework of the graph theory. Many topologies have been proposed for interconnection networks of massively parallel systems. The hypercube is a very popular topology and it has many variants. The cross-cube is such a topology, which can be obtained by adding one extra edge to each node of the hypercube. The cross-cube reduces the diameter of the hypercube, and allows cycles of odd lengths. Therefore, we focus on the cross-cube and propose an algorithm that constructs disjoint paths from a node to a set of nodes. We give a proof of correctness of the algorithm. Also, we show that the time complexity and the maximum path length of the algorithm are O(n³ log n) and 2n - 3, respectively. Moreover, we estimate that the average execution time of the algorithm is O(n²) based on a computer experiment.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2023EDP7067/_p

Copy

@ARTICLE{e107-d_1_53,
author={Rikuya SASAKI, Hiroyuki ICHIDA, Htoo Htoo Sandi KYAW, Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={Node-to-Set Disjoint Paths Problem in Cross-Cubes},
year={2024},
volume={E107-D},
number={1},
pages={53-59},
abstract={The increasing demand for high-performance computing in recent years has led to active research on massively parallel systems. The interconnection network in a massively parallel system interconnects hundreds of thousands of processing elements so that they can process large tasks while communicating among others. By regarding the processing elements as nodes and the links between processing elements as edges, respectively, we can discuss various problems of interconnection networks in the framework of the graph theory. Many topologies have been proposed for interconnection networks of massively parallel systems. The hypercube is a very popular topology and it has many variants. The cross-cube is such a topology, which can be obtained by adding one extra edge to each node of the hypercube. The cross-cube reduces the diameter of the hypercube, and allows cycles of odd lengths. Therefore, we focus on the cross-cube and propose an algorithm that constructs disjoint paths from a node to a set of nodes. We give a proof of correctness of the algorithm. Also, we show that the time complexity and the maximum path length of the algorithm are O(n³ log n) and 2n - 3, respectively. Moreover, we estimate that the average execution time of the algorithm is O(n²) based on a computer experiment.},
keywords={},
doi={10.1587/transinf.2023EDP7067},
ISSN={1745-1361},
month={January},}

Copy

TY - JOUR
TI - Node-to-Set Disjoint Paths Problem in Cross-Cubes
T2 - IEICE TRANSACTIONS on Information
SP - 53
EP - 59
AU - Rikuya SASAKI
AU - Hiroyuki ICHIDA
AU - Htoo Htoo Sandi KYAW
AU - Keiichi KANEKO
PY - 2024
DO - 10.1587/transinf.2023EDP7067
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E107-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2024
AB - The increasing demand for high-performance computing in recent years has led to active research on massively parallel systems. The interconnection network in a massively parallel system interconnects hundreds of thousands of processing elements so that they can process large tasks while communicating among others. By regarding the processing elements as nodes and the links between processing elements as edges, respectively, we can discuss various problems of interconnection networks in the framework of the graph theory. Many topologies have been proposed for interconnection networks of massively parallel systems. The hypercube is a very popular topology and it has many variants. The cross-cube is such a topology, which can be obtained by adding one extra edge to each node of the hypercube. The cross-cube reduces the diameter of the hypercube, and allows cycles of odd lengths. Therefore, we focus on the cross-cube and propose an algorithm that constructs disjoint paths from a node to a set of nodes. We give a proof of correctness of the algorithm. Also, we show that the time complexity and the maximum path length of the algorithm are O(n³ log n) and 2n - 3, respectively. Moreover, we estimate that the average execution time of the algorithm is O(n²) based on a computer experiment.
ER -