----------------------------------------------
|          TECHNICAL REPORT ECE-96-2           |
|                January 1996                  |
| Dept. of Electrical and Computer Engineering |
|           University of Victoria             |
 ----------------------------------------------

TITLE:   A Theory for Total Exchange in Multidimensional 
         Interconnection Networks

AUTHORS: V. V. Dimakopoulos and N. J. Dimopoulos

NOTE:    Submitted for publication

ABSTRACT

Total exchange (or multiscattering) is one  of  the  important
collective   communication    problems    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.  These  networks
have been adopted as cost-effective interconnection structures
for distributed-memory multiprocessors. We construct a general
algorithm for {\itshape  single-port\/} networks  and  provide
conditions under which it behaves optimaly. It  is  seen  that
many of the popular topologies, including hypercubes,  $k$-ary
$n$-cubes and  general  tori  satisfy  these  conditions.  The
algorithm is also extended to homogeneous networks with  $2^k$
dimensions  and  with  {\itshape   multiport\/}  capailitites.
Optimality conditions are also given for this model.

KEYWORDS: Collective communications, interconnection networks,
          multidimensional networks, packet-switched networks,
	  total exchange