A Randomized Approach to the
Synthesis of Interconnection Networks
Vijay Lakamraju, I. Koren and C.M. Krishna
Department of Electrical and Computer Engineering
University of Massachusetts, Amherst 01003
Abstract
In embedded systems, as in distributed and parallel processing systems, the interconnection network(ICN) is as much a determinant of performance as the processors themselves. So, the design of the interconnection network plays a crucial role in the design process. Designing the interconnection network for a certain set of requirements can be a daunting task in itself. Considerable attention must be paid to ensure that the ICN adequately provides the services required of it, without increasing the complexity and cost of the system. We presents a simple, yet efficient, method to synthesize interconnection networks. The beauty of this approach lies in the flexibility of the pruning step, which can be changed to select only those ICNs which satisfy a certain set of requirements.
Applications running on a embedded system demand a certain set of performance requirements from the ICN. Applications could require the ICN to provide them with a small message delivery time or a network more resilient to failure. There are a multitude of ICNs to choose from but a ICN which is good with regard to one feature is not necessarily good with regard to another feature. For example, though the hypercube has good symmetry and easy routing algorithms, its degree grows logarithmically with the number of nodes and hence is not easily scalable. Furthermore, in embedded systems, where space is limited and the power budget is low, it is required to use just the required number of nodes and still obtain desired performance requirements. We present here a single class of networks, called random regular graphs, which exhibit surprisingly good properties. They can be synthesized for any given number of nodes and degree and they perform well with regard to almost all of the properties which characterize a good ICN. Through numerous simulations/experiments, we show that random regular graphs outdo the performance of most networks with regard to many important properties and perform within reasonable limits with regard to other properties.
A good ICN is characterized by a number of desirable properties. The smaller the average node-pair distance, lesser would be the time messages spend in the network and hence lesser the chances of congestion or wastage of power. A small degree corresponds to reduced wiring and I/O interfaces. A good fault tolerant network does not get disconnected easily; it degrades gracefully as nodes and links fail. It should be possible to construct the ICN with the required number of nodes with relative ease. We show that a randomized construction approach to the synthesis of ICNs yield surprisingly good results.
Most of the ICNs published in the literature are based on a set of equations which govern the connections between the nodes in the graph. The generation of a random graph does not follow any specified set of equations, but the two nodes to be joined by an edge are chosen at random. This process continues until all the nodes in the graph satisfy the following two requirements: (i) the degree of all the nodes is the same and equal to the specified value and (ii) no pair of nodes is joined by more than one edge and no self loops exist. The generated graph is then tested for connectedness. This sequence of steps generates a random regular graph but in order to generate ICNs with the desired set of properties, they have to pass through the pruning step. The pruning step sifts out those graphs which do not satisfy the requirements. So, the pruning step primarily contains algorithms to check to see if the requirements are satisfied. For example, if the requirement was a diameter value of k, then the pruning step finds the diameter of the randomly generated ICN and sifts out those with diameter value greater than k. This process of generating random graphs and pruning them is carried out till the designer has a considerable set of ICNs to choose from or until the process has been executed for a specified maximum number of iterations.
Experiments were performed to see how well regular random graphs perform with respect to diameter, average node-pair distance and fault tolerance. For each random graph of a particular size, 1000 random graphs were generated and those with the smallest diameter noted. Results showed that the diameter is a slowly rising function of the size of the graph. Moreover, random graphs with a certain degree have the least diameter when compared with networks of the same degree. This is a very interesting result in that it claims that if we generate a sizeable number of random graphs, then selecting the one with the least diameter will most certainly give a graph that has diameter less than most of the interconnection networks published in literature. Some of networks used for comparison are chordal rings, multi-tree structured graphs, hypercubes, meshes and torii. Reliability is an important criteria in the performance evaluation of any interconnection network. Four new measures, the probability of disconnection, diameter vulnerability, average node-pair distance vulnerability and maximum connected component size have been proposed. These measures provide a fuller characterization of the network. Experiments were performed with various graph sizes to check the performance of random graphs with respect to these measures. Here again results showed that random graphs of degree 3 and degree 4 performed better than their counterparts with respect to all the four measures. It was this unexpected behavior of random graphs that motivated their study in greater depth. Our experiments have quantified the above findings in detail.
The contributions of our work are two-fold: we present a simple, yet efficient, algorithm for the synthesis of ICNs which exhibit a certain desired set of properties. So, given the number of nodes in the network, the degree of each node and the required set of properties, the algorithm outputs a small set of ICNs from which the designer can pick one and use as the underlying network of the embedded system. We provide experimental evidence that those surprisingly good properties of random graphs apply not only to graphs of large sizes but also to those of small sizes i.e. tens or hundreds of nodes.