Hierarchical swapped networks: efficient low-degree alternatives to hypercubes and generalized hypercubes

In this paper, we propose a new class of interconnection networks called hierarchical swapped networks (HSNs). We show that some subclasses of HSNs can efficiently emulate hypercubes, or generalized hypercubes, while having node degrees significantly smaller than the emulated networks. In particular, a suitably constructed HSN can emulate a hypercube or generalized hypercube with constant slowdown under the single-dimension communication model and asymptotically optimal slowdown with respect to its node degree under the all-port communication model. As a consequence, we obtain a variety of efficient algorithms on HSNs through emulation, thus proving the versatility of HSN. Some subclasses of HSNs are also shown to have asymptotically optimal diameters with respect to their node degrees. HSNs appear to be attractive low-degree alternatives to hypercubes and generalized hypercubes for general-purpose parallel computers