近年来，大规模并行计算(MPC)模型引起了广泛关注。然而，MPC模型中的大多数分布式并行图算法都是针对静态图设计的。动态图算法可以比相应的静态图算法更有效地处理图的变化。此外，MPC模型中的一些并行动态图算法(例如图连通性)已经提出并显示出优于并行静态算法的优势。然而，目前尚无适用于MPC模型的动态全对最短路径(APSP)算法。

为了解决这个问题，华强生领导的研究小组在《计算机科学前沿》上发表了他们的研究成果。

该团队在MPC模型中设计了一种全动态APSP算法，其轮复杂度较低，比所有现有的静态并行APSP算法都快。所提出的并行全动态APSP算法基于顺序动态APSP算法，该算法在MPC模型中直接实现会导致较大的轮复杂度，效率低下。此外，存储此顺序动态APSP算法的这些数据结构所需的总内存太大。

为了降低轮复杂度，使总内存占用尽可能小，该团队对原有的顺序动态APSP算法进行了改进，将图算法(例如受限Bellman-Ford算法)与代数方法(例如半环上的矩阵乘法)相结合，以降低轮复杂度和总内存占用。并在MPC模型中将其与现有的静态APSP算法进行了比较，证明了其有效性。

版权说明：本站所有作品图文均由用户自行上传分享，仅供网友学习交流。若您的权利被侵害，请联系我们

标签：