一种基于GPU加速的高效有向斯坦纳树算法研究

发布时间：2017-10-14 02:06

  本文关键词：一种基于GPU加速的高效有向斯坦纳树算法研究

  更多相关文章： 有向斯坦纳树问题 组合优化算法 近似算法 GPU并行计算 最短路径算法 多址路径选择

【摘要】：有向斯坦纳树问题的定义如下:给定一个有向图G=(V,A)和一个特定的根节点Vr?以及一个终点集合X?V(|X|=k),找到一棵以r为根,并且覆盖X集合中所有节点的最小代价树。很多问题都能够被抽象为有向斯坦纳树问题,如超大规模集成电路(VLSI)的布线,线长(wire-length)的估计以及网络中的服务质量布线等等问题。因此,求解有向斯坦纳树问题具有重要的研究意义。由于斯坦纳树问题是NP难题,因此主流的研究均集中于求解问题的近似解。本文针对该问题提出了一种高效的近似斯坦纳树算法HEA。本算法对TM算法进行了改进,修正了其在有向图下的时间复杂度。同时消除了一些冗余计算,使得其时间复杂度由O(kn2)降到了O(kn)。然后又改进了Charikar算法的子树连接方式降低了在低层数时的斯坦纳树误差,并采用了初始树枚举的策略进一步提高了算法的精确度。最终HEA算法在最差情况下的O(k2n3)时间内取得了2k-?的近似率。实验结果表明,相比一些传统的有向斯坦纳树算法来说,既提高了速度,也提高了精度。为了进一步加速该算法,本文又加入了GPU并行计算的元素。首先本文将二叉堆优化的最短路径算法并行化,采用多线程的方式为每个节点计算以其为源点到图上所有点之间的最短路径。然后本文又对2层树构造算法模块进行并行化,该算法为每一棵初始树启动一个线程,同步地计算出所有的斯坦纳树候选。GPU并行计算的加入进一步缩短了斯坦纳树的运算时间。与精度表现比较优异的Hseih算法相比,在并未使近似率降低的前提下,串行的HEA算法比该算法在速度上要快至少25倍。在加入GPU加速的元素后,HEA算法的最短路径计算部分又取得了10至40倍的加速,而并行2层树构造算法部分则取得了1.23~7.88的加速比。
【关键词】：有向斯坦纳树问题 组合优化算法 近似算法 GPU并行计算 最短路径算法 多址路径选择
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5;TP332
【目录】：

• 摘要4-5
• Abstract5-8
• 第1章 绪论8-15
• 1.1 课题背景及研究的目的和意义8-10
• 1.2 国内外关于有向斯坦纳树问题的研究现状10-12
• 1.2.1 Charikar算法10-11
• 1.2.2 TM算法11
• 1.2.3 Hsieh算法11-12
• 1.2.4 Greedy FLAC算法12
• 1.3 国内外关于并行斯坦纳树算法的研究现状12-13
• 1.3.1 精确求解算法12-13
• 1.3.2 近似求解算法13
• 1.4 本文的主要研究内容13-14
• 1.5 论文的结构安排14-15
• 第2章 GPU并行计算简介15-19
• 2.1 引言15
• 2.2 GPU介绍15-17
• 2.3 CUDA简介17-18
• 2.4 Graphviz工具使用18
• 2.5 本章小结18-19
• 第3章 一种斯坦纳树近似算法HEA的提出19-33
• 3.1 引言19-20
• 3.2 2层斯坦纳树构造算法20-23
• 3.2.1 算法的提出及原理20-22
• 3.2.2 算法的伪代码及详细步骤22-23
• 3.3 改进的TM算法23-27
• 3.3.1 算法的提出及原理23-26
• 3.3.2 算法的详细步骤以及伪代码26-27
• 3.4 初始树枚举27-30
• 3.4.1 算法的提出及原理27-29
• 3.4.2 算法的详细步骤以及伪代码29-30
• 3.5 HEA算法的近似率30-31
• 3.6 HEA算法的时间复杂度31
• 3.7 本章小结31-33
• 第4章 HEA算法的并行化实现33-42
• 4.1 引言33-34
• 4.2 并行最短路径算法34-39
• 4.2.1 GPU上图的表达方式34-35
• 4.2.2 Dijkstra算法35-36
• 4.2.3 GPU上的二叉堆表示36-37
• 4.2.4 本文中树的存储结构37
• 4.2.5 APSP问题的并行求解37-39
• 4.3 并行奇偶排序的实现39-40
• 4.4 并行2层树构造算法的实现40-41
• 4.5 本章小结41-42
• 第5章 实验结果以及分析42-51
• 5.1 引言42
• 5.2 测试数据来源介绍42-43
• 5.3 串行测试结果与分析43-45
• 5.4 并行测试结果与分析45-49
• 5.4.1 并行最短路径算法45-46
• 5.4.2 并行奇偶排序算法46-47
• 5.4.3 并行2层树构造算法47-49
• 5.5 本章小结49-51
• 结论51-53
• 参考文献53-57
• 攻读硕士学位期间发表的论文及其它成果57-59
• 致谢59

【参考文献】

中国期刊全文数据库 前1条

1 张珂良;李佳佳;陈钢;吴百锋;;奇偶合并排序的数据级并行实现[J];小型微型计算机系统;2012年06期

中国硕士学位论文全文数据库 前1条

1 张舒;模式识别并行算法与GPU高速实现研究[D];电子科技大学;2009年

，

本文编号：1028358