Permutation Sets and Routability of Multistage Interconnection Networks (MINs)

Multistage interconnection network is of the most important components for designing high-performance parallel supercomputers and for providing a powerful reconfigurable programming environment such that programming is independent of the actual computer architectures. In this research, some fundamental issues in multistage interconnection networks are investigated. Results, which promise great potential for the design of a reconfigurable high-speed parallel supercomputer with an architecture independent programming environment, are presented. First, two characteristic functions are introduced to characterize networks in a proposed class of multistage interconnection networks. Message routing schemes, network partitioning algorithms, and many other useful properties are presented. Next, a more general class of multistage interconnection networks and two more general characteristic functions are introduced. The transformation rules for one network to emulate another in the class is presented such that the programs and algorithms developed on one machine can be reused on others. Then, the permutation capability (in terms of non-conflict parallel communication) of each network is presented through the concept of network partitioning. An algorithm to determine the admissibility of any permutation on a multistage interconnection network is developed. Finally, a fault-tolerant reconfiguration scheme is presented for parallel processor systems which employ multistage interconnection networks for interprocessor communication.