并行最优路径算法及并行层次通信模型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模型更精确。