PRODUCT-SHUFFLE NETWORKS - TOWARD RECONCILING SHUFFLES AND BUTTERFLIES

We study product-shuffle (PS) net works, which are direct products of de Bruijn networks, as interconnection networks for parallel architectures. PS networks can be viewed as generalizing both butterfly-oriented networks (such as the butterfly and cube-connected cycles networks) and shuffle-oriented networks (such as the de Bruijn and shuffle-exchange networks), in the sense that . PS networks can emulate both butterfly-oriented and shuffle-oriented networks of any size, via emulations that are work preserving, i.e., preserve the processor-time product; . PS networks share many computationally valuable structural features of various butterfly- and shuffle-oriented networks, including pancyclicity, logarithmic diameter, and large complete binary tree subnetworks; . PS networks overcome certain computational deficiencies of butterfly- and shuffle-oriented networks, by containing as subnetworks moderate-size meshes and meshes of trees, networks which butterfly- and shuffle-oriented networks cannot emulate efficiently. Finally, PS networks attain their communication power at modest cost: they are 8-valent, and they enjoy VLSI layouts that consume only modestly more area than the best layouts of like-sized butterfly- and shuffle-oriented networks.