More Web Proxy on the site http://driver.im/

research-article

The Universality of the Shuffle-Exchange Network

Authors:

Tse-Yun FengAuthors Info & Claims

IEEE Transactions on Computers, Volume 30, Issue 5

Pages 324 - 332

https://doi.org/10.1109/TC.1981.1675790

Published: 01 May 1981 Publication History

Abstract

This paper has focused on the realization of every arbitrary permutation with the shuffle-exchange network. Permutation properties of shuffle-exchange networks are studied and are used to demonstrate several universal networks. It is concluded that 3(log2 N) -1 passes through a single-stage regular shuffle exchange network are sufficient to realize every arbitrary permutation where N is network size. A routing algorithm is also developed to calculate control settings of the shuffle-exchange switches for the permutation realization. Three optimal universal networks, namely, expanded direct- connection shuffle-exchange network, multiple-pass omega network, and modified shuffle-exchange network are then exploited for better interconnection purposes. In addition, this work specifies the inherent relationship between the shuffle-exchange network and the Benes binary network so that designers can have a broad prospect.

References

[1]

S. W. Golomb, "Permutations by cutting and shuffling," SIAM Rev., vol. 3, pp. 293-297, Oct. 1961.

Digital Library

[2]

M. C. Pease, "An adaptation of the fast Fourier transform for parallel processing," J. Ass. Comput. Mach., vol. 15, pp. 252-264, Apr. 1968.

Digital Library

[3]

H. S. Stone, "Parallel processing with the perfect shuffle," IEEE Trans. Comput., vol. C-20, pp. 153-161, Feb. 1971.

Digital Library

[4]

D. H. Lawrie, "Access and alignment of data in an array processor," IEEE Trans. Comput., vol. C-24, pp. 1145-1155, Dec. 1975.

Digital Library

[5]

T. Lang and H. S. Stone, "A shuffle-exchange network with simplified control," IEEE Trans. Comput., vol. C-25, pp. 55-65, Jan. 1976.

Digital Library

[6]

T. Lang, "Interconnections between processors and memory modules using the shuffle-exchange network," IEEE Trans. Comput., vol. C-25, pp. 496-503, May 1976.

Digital Library

[7]

H. J. Siegel, "The universality of various types of SIMD machine interconnection networks," in Proc. 4th Annu. Symp. Comput. Arch., Mar. 1977., pp. 70-79.

Digital Library

[8]

D. S. Parker, "Notes on shuffle/exchange-type switching networks," IEEE Trans. Comput., vol. C-29, pp. 213-222, Mar. 1980.

Digital Library

[9]

V. Benes, Mathematical Theory of Connecting Networks. New York: Academic, 1965.

[10]

M. C. Pease, "The indirect binary n-cube microprocessor array," IEEE Trans. Comput., vol. C-26, pp. 458-473, May 1977.

Digital Library

[11]

C. Wu and T. Feng, "On a class of multistage interconnection networks," IEEE Trans. Comput., vol. C-29, pp. 694-704, Aug. 1980; also in Proc. 1978 Int. Conf. on Parallel Processing, pp. 197-205.

Digital Library

[12]

H. J. Siegel and S. D. Smith, "Study of multistage SIMD interconnection networks," in Proc. 5th Annu. Symp. Comput. Arch., Apr. 1978, pp. 223-229.

Digital Library

[13]

D. Opferman and N. Tsao-Wu, "On a class of rearrangeable switching networks," Bell Syst. Tech. J., vol. 50, pp. 1579-1618, May-June 1971.

[14]

S. Andersen, 'The looping algorithm extended to base 2' rearrangeable switching networks," IEEE Trans. Commun., vol. COM-25, pp. 1057-1063, Oct. 1977.

[15]

J. Lenfant, "Parallel permutations of data: A Benes network control algorithm for frequently used permutations," IEEE Trans. Comput., vol. C-27, pp. 637-647, July 1978.

Digital Library

[16]

T. Feng, "Data manipulating functions in parallel processors and their implementations," IEEE Trans. Comput., vol. C-23, pp. 309-318, Mar. 1974.

Digital Library

[17]

D. Nassimi and S. Sahni, "Parallel algorithms to set-up the Benes permutation network," in Proc. Workshop on Interconnection Networks for Parallel and Distributed Processing. Apr. 1980, pp. 70-71.

[18]

C. Wu and T. Feng, "The reverse-exchange network," IEEE Trans. Comput., vol. C-29, pp. 801-811, Sept. 1980; also in Proc. 1979 Int. Conf. on Parallel Processing. pp. 160-174.

Digital Library

Cited By

Bilardi GScquizzato MSilvestri F(2018)A Lower Bound Technique for Communication in BSPACM Transactions on Parallel Computing10.1145/31817764:3(1-27)Online publication date: 20-Feb-2018
https://dl.acm.org/doi/10.1145/3181776
Bilardi GScquizzato MSilvestri F(2012)A lower bound technique for communication on BSP with application to the FFTProceedings of the 18th international conference on Parallel Processing10.1007/978-3-642-32820-6_67(676-687)Online publication date: 27-Aug-2012
https://dl.acm.org/doi/10.1007/978-3-642-32820-6_67
Vitter J(2008)Algorithms and data structures for external memoryFoundations and Trends® in Theoretical Computer Science10.1561/04000000142:4(305-474)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1561/0400000014
Show More Cited By

The Universality of the Shuffle-Exchange Network
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

Recommendations

Invariant Properties of the Shuffle-Exchange and a Simplified Cost-Effective Version of the Omega Network

Let O denote the set of permutations performable by a pass through the Omega network (an n-stage shuffle-exchange network), and let p denote an arbitrary permutation of N = 2n elements. In this paper we characterize the sets {p|pO = O} (called left ...
Shuffling with the Illiac and PM2I SIMD Networks

Two SIMD single-stage interconnection networks which have been proposed and studied in the literature are the Illiac type and PM2I. The ability of the Illiac and PM2I networks to perform the shuffle data permutation in an SIMD machine with N processors ...
A mathematical abstraction of the rearrangeability conjecture for shuffle-exchange networks

Shuffle-exchange networks have received a great deal of attention as interconnecting networks for parallel computing. One unsolved problem is the minimum by number of stages required by a shuffle-exchange network with 2^n inputs and outputs to be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 30, Issue 5

May 1981

75 pages

ISSN:0018-9340

Issue’s Table of Contents

Copyright © 1981.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 May 1981

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bilardi GScquizzato MSilvestri F(2018)A Lower Bound Technique for Communication in BSPACM Transactions on Parallel Computing10.1145/31817764:3(1-27)Online publication date: 20-Feb-2018
https://dl.acm.org/doi/10.1145/3181776
Bilardi GScquizzato MSilvestri F(2012)A lower bound technique for communication on BSP with application to the FFTProceedings of the 18th international conference on Parallel Processing10.1007/978-3-642-32820-6_67(676-687)Online publication date: 27-Aug-2012
https://dl.acm.org/doi/10.1007/978-3-642-32820-6_67
Vitter J(2008)Algorithms and data structures for external memoryFoundations and Trends® in Theoretical Computer Science10.1561/04000000142:4(305-474)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1561/0400000014
He RDelgado-Frias J(2007)Fault Tolerant Interleaved Switching Fabrics For Scalable High-Performance RoutersIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2007.110918:12(1727-1739)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1109/TPDS.2007.1109
Vitter J(2002)External memory algorithmsHandbook of massive data sets10.5555/779232.779243(359-416)Online publication date: 1-Jan-2002
https://dl.acm.org/doi/10.5555/779232.779243
Park BWatson K(1994)On the Rearrangeability of Reverse Shuffle/Exchange NetworksProceedings of the 1994 International Conference on Parallel Processing - Volume 0110.1109/ICPP.1994.139(113-116)Online publication date: 15-Aug-1994
https://dl.acm.org/doi/10.1109/ICPP.1994.139
Vitter JShriver E(1994)Algorithms for parallel memory, IAlgorithmica10.1007/BF0118520712:2-3(110-147)Online publication date: 1-Sep-1994
https://dl.acm.org/doi/10.1007/BF01185207
Yalamanchili SAggarwal J(1987)A Characterization and Analysis of Parallel Processor Interconnection NetworksIEEE Transactions on Computers10.1109/TC.1987.167696136:6(680-691)Online publication date: 1-Jun-1987
https://dl.acm.org/doi/10.1109/TC.1987.1676961
Huang STripathi S(1986)Finite State Model and Compatibility TheoryIEEE Transactions on Computers10.1109/TC.1986.167680035:7(591-601)Online publication date: 1-Jul-1986
https://dl.acm.org/doi/10.1109/TC.1986.1676800
Agrawal D(1983)Graph Theoretical Analysis and Design of Multistage Interconnection NetworksIEEE Transactions on Computers10.1109/TC.1983.167629532:7(637-648)Online publication date: 1-Jul-1983
https://dl.acm.org/doi/10.1109/TC.1983.1676295
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents