Topological Structure and Analysis of Interconnection Networks
==========================================================================
Chapter 2
Design
Methodology of Topological Structure of Interconnection Networks
Due to the recent advances in hardware technology, especially in
the advent of VLSI circuit technology, it is now feasible to build a large and very complex interconnection networks connecting
tens of thousands of processing elements for an MPS capable of executing parallel algorithms. For example, the Connection
Machine contains as many as $2^{16}$ processors. Thus, a systematic method is very necessary to design a topological
structure for such very large scale interconnection networks.
We have known that the topological structure of an interconnection network is a graph. The so-called design of the topological structure
of an interconnection network is essentially to construct a graph that satisfies prescribed requirements.
We will, in this chapter, introduce three major methods for constructing graphs: line graphical technique, Cayley method and
cartesian product technique, which can be actually referred to three special classes of graphs: line graphs, Cayley graphs and cartesian
product graphs. We will study key features of interest in such graphs, including regularity, connectivity, diameter, enlerian and
hamiltionian properties. We will also briefly discuss a basic problem in optimal design of networks, the
(d, k)-graph problem, i.e., for given d and k, how large order can be for a graph with the maximum degree
d and diameter at most k.
Throughout this chapter, all graphs are connected or strongly connected if they are not specially noted.
|
