并行最优路径算法及并行层次通信模型LogGP(h)研究

随着以数据为中心的超级计算时代的到来，在各种以图为数据结构的应用中数据规模日益增大，数据量的急剧增加使得串行最优路径算法成为应用的性能瓶颈，已不能满足大规模最优路径求解的实时性要求。然而，最优路径求解算法的并行化却对图的类型有高度的敏感性，尤其是对一些稀疏图，如交通网络图，目前并没有很好的算法提供足够的并行性[1]。对此，本文提出、实现和优化了一种新的基于网络划分和迭代更新的并行最优路径算法，并用真实的交通网络数据在IBM JS21集群和曙光5000A两种平台上对算法进行了评测。测试结果表明，该算法具有较好的性能，在IBM JS21集群上，使用16个进程会出现约15倍的加速比；而在曙光5000A上，算法使用同一节点内的16个核获得了约20倍的超线性加速比。 本文的另一部分研究工作集中在新的并行计算模型方面。研究者所提出的并行计算模型有很多，从基于共享存储器结构的第一代并行计算模型，到针对于分布式存储结构的第二代并行模型，再到考虑存储层次性的第三代并行计算模型，却较少有模型考虑到通信的层次性。 大规模集群系统往往由几百到几千、甚至上万个节点构成，网络拓扑结构复杂。在这样的大规模集群系统中，点对点通信的性能并不总是一致的。这种非一致的通信性能随着网络拓扑的复杂化呈现层次性的变化，本文首先提出了层次化非一致性带宽和延迟(Hierarchical Communication Latency and Bandwidth：HCLB)的概念，并以进程映射对MPI Allgather的四种算法性能影响说明了由多核结构引起的通信层次性；之后，本文将大规模集群系统中的HCLB现象模型化，提出LogGP(h)并行通信模型。LogGP(h)在LogGP模型基础上，通过参数h将网络拓扑结构抽象到模型中，很好的表达了通信层次性。本文在具有8个刀片的IBM JS21集群上对点对点通信和集合通信开销进行模型分析和实际测试，实验结果表明，LogGP(h)较未引入参数h的LogGP模型更精确。

聚合通信中LogGP模型和α+nβ模型的改进

针对高性能计算机实际获取性能低的突出问题,在大规模科学计算和工程应用中对占主要作用的聚合通信进行了研究。通过对聚合通信Reduce算法的理论分析与试验比较,找出LogGP模型和α+nβ模型的关系表达式,并在描述聚合通信算法的理论时间复杂度时,提出了对LogGP模型和α+nβ模型的补充和改进,这些工作对聚合通信算法的理论研究和设计具有重要的意义。

聚合通信模型的测试与分析

聚合通信的性能影响着大规模并行数值计算软件的整体效率,它是基于点对点消息传递实现的。可以通过选择点对点通信模型来描述聚合通信。一个恰当的模型可以为聚合通信算法提供精确的定量分析,有助于算法的设计与研究。论文通过对若干聚合通信典型算法的测试与分析,尝试比较与定量分析两种点对点通信模型对聚合通信的描述精度。