Communication-efficient interconnection networks for parallel computations
Mounir Hamdi · 1992
This dissertation investigates a variety of interconnection networks for supporting interprocessor communication in parallel computer systems. First, a new class of interconnection networks, referred to as Recursive Complete graph Compounds (RCC), is presented. The RCC class of interconnection networks is constructed by connecting together a number of basic networks, referred to as atoms, through the recursive application of a complete graph compound. Its architectural properties are derived as a function of the architectural properties of the basic atom. A specific instance of this class, RCC-CUBE, where the basic atom is a hypercube, is shown to have desirable network properties such as small diameter, small degree, high bandwidth, and optimal connectivity and compares favorably to the hypercube and the hypernet$\sp{(1)}$* on these measures. Convenient routing strategies are derived for RCC, and RCC is shown to emulate well the hypercube. The time performance of RCC on various fundamental parallel data movement operations is analyzed and evaluated as a function of the performance on the basic atom used; and the performance of RCC-CUBE on these data movement operations is shown to be very close to that of the hypercube. The hardware cost and physical time performance are estimated for RCC-CUBE which exhibits superior performance on these measures. A specific instance of RCC, RCC-FULL, where the basic atom is a fully connected network, is shown to sort in O(log(N)) time and to emulate deterministically the CRCW PRAM model with O(log(N)) degradation in time performance; and can be considered as a universal interconnection network. A variant of the RCC class of interconnection networks, referred to as Recursive Graph Compounds (RGC), is presented for the augmentation of mesh connected computers to increase the efficiency of image processing algorithms. RGC has lower bandwidth than RCC but scales up better than RCC while maintaining constant degree. The efficiency of the mesh augmented with an RGC in executing important image processing algorithms increases substantially when compared to the efficiency of the mesh alone, and compares favorably to other related architectures. Finally, the notion of directional interconnection networks and their cost effectiveness has been elaborated through the analysis of the directional hypercube, Dcube, which is a hypercube where only directional links are utilized. Key architectural features are evaluated for Dcube, hypercube emulation and routing are explored, and Dcube performance is found to compare favorably with the hypercube. ftn*Parenthetical references placed superior to the line of text refer to the bibliography.