SCIENCE@home

Product-Shuffle Networks: Toward Reconciling Shuffles and Butterflies

A. Rosenberg

Published 1992 in Discrete Applied Mathematics

ABSTRACT

Abstract We study 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 • • 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-20 of 20 references · Page 1 of 1

CITED BY

Showing 1-55 of 55 citing papers · Page 1 of 1