Shivnandan D. Kaushik, Sanjay Sharma, Chua-Huang Huang,
Jermy R. Johnson#, Robert W. Johnson** and P. Sadayappan
Department of Computer and Information Science
The Ohio State University
Columbus, OH 43210
#Department of Mathematics and Computer Science
Philadelphia, PA 19104
**Department of Computer Science
St. Cloud State University
St. Cloud, MN 56301
The theory of tensor products has been used for designing and implementing block recursive numerical algorithms on shared-memory vector multiprocessors such as the Cray-Y/MP. In this paper, we present an algebraic theory based on tensor products for modeling direct interconnection networks. The development of this model is expected to facilitate the development of a methodology for mapping algorithms expressed in tensor product form onto distributed-memory architectures. A network is defined as a tuple that includes a set of processors and a set of permutations expressed in tensor product notation which collectively represent the network topology. The tensor product of networks is defined so as to facilitate the recursive construction of complex networks from simple networks. Using the tensor product of networks, the properties of simple networks, such as network embedding, can be easily extended to complex networks. We start with a simple ring network and recursively construct two-dimensional torus and hypercube networks. Network embeddings for the ring network are extended in a straight-forward fashion to those for two-dimensional torus and hypercube networks. A formal model for specifying and verifying network embedding is presented. Using this model and the tensor product representation, the embeddings of the ring and the two-dimensional torus into the hypercube are specified and verified. Algorithm mapping using the tensor product formulation is demonstrated by mapping matrix transposition and matrix multiplication onto different networks.
Keywords: tensor product, block recursive algorithm, direct interconnection network, algorithm mapping, network embedding
Received December 15, 1994; revised June 22, 1995.
Communicated by Shing-Tsaan Huang.
*This work was supported in part by DARPA, order number 7898, monitored by NIST under grant number 60NANB1D1151, and by DARPA, order number 7899, monitored by NIST under grant number 60NAB1D1150.