Minimal Paths in a Bicube

Masaaki OKADA
Keiichi KANEKO

Publication
IEICE TRANSACTIONS on Information and Systems   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
Keyword: 
hypercube,  interconnection network,  massively parallel system,  shortest path,  topology,  

Full Text: PDF(436.5KB)>>
Buy this Article



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.


open access publishing via