【摘要】： 計算機圖形處理器(Graphics Processing Unit,GPU)的高速發(fā)展,不但促進(jìn)了圖像處理、虛擬現(xiàn)實、計算機仿真等應(yīng)用領(lǐng)域的快速發(fā)展,同時也為人們利用GPU進(jìn)行圖形處理以外的通用計算提供了良好的運行平臺�；贕PU的圖形處理及其通用計算成為圖形學(xué)及高性能計算領(lǐng)域的熱點研究課題�；贕PU的高性能并行算法研究是該課題的重要內(nèi)容之一。本文以探索GPU大規(guī)模并行通用計算的運用模式為目標(biāo),從傳統(tǒng)問題入手,選擇典型算法進(jìn)行研究,主要研究了數(shù)值類算法中的非計算密集型算法、數(shù)據(jù)密集類算法和元啟發(fā)式優(yōu)化算法這三類算法在GPU上的并行化。數(shù)值類算法中的非計算密集型算法存在內(nèi)存墻問題,而在基于GPU的并行化過程中,該瓶頸尤為突出。本文以稀疏矩陣向量乘算法為代表,研究基于GPU并行化方法以及性能優(yōu)化策略。數(shù)據(jù)密集類算法由于其特有的數(shù)據(jù)可分割性,因而比較適于GPU并行計算。本文以頻繁模式挖掘算法和最近鄰搜索算法為代表,研究了此類算法的GPU并行化方法以及性能優(yōu)化策略;針對最近鄰搜索問題,結(jié)合KD-Tree空間劃分與ABT方法,提出了適于歐幾里德距離的點剪枝策略。元啟發(fā)式優(yōu)化算法是求解大規(guī)模優(yōu)化問題的高效方法之一,其解空間搜索過程具有天然的并行性。本文以蟻群算法為代表,研究了蟻群算法及其若干改進(jìn)算法在GPU上的并行化方法;針對螞蟻個體智能性不足的問題,提出了帶有展望策略的蟻群優(yōu)化算法;針對蟻群參數(shù)敏感問題,研究了多蟻群在GPU上同時進(jìn)化方法,提出了適于GPU的粗/細(xì)粒度結(jié)合的多蟻群算法;針對異構(gòu)多蟻群的信息交流問題,提出了一種新的基于共享信息素矩陣的交流策略。大量的標(biāo)準(zhǔn)測試表明,上述算法可以達(dá)到幾倍甚至上百倍的加速比;與已有的同類基于GPU的并行算法相比,上述算法具有更高的實際浮點性能和存儲器帶寬。CPU+GPU的異構(gòu)多核架構(gòu)是目前GPU大規(guī)模并行通用計算的運用模式,探討傳統(tǒng)算法的GPU并行化方法,使之更適用于異構(gòu)多核架構(gòu)下并行計算,能夠為基于GPU的高性能計算的普及提供理論和方法。
【圖文】：

構(gòu)和并行層次為主線討論 GPU 通用計算與 CPU 指令級及多核并行、超級計的多處理器級并行和集群分布式并行的區(qū)別。2.1 GPU 體系架構(gòu)GPU 體系架構(gòu)在不斷的發(fā)展，本節(jié)以最新的 NVIDIA Tesla GT200 體系架代表對 GPU 的并行層次進(jìn)行分析。Tesla GT200 由兩部分組成，分別是可伸處理器陣列(Scalable Streaming Processor Array，SPA)和存儲器系統(tǒng)，它們由片上互聯(lián)網(wǎng)絡(luò)連接。如圖 1.1 所示，可伸縮流處理器陣列由若干個線程處理(Thread Processing Cluster，TPC)構(gòu)成，每個 TPC 包含 2～3 個流多處理treaming Multiprocessor，SM)，每個流多處理器中包含 8 個流處理器(Streamocessor，SP)。流處理器有獨立的寄存器和指令指針，但缺少取指和調(diào)度單流多處理器才擁有完整前端，，包括取值、譯碼、發(fā)射和執(zhí)行單元等。從結(jié)構(gòu)，每個流多處理器相當(dāng)于一個 8 路單指令流多數(shù)據(jù)流(Single Instruction Mulata，SIMD)處理器，不同的是，GPU 實現(xiàn)了自動向量機化，NVIDIA 將之命單指令流多線程(Single Instruction Multiple Thread，SIMT)[5]。

第 1 章 緒 論關(guān) GPU 架構(gòu)的細(xì)節(jié)見文獻(xiàn)[4，5]。與多核 CPU 的區(qū)別統(tǒng) CPU 的并行層次只有指令級并行，然而通用計算中可并行過超標(biāo)量、深度流水、長指令字等手段增加指令級并行不能取U 性能提升主要依靠提高處理器的工作頻率，先進(jìn)的分支預(yù)測緩存增加命中率這三種方式。然而，制造工藝的提高是有限度工作頻率的增長都因為量子效應(yīng)等原因而趨緩，通過提高處理 CPU 的性能遇到了前所未有的困境。INTEL、AMD 等廠商轉(zhuǎn)而在單塊芯片內(nèi)集成更多的處理器核心，使 CPU 向多核的方向了雙核 CPU 產(chǎn)品，繼而又有 3 核以及 4 核產(chǎn)品面市，圖 1.2 給出PU 的架構(gòu)示意圖。
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2010
【分類號】：TP338.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前8條

1 吳春明;陳治;姜明;;蟻群算法中系統(tǒng)初始化及系統(tǒng)參數(shù)的研究[J];電子學(xué)報;2006年08期

2 黃國銳,曹先彬,王煦法;基于信息素擴散的蟻群算法[J];電子學(xué)報;2004年05期

3 吳斌,史忠植;一種基于蟻群算法的TSP問題分段求解算法[J];計算機學(xué)報;2001年12期

4 陳],沈潔,秦玲,陳宏建;基于分布均勻度的自適應(yīng)蟻群算法[J];軟件學(xué)報;2003年08期

5 曹鋒;周傲英;;基于圖形處理器的數(shù)據(jù)流快速聚類[J];軟件學(xué)報;2007年02期

6 吳恩華;圖形處理器用于通用計算的技術(shù)、現(xiàn)狀及其挑戰(zhàn)[J];軟件學(xué)報;2004年10期

7 朱慶保,楊志軍;基于變異和動態(tài)信息素更新的蟻群優(yōu)化算法[J];軟件學(xué)報;2004年02期

8 孫力娟,王良俊,王汝傳;改進(jìn)的蟻群算法及其在TSP中的應(yīng)用研究[J];通信學(xué)報;2004年10期

本文編號：2599559