快速最小生成树 Sollin 求解算法

摘要：

最小生成树算法在计算机网络、信息安全等领域中有着广泛的应用，目前比较普遍的求解算法有 Prim 算法和 Kruskal 算法，但这两种算法由于本身的数据结构特性和迭代过程的相关性限制而难以并行化，因而无法有效地利用通用 GPU 并行架构进行并行化加速。Sollin算法虽然是最古老的最小生成树算法之一，但是在算法中经过初始化的森林迭代过程，每次迭代可以同时扩展合并多棵最小生成树，经过数次扩展和合并，最终由初始森林合并为一棵树，一旦成功扩展，这棵树一定是最小生成树。在扩展合并的过程中，每次迭代中每棵树的扩展和合并过程相互独立，这一特征使 Sollin 算法具有较好的并行性，可以利用目前流行的 GPU 并行架构进行快速求解优化。正因如此，文章针对传统 CPU 执行的串行 Sollin 算法，结合适用于通用 GPU 并行运算的数据结构特性，在提出可扩展树这一并行适用的数据存储结构的基础上，提出了一种基于可扩展树的快速扩展、合并最小生成树的方法，并针对通用 GPU 平台进行了实现。我们采用多组不同规模的测试数据进行实验。结果表明，相对传统串行 Sollin 最小生成树求解算法，该算法在用于较大数据规模的情况中具有明显的性能提升，同由 CPU 执行的传统串行方案相比，文章提出的方案获得了10至18倍的加速度。

关键词：GPGPU、最小生成树、Sollin 算法、CUDA

分类号：TP309(计算技术、计算机技术)

资助基金：国家自然科学基金[61103068]、教育部博士点基金[20110072120017]、信息安全国家重点实验室开放课题[2013-3-5]、上海科委优秀技术带头人计划课题、中央高校基本科研业务费专项资金

在线出版日期：2014-08-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：87-91