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

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