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

被引：5

作者：

郭绍忠

王伟

王磊

机构：

[1] 解放军信息工程大学信息工程学院

来源：

计算机应用研究 | 2011年 / 28卷 / 05期

关键词：

图形处理器; 图论; 最小生成树; Prim算法; 数据并行原语;

D O I：

暂无

中图分类号：

TP391.41 [];

学科分类号：

080203 ;

摘要：

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

引用

页码：1682 / 1684+1702 +1702

页数：4

共 7 条

[1] A new parallel algorithm forminimum spanning tree problem. ROHIT S,ARUN N,SHANKAR B. Proc of International Confe-rence on High Performance Computing . 2009
[2] Parallel Prim’s algorithm ondense graphs with a novel extension. EKATERINA G,LAXMIKANT V K. . 2007
[3] Linear algebraic primitives for parallel computing on largegraphs. BULLUC A. . 2010
[4] Fast shared-memory algorithms for computing the minimumspanning forest of sparse graphs. BADER D A,CONG G. J. Parallel Distrib. Comput . 2006
[5] Optimizing parallel reduction in CUDA. HARRIS M. http://developer.download.nvidia.com/compute/cuda/11/Website/Data-Parallel Algorithms.html . 2007
[6] Onthe limits of GPU acceleration. VUDUCY R,CHANDRAMOWLISHWARANY A,CHOI J,et al. http://www.use-nix.org/event/hotpar10/tech/full_papers/Vuduc.pdf . 2010
[7] Fast minimum spanningtree for large graphs on the GPU. VINEET V,HARISH P,PATIDAR S,et al. Proc of Conference on HighPerformance Graphics . 2009

← 1 →