The search functionality is under construction.

The search functionality is under construction.

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

Masaaki OKADA

Tokyo University of Agriculture and Technology

Keiichi KANEKO

Tokyo University of Agriculture and Technology

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.

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 -