Minimal Paths in a Bicube

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.

Automated summary

The rapid growth in demand for high-performance computing has led to increased research on massively parallel systems. Interconnection networks play a crucial role in these systems, with the bicube topology gaining attention for its properties such as maintaining node symmetry and providing shorter path lengths compared to the popular hypercube topology. Researchers have focused on proposing algorithms to find the shortest path between nodes in the bicube topology and have demonstrated their correctness in execution.