The paper studies product-shuffle (PS) networks, 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 (1)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; (2)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; (3)PS networks overcome certain computational deficiencies of butterfly- and shuffle-oriented networks, by containing a subnetworks moderate-size 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.
