ON THE DECYCLING PROBLEM IN HIERARCHICAL HYPERCUBES
Antoine Bossard · Journal of Interconnection Networks · 2013
Due to the huge number of CPU nodes involved in modern supercomputers, efficient CPU connection is challenging, and legacy simple network topologies such as hypercubes are no more suitable for physical reasons. The hierarchical hypercube (HHC) has been designed as a topology for interconnection network of massively parallel systems. An HHC is effectively able to link many nodes while retaining a low degree and a small diameter compared to a hypercube of the same size. In this paper, we address a fundamental problem inside an HHC, the decycling problem, which consists of finding a set of nodes as small as possible such that excluding these nodes from the network ensures a cycle-free topology. This problem has many important applications such as lock-free resource allocation and concurrent access. So, we propose in this paper an efficient algorithm finding in an HHC a decycling set of competitively small size.