JISE

    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.