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

Josiah02

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