--------------------------------------------------------------- 
|                                                               |
|                 SIVAKUMAR RADHAKRISHNAN                       |
|    Topological Optimization and Deadlock-Free Routing in      |
|        Interconnection Networks Based On Hypercycles          |
|                                                               |
|                        PhD THESIS                             |
|      Department of Electrical and Computer Engineering        |
|                  University of Victoria                       |
|                        Nov. 1995                              |
|                                                               |
 --------------------------------------------------------------- 


    In this dissertation, we address some of  the  architectural,
algorithmic and communication issues involved in  the  design  of
parallel  computer  systems.  The  performance  of  large   scale
parallel   computers    depends    mainly    on    interprocessor
communication. As a result, considerable effort has been directed
towards the design of efficient interconnection networks, routing
algorithms and hardware routers. This work  specifically  focuses
on hypercycle based interconnection networks which are a class of
multidimensional, symmetric graphs that  are  generalizations  of
several popular topologies  such  as  the  ring,  hypercubes  and
generalized hypercubes. Hypercycles  are  products  of  circulant
graphs with simple routing schemes. Their ability, given a  fixed
degree, to  form  alternate  graphs  makes  them  attractive  for
space/mass  limited  applications,  e.g.  on-board  computers  in
satellites, autonomous vehicles, avionics,  robotic  control  and
submersibles.

    One of the issues that  confronts  the  design  of  efficient
interconnection networks  is  finding  a  topology  with  minimum
average distance, diameter and the degree*diameter  product.  New
results on the  synthesis  of  cost  optimal  hypercycle  network
topologies minimizing the above metrics are~presented.

    Graph embeddings permit a parallel  machine  having  a  given
interconnection  topology  to  simulate  different  computational
structures such as chains, cycles, grids and trees. An  efficient
algorithm for embedding complete binary  trees  in  a  hypercycle
network with unit dilation is  proposed.  The  dissertation  also
investigates the problem of embedding Hamiltonian  cycles  and  a
generalized  $m$-ary  gray  code  algorithm  for  hypercycles  is
evolved.

    Routing  algorithms  for  interconnection  networks  must  be
efficient and free from deadlocks.  Two  algorithms,  namely  the
$e$-cube and prioritized mixed $e$-cube \&  backtracking  schemes
are proposed and shown to  be  deadlock  preventing.  The  system
architecture of  a  routing  engine  to  implement  deadlock-free
routing algorithms is proposed. A VLSI chip that  implements  the
$e$-cube  algorithm  has  been  designed  in  1.2  $\mu  m$  CMOS
technology for a 4-dimensional hypercycle network with a measured
throughput in excess of 15 million decisions per second.

    Finally, a framework for rapidly prototyping  policy-specific
controllers for the routing engine using a novel general  purpose
hardware description  language  called  {\sc  CoDeL}  (Controller
Design Language) has been developed. Using {\sc CoDeL}, a circuit
switching based $e$-cube routing controller has been  synthesized
and mapped to  a  Xilinx  4010PC84  chip.  Test  results  of  the
controller indicate that a link in a source-destination path  can
be established in less than 3 $\mu s$.