论文研究基于GPU的并行最小生成树算法的设计与实现.pdf

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