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

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

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

• 摘要4-5
• Abstract5-8
• 第1章 緒論8-15
• 1.1 課題背景及研究的目的和意義8-10
• 1.2 國(guó)內(nèi)外關(guān)于有向斯坦納樹(shù)問(wè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 國(guó)內(nèi)外關(guān)于并行斯坦納樹(shù)算法的研究現(xiàn)狀12-13
• 1.3.1 精確求解算法12-13
• 1.3.2 近似求解算法13
• 1.4 本文的主要研究?jī)?nèi)容13-14
• 1.5 論文的結(jié)構(gòu)安排14-15
• 第2章 GPU并行計(jì)算簡(jiǎn)介15-19
• 2.1 引言15
• 2.2 GPU介紹15-17
• 2.3 CUDA簡(jiǎn)介17-18
• 2.4 Graphviz工具使用18
• 2.5 本章小結(jié)18-19
• 第3章 一種斯坦納樹(shù)近似算法HEA的提出19-33
• 3.1 引言19-20
• 3.2 2層斯坦納樹(shù)構(gòu)造算法20-23
• 3.2.1 算法的提出及原理20-22
• 3.2.2 算法的偽代碼及詳細(xì)步驟22-23
• 3.3 改進(jìn)的TM算法23-27
• 3.3.1 算法的提出及原理23-26
• 3.3.2 算法的詳細(xì)步驟以及偽代碼26-27
• 3.4 初始樹(shù)枚舉27-30
• 3.4.1 算法的提出及原理27-29
• 3.4.2 算法的詳細(xì)步驟以及偽代碼29-30
• 3.5 HEA算法的近似率30-31
• 3.6 HEA算法的時(shí)間復(fù)雜度31
• 3.7 本章小結(jié)31-33
• 第4章 HEA算法的并行化實(shí)現(xiàn)33-42
• 4.1 引言33-34
• 4.2 并行最短路徑算法34-39
• 4.2.1 GPU上圖的表達(dá)方式34-35
• 4.2.2 Dijkstra算法35-36
• 4.2.3 GPU上的二叉堆表示36-37
• 4.2.4 本文中樹(shù)的存儲(chǔ)結(jié)構(gòu)37
• 4.2.5 APSP問(wèn)題的并行求解37-39
• 4.3 并行奇偶排序的實(shí)現(xiàn)39-40
• 4.4 并行2層樹(shù)構(gòu)造算法的實(shí)現(xiàn)40-41
• 4.5 本章小結(jié)41-42
• 第5章 實(shí)驗(yàn)結(jié)果以及分析42-51
• 5.1 引言42
• 5.2 測(cè)試數(shù)據(jù)來(lái)源介紹42-43
• 5.3 串行測(cè)試結(jié)果與分析43-45
• 5.4 并行測(cè)試結(jié)果與分析45-49
• 5.4.1 并行最短路徑算法45-46
• 5.4.2 并行奇偶排序算法46-47
• 5.4.3 并行2層樹(shù)構(gòu)造算法47-49
• 5.5 本章小結(jié)49-51
• 結(jié)論51-53
• 參考文獻(xiàn)53-57
• 攻讀碩士學(xué)位期間發(fā)表的論文及其它成果57-59
• 致謝59

【參考文獻(xiàn)】

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

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

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

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

，

本文編號(hào)：1028358