Josiah02 发表于 2024-9-4 18:05:49

并行计算模型中的改进算法比现有的静态并行APSP算法速度更快

近年来,大规模并行计算 (MPC) 模型引起了广泛关注。然而,MPC 模型中的大多数分布式并行图算法都是针对静态图设计的。动态图算法可以比相应的静态图算法更有效地处理图的变化。此外,MPC 模型中的一些并行动态图算法(例如图连通性)已经提出并显示出优于并行静态算法的优势。然而,目前尚无适用于 MPC 模型的动态全对最短路径 (APSP) 算法。
为了解决这个问题,华强生领导的研究小组在《计算机科学前沿》上发表了他们的研究成果。
该团队在 MPC模型中设计了一种全动态 APSP算法,其轮复杂度较低,比所有现有的静态并行 APSP 算法都快。所提出的并行全动态 APSP 算法基于顺序动态 APSP 算法,该算法在 MPC 模型中直接实现会导致较大的轮复杂度,效率低下。此外,存储此顺序动态 APSP 算法的这些数据结构所需的总内存太大。
为了降低轮复杂度,使总内存占用尽可能小,该团队对原有的顺序动态APSP算法进行了改进,结合图算法(例如受限Bellman-Ford算法)和代数方法(例如半环上的矩阵乘法),降低了轮复杂度和总内存占用,并在MPC模型中与现有的静态APSP算法进行了对比,证明了该算法的有效性。

页: [1]
查看完整版本: 并行计算模型中的改进算法比现有的静态并行APSP算法速度更快