Homogeneous product networks for processor interconnection
Antonio Fernández Anta · 1994
This dissertation proposes the cartesian product operation for graphs as a unifying framework for the study of interconnection networks. In this research, we concentrate on homogeneous product networks and generate a large set of important general results which yield the characteristics of the product network from those of its factor network. From these characteristics, a network can be evaluated and different networks can be meaningfully compared. The results of this study are grouped in four main areas. First, we obtain structural properties of homogeneous product networks. We have compiled results on the diameter, vertex degree, connectivity, and partitionability of these networks. Then, we have addressed the study of other properties and derived results on the bisection width and crossing number. To generate these results we introduce a new structural property of a graph, the maximal congestion, which seems to be interesting for future research. Second, we have obtained simple but powerful results on embeddings between homogeneous product networks. These results allow to transfer the computational power of one network to the other by emulation. Third, we have developed algorithms that can be implemented in any homogeneous product network without variation. These algorithms cover several important problems: sorting, summation, matrix multiplication, and minimum-weight spanning-tree finding. Some of them can be readily modified to solve many other problems. Finally, we have studied the VLSI layout complexity of homogeneous product networks, obtaining lower bounds on the area and wire length they require and presenting methods to produce optimal-area layouts. We have applied these results to several instances of homogeneous product networks, showing how simply the results can be used to evaluate a network. Then, we have concentrated in the study of three of them: the product of complete binary trees, shuffle-exchange graphs, and de Bruijn graphs. These three homogeneous product networks have been shown to be very powerful and interesting candidates for being used as inter-connection networks.