基于GPU的并行最小生成树算法的设计与实现

Design and implementation of GPU-based parallel minimum spanning tree algorithm

针对目前并行Prim最小生成树算法效率不高的问题,在分析现有并行Prim算法的基础上,提出了适于GPU架构的压缩邻接表图表示形式,开发了基于GPU的min-reduction数据并行原语,在NVIDIA GPU上设计并实现了基于Prim算法思想的并行最小生成树算法。该算法通过使用原语缩短关键步骤的查找时间,从而获得较高效率。实验表明,相对于传统CPU实现算法和不使用原语的算法,该算法具有较明显的性能优势。

Considering current parallel Prim＇s MST algorithms＇ limited speedup,based on analyzing existing parallel MST algorithms,this paper used compress adjacency list graph representation suited to GPU architecture,developed GPU-based min-reduction data parallel primitive,and designed parallel Prim＇s MST algorithm on NVIDIA GPU.The algorithm shortened the finding time via using primitives in the key step so achieved higher efficiency.Experimental results show that it obtains evident performance improvement over the traditional CPU implementation and non-primitives GPU implementation.