Mathematical theory of multistage interconnection networks analysis
Zhixi Fang · Lincoln (University of Nebraska) · 1984
A mathematical model for evaluation and analysis of multistage interconnection networks is developed from the point of view of permutation group. The concepts of network equivalence and isomorphism are introduced. The necessary and sufficient criteria for equivalence and isomorphism are developed and properties of equivalent classes of multistage interconnection networks are investigated. These properties are used to analyze the routing techniques and to investigate the conflict resolution problem in multistage interconnection networks. Two methods of conflict resolution are analyzed. A graph model of conflict resolution problem for baseline network is developed. It is shown that the conflict resolution problem in multistage interconnection networks is NP-complete. Three heuristic algorithms for conflict resolution problem are developed and their time complexity and average number of passes are investigated for different size of inputs. The transfer algorithm among the control functions of equivalent and isomorphic interconnection networks is developed. Applications of these results to parallel processing systems are also discussed.