GPU加速的并行Prim最小生成树算法优化

"这篇论文探讨了基于GPU的并行最小生成树算法设计与实现，主要关注如何提高Prim算法在GPU环境下的执行效率。作者提出了一种适用于GPU架构的压缩邻接表图表示方法，并开发了名为min-reduction的数据并行原语，以此优化算法的关键步骤，缩短查找时间，提升整体性能。实验结果显示，相较于传统CPU实现和未使用原语的算法，该方法有显著的性能优势。该研究得到了国家‘863’计划和上海市科委项目的资助，作者来自解放军信息工程大学信息工程学院，研究方向涉及分布式计算和GPU通用计算。" 在并行计算领域，最小生成树（Minimum Spanning Tree, MST）算法是解决图论问题中的一个重要工具，用于寻找连通图中边权重之和最小的树形子图。Prim算法是一种经典的MST构造算法，它从一个顶点开始逐步扩展，每次选择与已构建树连接的边中权重最小的一条，直至覆盖所有顶点。 在GPU（Graphics Processing Unit）平台上实现并行计算能极大地提高计算速度，但传统的Prim算法并不直接适应GPU的并行计算架构。针对这一问题，论文提出的压缩邻接表图表示形式可以更有效地利用GPU的并行处理能力。这种表示方式减少了存储需求，同时使得边的查找和比较操作更为高效。 min-reduction数据并行原语是论文的核心贡献之一，它是一种专门针对GPU设计的并行操作，能够在大规模数据集上快速找到最小值。在Prim算法的关键步骤中，这个原语能够并行地找出与已构建树相邻的所有顶点中边权重最小的那一条，大大减少了查找的时间复杂度，从而提升了整体算法的执行效率。 实验结果证明，采用这种新的算法设计和原语，不仅在计算速度上有显著提升，而且在资源利用率和并行性方面也表现出优势。这为GPU上的图算法优化提供了一个有效的范例，对于解决大规模图数据处理问题有着重要的实践意义。 总结起来，这篇论文通过创新的图表示和并行原语，成功地解决了GPU上Prim算法的效率问题，为并行计算和图论领域的研究提供了新的思路和技术支持。