IEICE TRANSACTIONS on Information
Minimal Paths in a Bicube
Summary :
Nowadays, a rapid increase of demand on high-performance computation causes the enthusiastic research activities regarding massively parallel systems. An interconnection network in a massively parallel system interconnects a huge number of processing elements so that they can cooperate to process tasks by communicating among others. By regarding a processing element and a link between a pair of processing elements as a node and an edge, respectively, many problems with respect to communication and/or routing in an interconnection network are reducible to the problems in the graph theory. For interconnection networks of the massively parallel systems, many topologies have been proposed so far. The hypercube is a very popular topology and it has many variants. The bicube is a such topology and it can interconnect the same number of nodes with the same degree as the hypercube while its diameter is almost half of that of the hypercube. In addition, the bicube keeps the node-symmetric property. Hence, we focus on the bicube and propose an algorithm that gives a minimal or shortest path between an arbitrary pair of nodes. We give a proof of correctness of the algorithm and demonstrate its execution.
- Publication
- IEICE TRANSACTIONS on Information Vol.E105-D No.8 pp.1383-1392
- Publication Date
- 2022/08/01
- Publicized
- 2022/04/22
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2021EDP7235
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Masaaki OKADA
Tokyo University of Agriculture and Technology
Keiichi KANEKO
Tokyo University of Agriculture and Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masaaki OKADA, Keiichi KANEKO, "Minimal Paths in a Bicube" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 8, pp. 1383-1392, August 2022, doi: 10.1587/transinf.2021EDP7235.
Abstract: Nowadays, a rapid increase of demand on high-performance computation causes the enthusiastic research activities regarding massively parallel systems. An interconnection network in a massively parallel system interconnects a huge number of processing elements so that they can cooperate to process tasks by communicating among others. By regarding a processing element and a link between a pair of processing elements as a node and an edge, respectively, many problems with respect to communication and/or routing in an interconnection network are reducible to the problems in the graph theory. For interconnection networks of the massively parallel systems, many topologies have been proposed so far. The hypercube is a very popular topology and it has many variants. The bicube is a such topology and it can interconnect the same number of nodes with the same degree as the hypercube while its diameter is almost half of that of the hypercube. In addition, the bicube keeps the node-symmetric property. Hence, we focus on the bicube and propose an algorithm that gives a minimal or shortest path between an arbitrary pair of nodes. We give a proof of correctness of the algorithm and demonstrate its execution.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021EDP7235/_p
Copy
@ARTICLE{e105-d_8_1383,
author={Masaaki OKADA, Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={Minimal Paths in a Bicube},
year={2022},
volume={E105-D},
number={8},
pages={1383-1392},
abstract={Nowadays, a rapid increase of demand on high-performance computation causes the enthusiastic research activities regarding massively parallel systems. An interconnection network in a massively parallel system interconnects a huge number of processing elements so that they can cooperate to process tasks by communicating among others. By regarding a processing element and a link between a pair of processing elements as a node and an edge, respectively, many problems with respect to communication and/or routing in an interconnection network are reducible to the problems in the graph theory. For interconnection networks of the massively parallel systems, many topologies have been proposed so far. The hypercube is a very popular topology and it has many variants. The bicube is a such topology and it can interconnect the same number of nodes with the same degree as the hypercube while its diameter is almost half of that of the hypercube. In addition, the bicube keeps the node-symmetric property. Hence, we focus on the bicube and propose an algorithm that gives a minimal or shortest path between an arbitrary pair of nodes. We give a proof of correctness of the algorithm and demonstrate its execution.},
keywords={},
doi={10.1587/transinf.2021EDP7235},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - Minimal Paths in a Bicube
T2 - IEICE TRANSACTIONS on Information
SP - 1383
EP - 1392
AU - Masaaki OKADA
AU - Keiichi KANEKO
PY - 2022
DO - 10.1587/transinf.2021EDP7235
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2022
AB - Nowadays, a rapid increase of demand on high-performance computation causes the enthusiastic research activities regarding massively parallel systems. An interconnection network in a massively parallel system interconnects a huge number of processing elements so that they can cooperate to process tasks by communicating among others. By regarding a processing element and a link between a pair of processing elements as a node and an edge, respectively, many problems with respect to communication and/or routing in an interconnection network are reducible to the problems in the graph theory. For interconnection networks of the massively parallel systems, many topologies have been proposed so far. The hypercube is a very popular topology and it has many variants. The bicube is a such topology and it can interconnect the same number of nodes with the same degree as the hypercube while its diameter is almost half of that of the hypercube. In addition, the bicube keeps the node-symmetric property. Hence, we focus on the bicube and propose an algorithm that gives a minimal or shortest path between an arbitrary pair of nodes. We give a proof of correctness of the algorithm and demonstrate its execution.
ER -
English
