当前,集群是流行的并行计算平台,既具有所有并行计算都具备的一般特性,又具有自己独有的特性———节点计算资源的异构性、节点计算资源的非独占性、对节点间通信的敏感性。针对基于集群环境的并行计算,对非独占、异构、同步LogGP模型NHBL(Nondedicated Heterogeneous Barrier Log GP model)进行改进,提出了一种更实用的计算模型,即考虑网络拥塞的非独占、异构、同步LogGP模型NHCBL(Nondedicated Heterogeneous Barrier Log GP model considering Conges-tion)。NHCBL模型既比较准确地描述了并行计算的一般特性,又比较准确地描述了基于集群的并行计算独有的节点计算资源的异构性、节点计算资源的非独占性、对节点间通信的敏感性,其描述比NHBL模型更全面也更准确。
并行处理作为一个重要的研究领域，受到研究者越来越多的重视，而提高通信效率是一个重要的研究课题。本文针对程序中的通信效率问题，分析了产生通信拥挤的三个因素，即BSP程序引起的通信拥挤、网络拓扑结构引起的通信拥挤和网络嵌入算法不当引起的通信拥挤。在此基础上，选择这三个问题作为本文的主攻方向。经过三年的研究，在阅读大量文献的基础上，取得了理想的研究成果。针对并行程序的效率，本文提出了CSA-BSP模型，该模型能够引导程序设计者写出高效率的并行程序；针对互连网络，本文提出了RP（k）网络，该网络拓扑具有许多优良的性质，因而能够更好地提高通信效率；针对网络嵌入问题，本文设计了将环、Mesh和Hypercube通信模式嵌入RP（k）互连网络的高效算法，使得在这些网络上已开发的应用能够高效地移植到RP（K）网络上。
经过三年深入的研究，达到了预期的目的，取得了理想的结果，本文的主要创新点如下：
① 提出了一类基于Petersen图的互连网络拓扑结构RP（k）。该网络的连接度为5，直径为[k／2]+2；该网络具有短的网络直径、简单的拓扑结构、方便的路由策略；该网络硬件复杂度低、实现简单；在环、Mesh和Hypercube上设计的算法能够高效地嵌入RP（k）。同时，针对不同的互连网络规模，本文对该网络进行了扩展，提出了RP（P，k1，k2）网络拓扑，并讨论了其性质。
② 设计了RP（k）互连网络上的路由算法，主要设计了点点路由、置换路由、广播路由和All-to-all路由算法。这些算法的通信次数分别为[k／2]+2、k+5、[k／2]+2、k+5。这样，RP（k）网络和其上的路由算法为并行体系结构提供了一个实用的工具集。同时，在RP（P，k1，k2）网络上，本文也设计了以上四个通信模式的路由算法，它们的通信次数分别为[k2／2]+[k1／2]+2、4+m{k2，k1}+（k2-1）*（k1-1）、[k2／2]+[k1／2]+2和10*k1*k2-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）*2n-5]}条波长。同时，设计了一个将n维Hypercube嵌入环网络
暂无评论