【作者】 刘方爱；

【导师】 刘志勇；

【作者基本信息】 中国科学院研究生院（计算技术研究所） ， 计算机系统结构， 2001， 博士

【摘要】 并行处理作为一个重要的研究领域，受到研究者越来越多的重视，而提高通信效率是一个重要的研究课题。本文针对程序中的通信效率问题，分析了产生通信拥挤的三个因素，即BSP程序引起的通信拥挤、网络拓扑结构引起的通信拥挤和网络嵌入算法不当引起的通信拥挤。在此基础上，选择这三个问题作为本文的主攻方向。经过三年的研究，在阅读大量文献的基础上，取得了理想的研究成果。针对并行程序的效率，本文提出了CSA-BSP模型，该模型能够引导程序设计者写出高效率的并行程序；针对互连网络，本文提出了RP（k）网络，该网络拓扑具有许多优良的性质，因而能够更好地提高通信效率；针对网络嵌入问题，本文设计了将环、Mesh和Hypercube通信模式嵌入RP（k）互连网络的高效算法，使得在这些网络上已开发的应用能够高效地移植到RP（K）网络上。 经过三年深入的研究，达到了预期的目的，取得了理想的结果，本文的主要创新点如下： ① 提出了一类基于Petersen图的互连网络拓扑结构RP（k）。该网络的连接度为5，直径为[k／2]+2；该网络具有短的网络直径、简单的拓扑结构、方便的路由策略；该网络硬件复杂度低、实现简单；在环、Mesh和Hypercube上设计的算法能够高效地嵌入RP（k）。同时，针对不同的互连网络规模，本文对该网络进行了扩展，提出了RP（P，k₁，k₂）网络拓扑，并讨论了其性质。 ② 设计了RP（k）互连网络上的路由算法，主要设计了点点路由、置换路由、广播路由和All-to-all路由算法。这些算法的通信次数分别为[k／2]+2、k+5、[k／2]+2、k+5。这样，RP（k）网络和其上的路由算法为并行体系结构提供了一个实用的工具集。同时，在RP（P，k₁，k₂）网络上，本文也设计了以上四个通信模式的路由算法，它们的通信次数分别为[k₂／2]+[k₁／2]+2、4+m{k₂，k₁}+（k₂-1）^*（k₁-1）、[k₂／2]+[k₁／2]+2和10^*k₁*k₂-4。 ③ 提出了将Ring和Mesh嵌入RP（k）网络的算法，证明了RP（k）网络是一个Hamiltonian图。考虑到网络的容错情况，当RP（k）网络中每个片有一个节点出现故障时，去掉故障节点和相应的边，得到互连网络RP-1（k），我们证明了该网络也是Hamiltonian图。因此，可以分别将10*k和9*k个节点的环嵌入到RP（k）和RP-1（k）网络中去。同时，我们也设计了将2-D mesh嵌入RP（k）网络的方法，取得了良好的嵌入性能。 ④ 基于光RP（k）网络，本文设计了一个实现n维Hypercube通信模式的算法，该算法最多需要max{2，[（5／3）^*2^n-5]}条波长。同时，设计了一个将n维Hypercube嵌入环网络更多还原

【Abstract】 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更多还原