--------------------------------------------------------------- 
|                                                               |
|                VASSILIOS V. DIMAKOPOULOS                      |
|       Processor Allocation and Message Broadcasting in        |
|            Hypercycle Interconnection Networks                |
|                                                               |
|                        MASc THESIS                            |
|      Department of Electrical and Computer Engineering        |
|                  University of Victoria                       |
|                         June 1992                             |
|                                                               |
 --------------------------------------------------------------- 


    Hypercycles   are   a   class   of   static    multiprocessor
interconnection  networks  with  the  ability  of  matching   the
processing node and communication link restrictions  of  a  large
number of applications. This is in contrast  with  other  popular
interconnection   topologies   including   hypercubes,    $k$-ary
$n$-cubes and generalized hypercubes. The  regular  structure  of
hypercycles  allows  for  simple  routing  strategies  which  are
responsible for the communication between the  processing  nodes.
Broadcasting a message to all the processors in the network is an
essential part of  the  routing  engine  and  an  algorithm  that
implements it for hypercycles constitutes part  of  this  thesis.
The proposed algorithm is analysed and proven to be optimal.

    Processor allocation which is the second and  most  important
subject of this  study  is  a  major  issue  for  achieving  high
performance in multiprocessor systems. This  theoretical  problem
has topology-specific solutions and various  strategies  to  deal
with it for the hypercycles case are presented here.  Comparisons
between the proposed strategies are made  using  both  analytical
and computer simulation  tools.  Part  of  this  thesis  was  the
implementation of a simulator to  help  with  these  comparisons.
Hypercubes, being a subset of hypercycles, can benefit  from  the
proposed strategies which exhibited better performance  than  the
ones with similar complexity proposed in the current literature.