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

摘要：

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

关键词：图形处理器、图论、最小生成树、Prim算法、数据并行原语

所属期刊栏目：28

分类号：TP311.52(计算技术、计算机技术)

资助基金：国家"863"计划重点资助项目2009AA012201;上海市科委重大科技攻关资助项目08dz501600

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

页数：共4页

页码：1682-1684,1702