Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.9 No.1, pp.1-26 (March 1993)
An Algebraic Theory for Modeling
Multistage Interconnection Networks*

S. D. Kaushik, S. Sharma and C.-H. Huang
Department of Computer and Information Science
The Ohio State University
Columbus, OH 43210

We use an algebraic theory based on tensor products to model multistage interconnection networks. This algebraic theory has been used for designing and implementing block recursive numerical algorithms on shared-memory vector multiprocessors. In this paper, we focus on the modeling of multistage interconnection networks. The tensor product representations of the baseline network, the reverse baseline network, the indirect binary n-cube network, the generalized cube network, the omega network, and the flip network are given. We present the use of this theory for specifying and verifying network properties such as network partitioning and topological equivalence. Algorithm mapping using tensor product formulation is demonstrated by mapping the matrix transposition algorithm onto multistage interconnection networks.

Keywords: tensor product, parallel architecture, multistage interconnection network, partitionability, topological equivalence, algorithm mapping

Received December 12, 1992; revised April 15, 1993.
Communicated by Chuan-lin Wu.
*This work was supported in part by DARPA, order number 7899, monitored by NIST under grant number 60NANB1D1150 and Ohio State University Seed Grant, No. 221337.