DocumentCode :
922357
Title :
Rearrangeable three-stage interconnection networks and their routing properties
Author :
Douglass, Barry G.
Author_Institution :
Dept. of Electr. Eng., Texas A&M Univ., College Station, TX, USA
Volume :
42
Issue :
5
fYear :
1993
fDate :
5/1/1993 12:00:00 AM
Firstpage :
559
Lastpage :
567
Abstract :
A rearrangeable network is an interconnection network which can achieve all possible permutations of its inputs´ connections to its outputs. One class of rearrangeable networks, which have been studied are Clos three-stage networks. Earlier procedures to route such networks rapidly require an excessive amount of hardware, either in the network itself or in the device required to compute the routing. A class of rearrangeable three-stage networks which is both compact and which can be routed quickly is introduced, along with a routing scheme. Switches are added to the network so as to reduce the interdependence between the switch settings, allowing faster routing while only moderately increasing network complexity. A network with O(Nlog 1.5N) hardware and O(log1.5N ) depth is derived from O(log2.5N) switch setup time
Keywords :
computational complexity; multiprocessor interconnection networks; Clos three-stage networks; interconnection network; network complexity; permutations; rearrangeable network; routing scheme; switch settings; Communication switching; Computer networks; Hardware; Multiprocessing systems; Multiprocessor interconnection networks; Parallel processing; Routing; Sorting; Switches; Telephony;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.223675
Filename :
223675
Link To Document :
بازگشت