Efficient low-degree interconnection networks for parallel processing: Topologies, algorithms, VLSI layouts, and fault tolerance

Due to the impact of inter-processor communication mechanisms on the cost and performance of parallel computers, numerous interconnection topologies have been proposed and intensely studied. In this thesis, we propose the index-permutation (IP) graph model, a simple extension of the Cayley graph model, which provides insight into the design of novel communication-efficient networks, and serves as a framework that ties together many previously proposed interconnection topologies. We propose a variety of interconnection topologies that have low node degree, small diameter, and can efficiently emulate several popular topologies. We show that by properly selecting network parameters, parallel architectures based on IP graphs can balance system resources and satisfy the technology and application requirements. We develop a variety of efficient algorithms for the proposed networks, establishing the versatility of designs based on IP graphs. Additionally, we derive efficient very large scale integration (VLSI) layouts for a variety of interconnection networks, such as hypercubes, cube-connected cycles (CCC), butterfly networks, star graphs, hierarchical cubic networks, generalized hypercubes, as well as networks proposed in this thesis. We also deal with reliability problems in large interconnection networks by incorporating fault tolerance into the design of algorithms.