--------------------------------------------------------------- 
|                                                               |
|                VASSILIOS V. DIMAKOPOULOS                      |
|      Collective Communication Problems in MultiProcessors     |
|                                                               |
|                         PhD THESIS                            |
|      Department of Electrical and Computer Engineering        |
|                  University of Victoria                       |
|                         March 1996                            |
|                                                               |
 --------------------------------------------------------------- 


    Distributed-memory multiprocessors are based on a  collection
of   independent   processing   nodes   integrated   through    a
point-to-point interconnection network. The presence  of  locally
generated or maintained data spawns the need for solving  certain
information dissemination  problems,  also  known  as  collective
communications. They include: {\itshape broadcasting\/} where one
node needs to send one piece of  information  to  all  the  other
nodes; {\itshape scattering\/}  where  one  node  needs  to  send
different items of  information  to  different  nodes;  {\itshape
gathering\/}, the dual problem  of  scattering,  where  one  node
collects  data  from  every  other  node;   {\itshape   multinode
broadcasting\/} where every node needs to broadcast its own data;
{\itshape total exchange\/} where every  node  needs  to  perform
scattering, that is every node has a different message to send to
every other node.

    In  this  dissertation  we  study  the  above   communication
problems in packet-switched networks under two capability models:
{\itshape single-port\/} and {\itshape multiport\/}.  We  provide
solutions for specific networks as well as results applicable  to
general settings. In particular,  we  design  optimal  scattering
algorithms  for  extended  rings  and  two-dimensional  tori,  we
present optimal total exchange algorithms in  linear  arrays  and
rings and we solve optimally the aforementioned problems  in  fat
trees.

    For the multiport broadcasting problem we provide  a  general
construction of broadcast trees  in  multidimensional  (cartesian
product) networks. Under the  single-port  model  we  derive  new
lower bounds. Known bounds on this problem become  special  cases
of our result.

    For the single-port total exchange problem  we  construct  an
optimal algorithm for a large number of node symmetric  networks,
the class of Cayley graphs. Complete graphs,  rings,  circulants,
hypercubes, cube-connected cycles, butterflies,  belong  to  this
family and our construction is an optimal solution applicable  to
all these networks.

    A general theory is also  developed  for  total  exchange  in
multidimensional networks.  We  show  that  the  problem  can  be
decomposed to the simpler problem of performing total exchange in
individual dimensions. We provide optimality conditions  for  any
multidimensional network under  the  single-port  model  and  for
homogeneous networks under the multiport model. The  analysis  is
applicable to many popular interconnection networks such as  e.g.
hypercubes, meshes, tori (including $k$-ary $n$-cubes).