Research On The Topologies And Communcation Algorithms Of Interconnection Networks For Multicomputers

The design of the interconnection architecture is one of the most important tasks for a high performance parallel computer. The choice of the interconnection networks determines several important characteristics of the final system, such as performance, programmability, reliability, scalability, and complexity of physical layout.In this dissertation, an ECG model is proposed, which is an extension of Cayley graph model. The ECG model not only provides insight into the design of novel communication-efficient networks, but also serves as a framework that ties together many previously proposed interconnection network topologies. By properly selecting base node, base graph and generators, we can construct new and efficient interconnection networks for new applications.We propose two new interconnection networks models based on the ECG model. Comparing with other popular interconnection networks, when an equal number of nodes are concerned, they have attractive cost and performance trade-off, and can emulate popular interconection networks with constant dilation. An improved hierarchical cube network is also proposed. It has shorter communication diameter and strong fault-tolerant ability. Also, we propose a new class of homogeneous expanding node networks with the distinct characteristic of constant degree. It is easy to expand without increasing the node degree. When an equal number of nodes are concerned, its diameter is only a half of mesh. Detailed performance analysis and routing algorithms for these networks are given in this dissertation.Star graph interconnection network has received much attention as an...