The Computation Models And Interconnection Networks In High Efficient And Parallel Computing Systems

Parallel processing is one of the most interesting research areas in computer technology and has been investigated widely. Among those investigated subjects, how to enhance the communication efficiency is regarded as one of the key topics in parallel processing. The communication efficiency can be improved by several means, for example, designing efficient algorithms, writing efficient programs utilizing characteristics of computer hardware, and designing high efficient interconnection networks. Here we choose parallel computation models and interconnection networks as the key topics of our researches. Firstly, by improving the BSP model, the CSA-BSP model is proposed and it can guide programmers to write high efficient parallel programs. Secondly the topologies of interconnection networks are investigated and the RP(k) network is invented. The RP(k) network has many good properties, like simple topology, lower connectivity degree and smaller network diameter. Based on this network, the routing algorithms are designed.During the research, much work has been done. On interconnection networks, starting from some basic network topologies, for example, Ring, Torus, Hypercube and their routing strategies, some complex networks, like Butterfly networks, the Caylay graph networks, Hierarchy networks and Star-graph networks, are analyzed step by step. At the same time, the parallel computation models, mainly on shared memory models, hierarchy models, and message-passing models, are investigated. These understandings have contributed a lot to my reseaches.The main achievements of this thesis can be summarized as follows:â‘ Based on the Petersen graph and the Ring network, the RP(k) network is proposed. Itsconnectivity degree is 5 and its diameter is 「k/2」 + 2. Compared with 2-D Torus, the RP(k)network has many good properties, like short diameter, simple topology, flexible routing strategies. It is a practical interconnection network. To enlarge the size of the RP(k) network, the RP(P,k₁,k₂) network is proposed and its properties are analyzed.â‘¡Based on the RP(k) network, the routing algorithms have been designed, which include point-to-point routing, One-to-all routing, permutation routing, and All-to-all routing.The efficiencies of these algorithms are 「k/2」 + 2,「k/2」 + 2,.k+5 and k+5 respectively. Thusthe RP(k) network and its routing algorithms consist of a practical tool set for parallel architectures. Based on the RP(P,k₁,k₂) network, the above four routing algorithms are also...