
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Minimal Paths in a Bicube
Masaaki OKADA Keiichi KANEKO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E105D
No.8
pp.13831392 Publication Date: 2022/08/01 Publicized: 2022/04/22 Online ISSN: 17451361
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)>>
Summary:
Nowadays, a rapid increase of demand on highperformance 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 nodesymmetric 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







