Frames: A Simple Characterization of Permutations Realized by Frequently Used Networks

Hasan Cam; Jose A.B. Fortes

doi:10.1109/12.381954

Frames: A Simple Characterization of Permutations Realized by Frequently Used Networks

Hasan Cam, Jose A.B. Fortes

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

Rearrangeable multistage networks such as the Benes network realize any permutation, yet their routing algorithms are not cost-effective. On the other hand, there exist inexpensive routing algorithms for nonrearrangeable networks, but no simple technique exists to characterize all the permutations realized on these networks. This paper introduces the concept of frame and shows how it can be used to characterize all the permutations realized on various multistage interconnection networks. They include subnetworks of baseline, Benes, and cascaded baseline and shuffle-exchange networks.

Original language	English
Pages (from-to)	695-697
Number of pages	3
Journal	IEEE Transactions on Computers
Volume	44
Issue number	5
DOIs	https://doi.org/10.1109/12.381954
State	Published - May 1995
Externally published	Yes

Bibliographical note

Funding Information:
This research was supported in part by the U.S. Office of Naval Research under contract No. OOO14-90-5-1483 and in part by the Innovative Science and Technology Office of the Strategic Defense Initiative Organization and was administered through the U.S. Office of Naval Research under contract No. 00014-88-k-0723.

Keywords

Network
balanced matrices
frames
permutations
rearrangeability
topological equivalence

ASJC Scopus subject areas

Software
Theoretical Computer Science
Hardware and Architecture
Computational Theory and Mathematics

Access to Document

10.1109/12.381954

Cite this

@article{fed1736b490844b1ac3a662f907500bb,

title = "Frames: A Simple Characterization of Permutations Realized by Frequently Used Networks",

abstract = "Rearrangeable multistage networks such as the Benes network realize any permutation, yet their routing algorithms are not cost-effective. On the other hand, there exist inexpensive routing algorithms for nonrearrangeable networks, but no simple technique exists to characterize all the permutations realized on these networks. This paper introduces the concept of frame and shows how it can be used to characterize all the permutations realized on various multistage interconnection networks. They include subnetworks of baseline, Benes, and cascaded baseline and shuffle-exchange networks.",

keywords = "Network, balanced matrices, frames, permutations, rearrangeability, topological equivalence",

author = "Hasan Cam and Fortes, \{Jose A.B.\}",

note = "Funding Information: This research was supported in part by the U.S. Office of Naval Research under contract No. OOO14-90-5-1483 and in part by the Innovative Science and Technology Office of the Strategic Defense Initiative Organization and was administered through the U.S. Office of Naval Research under contract No. 00014-88-k-0723.",

year = "1995",

month = may,

doi = "10.1109/12.381954",

language = "English",

volume = "44",

pages = "695--697",

journal = "IEEE Transactions on Computers",

issn = "0018-9340",

number = "5",

}

TY - JOUR

T1 - Frames

T2 - A Simple Characterization of Permutations Realized by Frequently Used Networks

AU - Cam, Hasan

AU - Fortes, Jose A.B.

N1 - Funding Information: This research was supported in part by the U.S. Office of Naval Research under contract No. OOO14-90-5-1483 and in part by the Innovative Science and Technology Office of the Strategic Defense Initiative Organization and was administered through the U.S. Office of Naval Research under contract No. 00014-88-k-0723.

PY - 1995/5

Y1 - 1995/5

N2 - Rearrangeable multistage networks such as the Benes network realize any permutation, yet their routing algorithms are not cost-effective. On the other hand, there exist inexpensive routing algorithms for nonrearrangeable networks, but no simple technique exists to characterize all the permutations realized on these networks. This paper introduces the concept of frame and shows how it can be used to characterize all the permutations realized on various multistage interconnection networks. They include subnetworks of baseline, Benes, and cascaded baseline and shuffle-exchange networks.

AB - Rearrangeable multistage networks such as the Benes network realize any permutation, yet their routing algorithms are not cost-effective. On the other hand, there exist inexpensive routing algorithms for nonrearrangeable networks, but no simple technique exists to characterize all the permutations realized on these networks. This paper introduces the concept of frame and shows how it can be used to characterize all the permutations realized on various multistage interconnection networks. They include subnetworks of baseline, Benes, and cascaded baseline and shuffle-exchange networks.

KW - Network

KW - balanced matrices

KW - frames

KW - permutations

KW - rearrangeability

KW - topological equivalence

UR - https://www.scopus.com/pages/publications/0029307653

U2 - 10.1109/12.381954

DO - 10.1109/12.381954

M3 - Article

AN - SCOPUS:0029307653

SN - 0018-9340

VL - 44

SP - 695

EP - 697

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

IS - 5

ER -

Frames: A Simple Characterization of Permutations Realized by Frequently Used Networks

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this