The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
De nos jours, une augmentation rapide de la demande en calcul haute performance provoque des activités de recherche enthousiastes concernant les systèmes massivement parallèles. Un réseau d'interconnexion dans un système massivement parallèle interconnecte un grand nombre d'éléments de traitement afin qu'ils puissent coopérer pour traiter des tâches en communiquant entre autres. En considérant un élément de traitement et une liaison entre une paire d'éléments de traitement comme un nœud et un bord, respectivement, de nombreux problèmes concernant la communication et/ou le routage dans un réseau d'interconnexion sont réductibles aux problèmes de la théorie des graphes. Pour les réseaux d'interconnexion des systèmes massivement parallèles, de nombreuses topologies ont été proposées jusqu'à présent. L’hypercube est une topologie très populaire et comporte de nombreuses variantes. Le bicube est une telle topologie et il peut interconnecter le même nombre de nœuds avec le même degré que l'hypercube tandis que son diamètre est presque la moitié de celui de l'hypercube. De plus, le bicube conserve la propriété de symétrie des nœuds. Par conséquent, nous nous concentrons sur le bicube et proposons un algorithme qui donne un chemin minimal ou le plus court entre une paire arbitraire de nœuds. Nous donnons une preuve de l’exactitude de l’algorithme et démontrons son exécution.
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.
Copier
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
Copier
@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},}
Copier
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 -