research-article

On the Rearrangeability of 2(Iog2N) -1 Stage Permutation Networks

Author:

Kyungsook Yoon LeeAuthors Info & Claims

IEEE Transactions on Computers, Volume 34, Issue 5

Pages 412 - 425

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

Published: 01 May 1985 Publication History

Publisher Site

Abstract

For any parallel computer systems which consist of many processing elements and memories, interconnection networks provide communication paths among processing elements and memories. Both the rearrangeability proof and the control algorithm are well known for the Benes network, which is intrinsically symmetric. However, there has been little progress for the case of nonsymmetric networks of similar hardware requirements.

Cited By

View all

Jain TSchneider KTalpin J(2016)Verifying the concentration property of permutation networks by BDDsProceedings of the 14th ACM-IEEE International Conference on Formal Methods and Models for System Design10.5555/3343414.3343420(43-53)Online publication date: 18-Nov-2016
https://dl.acm.org/doi/10.5555/3343414.3343420
Milder PHoe JPüschel MBenini LDe Micheli GAl-Hashimi BMueller W(2009)Automatic generation of streaming datapaths for arbitrary fixed permutationsProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874891(1118-1123)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.5555/1874620.1874891
Püschel MMilder PHoe J(2009)Permuting streaming data using RAMsJournal of the ACM10.1145/1502793.150279956:2(1-34)Online publication date: 17-Apr-2009
https://dl.acm.org/doi/10.1145/1502793.1502799
Show More Cited By

On the Rearrangeability of 2(Iog2N) -1 Stage Permutation Networks

Recommendations

On the rearrangeability of 2(log₂N)−1 stage permutation networks
Interconnection networks for high-performance parallel computers
Rearrangeability of Tandem Cascade of Banyan-Type Networks

The cascade of two baseline networks in tandem is a rearrangeable network. The cascade of two omega networks appended with a certain interconnection pattern is also rearrangeable. These belong to the general problem: for what banyan-type network (i.e., ...
On rearrangeability of tandem connection of banyan-type networks

A multistage interconnection network (MIN) consisting of 2 × 2 nodes constructs a nonblocking switch if the network is rearrangeable. When a 2ⁿ × 2ⁿ bit-permuting network is rearrangeable with the minimum depth of 2n - 1, the initial (resp. final) n ...

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 34, Issue 5

May 1985

98 pages

ISSN:0018-9340

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 May 1985

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jain TSchneider KTalpin J(2016)Verifying the concentration property of permutation networks by BDDsProceedings of the 14th ACM-IEEE International Conference on Formal Methods and Models for System Design10.5555/3343414.3343420(43-53)Online publication date: 18-Nov-2016
https://dl.acm.org/doi/10.5555/3343414.3343420
Milder PHoe JPüschel MBenini LDe Micheli GAl-Hashimi BMueller W(2009)Automatic generation of streaming datapaths for arbitrary fixed permutationsProceedings of the Conference on Design, Automation and Test in Europe10.5555/1874620.1874891(1118-1123)Online publication date: 20-Apr-2009
https://dl.acm.org/doi/10.5555/1874620.1874891
Püschel MMilder PHoe J(2009)Permuting streaming data using RAMsJournal of the ACM10.1145/1502793.150279956:2(1-34)Online publication date: 17-Apr-2009
https://dl.acm.org/doi/10.1145/1502793.1502799
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
Kannan R(1997)A Pipelined Single-Bit Controlled Sorting Network with O(N log^2 N) Bit ComplexityProceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution10.5555/839292.843056Online publication date: 9-Apr-1997
https://dl.acm.org/doi/10.5555/839292.843056
Gu QTamaki H(1997)Routing a Permutation in the Hypercube by Two Sets of Edge Disjoint PathsJournal of Parallel and Distributed Computing10.1006/jpdc.1997.135844:2(147-152)Online publication date: 1-Aug-1997
https://dl.acm.org/doi/10.1006/jpdc.1997.1358
Gu QTamaki H(1996)Routing a Permutation in the Hypercube by Two Sets of Edge-Disjoint PathsProceedings of the 10th International Parallel Processing Symposium10.5555/645606.661013(561-567)Online publication date: 15-Apr-1996
https://dl.acm.org/doi/10.5555/645606.661013
Lee K(1987)A New Benes Network Control AlgorithmIEEE Transactions on Computers10.1109/TC.1987.167697036:6(768-772)Online publication date: 1-Jun-1987
https://dl.acm.org/doi/10.1109/TC.1987.1676970

Abstract

Cited By

Recommendations

On the rearrangeability of 2(log2N)−1 stage permutation networks

Rearrangeability of Tandem Cascade of Banyan-Type Networks

On rearrangeability of tandem connection of banyan-type networks

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations

On the rearrangeability of 2(log₂N)−1 stage permutation networks