Low Diameter Regular Graph as a Network Topology in Direct and Hybrid Interconnection Networks

Performance of a parallel computer depends on the computation power of the processors and the performance of the communication network connecting them. With the increasing scale and compute power of today's parallel machines, interprocessor communication becomes the bottleneck. Communication performance depends on the network topology and routing scheme for packets. This master's thesis explores the use of low diameter regular (LDR) graph as a topology for interconnection networks. We generate graphs having same number of nodes and connections per node as the hypercube, a widely used network topology. These graphs have lower diameter and lower average internode distance than the corresponding hypercubes, which implies that on an average, packets travel for a lower number of hops. With a good routing scheme this would reduce the average message latency and lead to better communication performance. We run experiments with this new topology in a parallel simulation framework for interconnection networks, BigNetSim. We show that LDR graphs achieve better performance than equivalent hypercubes for standard network traffic patterns. We have also developed a framework for implementing hardware collectives and we compare collective communication performance for different topologies. We implement a hybrid topology of a fat-tree and a LDR graph and evaluate its performance in comparison with a hybrid of a fat-tree and a hypercube.

Yogesh Mehta, "Low diameter regular graph as a network topology in direct and
hybrid interconnection networks", Dept. of Computer Science, University of 
Illinois, 2005.

@mastersthesis{YogeshMSThesis,
        author="Yogesh Mehta",
        title="Low diameter regular graph as a network topology in direct and hybrid interconnection networks",
        year="2005",
        school = {Dept. of Computer Science, University of Illinois},
}