本文關(guān)鍵詞：一種基于GPU加速的高效有向斯坦納樹算法研究

  更多相關(guān)文章： 有向斯坦納樹問題 組合優(yōu)化算法 近似算法 GPU并行計算 最短路徑算法 多址路徑選擇

【摘要】：有向斯坦納樹問題的定義如下:給定一個有向圖G=(V,A)和一個特定的根節(jié)點Vr?以及一個終點集合X?V(|X|=k),找到一棵以r為根,并且覆蓋X集合中所有節(jié)點的最小代價樹。很多問題都能夠被抽象為有向斯坦納樹問題,如超大規(guī)模集成電路(VLSI)的布線,線長(wire-length)的估計以及網(wǎng)絡(luò)中的服務(wù)質(zhì)量布線等等問題。因此,求解有向斯坦納樹問題具有重要的研究意義。由于斯坦納樹問題是NP難題,因此主流的研究均集中于求解問題的近似解。本文針對該問題提出了一種高效的近似斯坦納樹算法HEA。本算法對TM算法進行了改進,修正了其在有向圖下的時間復雜度。同時消除了一些冗余計算,使得其時間復雜度由O(kn2)降到了O(kn)。然后又改進了Charikar算法的子樹連接方式降低了在低層數(shù)時的斯坦納樹誤差,并采用了初始樹枚舉的策略進一步提高了算法的精確度。最終HEA算法在最差情況下的O(k2n3)時間內(nèi)取得了2k-?的近似率。實驗結(jié)果表明,相比一些傳統(tǒng)的有向斯坦納樹算法來說,既提高了速度,也提高了精度。為了進一步加速該算法,本文又加入了GPU并行計算的元素。首先本文將二叉堆優(yōu)化的最短路徑算法并行化,采用多線程的方式為每個節(jié)點計算以其為源點到圖上所有點之間的最短路徑。然后本文又對2層樹構(gòu)造算法模塊進行并行化,該算法為每一棵初始樹啟動一個線程,同步地計算出所有的斯坦納樹候選。GPU并行計算的加入進一步縮短了斯坦納樹的運算時間。與精度表現(xiàn)比較優(yōu)異的Hseih算法相比,在并未使近似率降低的前提下,串行的HEA算法比該算法在速度上要快至少25倍。在加入GPU加速的元素后,HEA算法的最短路徑計算部分又取得了10至40倍的加速,而并行2層樹構(gòu)造算法部分則取得了1.23~7.88的加速比。
【關(guān)鍵詞】：有向斯坦納樹問題 組合優(yōu)化算法 近似算法 GPU并行計算 最短路徑算法 多址路徑選擇
【學位授予單位】：哈爾濱工業(yè)大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O157.5;TP332
【目錄】：

• 摘要4-5
• Abstract5-8
• 第1章 緒論8-15
• 1.1 課題背景及研究的目的和意義8-10
• 1.2 國內(nèi)外關(guān)于有向斯坦納樹問題的研究現(xiàn)狀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 國內(nèi)外關(guān)于并行斯坦納樹算法的研究現(xiàn)狀12-13
• 1.3.1 精確求解算法12-13
• 1.3.2 近似求解算法13
• 1.4 本文的主要研究內(nèi)容13-14
• 1.5 論文的結(jié)構(gòu)安排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 本章小結(jié)18-19
• 第3章 一種斯坦納樹近似算法HEA的提出19-33
• 3.1 引言19-20
• 3.2 2層斯坦納樹構(gòu)造算法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 本章小結(jié)31-33
• 第4章 HEA算法的并行化實現(xiàn)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 本文中樹的存儲結(jié)構(gòu)37
• 4.2.5 APSP問題的并行求解37-39
• 4.3 并行奇偶排序的實現(xiàn)39-40
• 4.4 并行2層樹構(gòu)造算法的實現(xiàn)40-41
• 4.5 本章小結(jié)41-42
• 第5章 實驗結(jié)果以及分析42-51
• 5.1 引言42
• 5.2 測試數(shù)據(jù)來源介紹42-43
• 5.3 串行測試結(jié)果與分析43-45
• 5.4 并行測試結(jié)果與分析45-49
• 5.4.1 并行最短路徑算法45-46
• 5.4.2 并行奇偶排序算法46-47
• 5.4.3 并行2層樹構(gòu)造算法47-49
• 5.5 本章小結(jié)49-51
• 結(jié)論51-53
• 參考文獻53-57
• 攻讀碩士學位期間發(fā)表的論文及其它成果57-59
• 致謝59

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前1條

1 張珂良;李佳佳;陳鋼;吳百鋒;;奇偶合并排序的數(shù)據(jù)級并行實現(xiàn)[J];小型微型計算機系統(tǒng);2012年06期

中國碩士學位論文全文數(shù)據(jù)庫 前1條

1 張舒;模式識別并行算法與GPU高速實現(xiàn)研究[D];電子科技大學;2009年

，

本文編號：1028358