Self-routing technique in perfect-shuffle networks using control tags

Author

Huang, Shing-Tsaan ; Tripathi, Satish K.

Author_Institution

Inst. of Comput. Manage. & Decision Sci., Nat. Tsing-Hua Univ., Hsin-Chu, Taiwan

Volume

37

Issue

2

fYear

1988

fDate

2/1/1988 12:00:00 AM

Firstpage

251

Lastpage

256

Abstract

The self-routing technique using control tags on multiple-pass perfect-shuffle networks is generalized. In particular, they show that bit-permute-complement permutations can be realized and unscrambled in (2n-1) passes or less, where n=log₂N , N being the number of terminals on either side. They also show that most of the frequently used permutations are in the intersection of omega-realizing and inverse-omega-realizing sets and can be realized and unscrambled in n passes

Keywords

computational complexity; multiprocessor interconnection networks; set theory; bit-permute-complement permutations; computational complexity; control tags; inverse-omega-realizing sets; multiple-pass perfect-shuffle networks; multiprocessor interconnection networks; permutation networks; self-routing technique; set intersections; unscrambling; Automatic testing; Broadcasting; Communication system control; Fault diagnosis; Intelligent networks; Performance evaluation; System testing; Technical Activities Guide -TAG; Voting;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.2159

Filename

2159