TITLE:   Decomposition of Total Exchange for 
	 Multidimensional Interconnects
	 
AUTHORS: Vassilis V. Dimakopoulos and 
	 Nikitas J. Dimopoulos
	 
IN:      1996 International Conference on Parallel 
	 Processing, August 12-16, 1996, 
	 pp. I17-I21 

	 

ABSTRACT 

Total exchange is an important collective communication 
problem in multiprocessor interconnection networks. It 
involves the dissemination of distinct messages from 
every node to every other node. We present a novel 
theory for solving the problem in any multidimensional
(cartesian product) network. We construct a general 
algorithm and provide optimality conditions. It is seen
that many of the popular topologies, including hypercubes,
k-ary n-cubes and general tori satisfy these conditions.
The results we present here apply to the single-port
model.