An Analysis of Connectivity of k-ary n-cube m-diag Interconnection Networks
Didier Badouel, Charles A. W\"uthrich, and Eugene L. Fiume
Computer System Research Institute
University of Toronto
CSRI Technical Report #266
Abstract
The comparison between different topologies in interconnection networks is
a debated issue among highly parallel machine designers, since opposing
parameters influence the network performance. This paper presents a new
model, k-ary n-cube m-diag, which generalizes existing k-ary n-cube
topologies to include hexagonal networks and their $n$-dimensional
extensions. A performance analysis based on this model is conducted,
showing that the increase of connectivity in low-dimensional networks by
means of diagonal links results in better latency and throughput in the
network. An algorithm for routing messages in k-ary n-cube m-diags is
proposed, showing the relative ease of performing this task on such
topologies.
Index Terms:Interconnection networks, highly parallel systems,
topological comparisons, performance analysis, routing algorithms.
------------------
The file topos.ps.Z is a compressed postscript file resulting from using
dvips on a latex-produced file. It should print (a little slowly because
of the figures) on any postscript printer after decompressing it using
the UNIX uncompress command.
If you take a copy of this, please let me know who you are so that I have
a sense of where it's going.
Eugene Fiume.
This report was made available for anonymous ftp by:
elf@csri.toronto.edu