CONSTRUCTING GRAPHS FOR INTERCONNECTION NETWORK TOPOLOGIES

Abstract

One of the most difficult technical issues in the design of a parallel or distributed computer system is the interconnection network. The interconnection network must be designed carefully so as to derive the maximum benefit from having multiple processors and achieve maximum throughput and performance from the system at the lowest cost. This research focuses on one aspect of the interconnection problem, namely, the topology of an interconnection network. The topology determines to a large extent certain properties of the interconnection network such as the time delay m communication and the cost of constructing the network as well as the ease in incrementing the number of processor units. Although many topologies are known, there is no one which is the best. This is because the suitability of a particular topology depends not only on its properties but also on the applications for which it is intended. In this research, we are not actually looking for particular topologies as such, rather, we concentrate on developing a new construction method for generating topologies. We begin our work by examining the properties of good topologies and by providing a survey of current topologies used for interconnection networks. We then move on to develop a graph-theoretic method of constructing topological structures based on two classes of graphs known as group and quasi-group graphs and their products. We show that many well-known topologies, such as the hypercubes, the complete graphs and the toruses, can be constructed using this method, and that there are many others yet to be discovered which may turn out to be ideal topologies for certain applications. The method makes it easy to lay out the graph. The layout algorithm is straightforward and simple and has complexity O(n). We also consider the problem of routing in a group graph. We use the shortest path tree to perform routing in a group graph and discuss how we can implement shortest path tree routing in hardware using programmable logic arrays. We then extend hardware routing to product of quasi-group graphs. We further apply our construction method to fixed-degree topologies which maintain the same number of links connected to a processor as the size of the network grows, i.e. as more processors are added. We then show how we can define families of such fixed-degree graphs which are useful for incrementing the size of a parallel/distributed computer system with the same processor and memory units. We apply this method to the definition of the family of Petersen graphs, all with degree 3 and having the same structure as the Petersen graph Finally we discuss a number of possible future extensions to this research. These include generation of new topologies expressed in group or quasi-group graphs, derivation of general measures of performance for group and quasi-group graphs, study of families of fixed-degree group and quasi-group graphs, and investigation into other methods of combining graphs.