基於圖形處理器的球面Voronoi圖生成演算法優化論文
摘要:基於四元三角格網(QTM)之間距離計算與比較的球面Voronoi圖生成演算法相對於擴張演算法具有較高的精度,但由於需要計算並比較每個格網到所有種子點的距離,致使演算法效率較低。針對這一問題,利用圖形處理器(GPU)平行計算對演算法進行實現,然後從GPU共享記憶體、常量記憶體、暫存器等三種記憶體的訪問方面進行優化,最後用C++語言和統一計算裝置架構(CUDA)開發了實驗系統,對優化前後演算法的效率進行對比。實驗結果表明,不同記憶體的合理使用能在很大程度上提高演算法的效率,且資料規模越大,所獲得的加速比越高。
關鍵詞:球面Voronoi圖;統一計算裝置架構;共享記憶體;常量記憶體;暫存器
英文摘要
Abstract:Spherical Voronoi diagram generating algorithm based on distance computation and comparison of Quaternary Triangular Mesh (QTM) has a higher precision relative to dilation algorithm. However, massive distance computation and comparison lead to low efficiency. To improve efficiency, Graphic Processing Unit (GPU) parallel computation was used to implement the algorithm. Then, the algorithm was optimized with respect to the access to GPU shared memory, constant memory and register. At last, an experimental system was developed by using C++ and Compute Unified Device Architecture (CUDA ) to compare the efficiency before and after the optimization. The experimental results show that efficiency can be improved to a great extent by using different GPU memories reasonably. In addition, a higher speedup ratio can be acquired when the data scale is larger.
英文關鍵詞
Key words:spherical Voronoi diagram; Compute Unified Device Architecture (CUDA); shared memory; constant memory; register
0 引言
近年來,圖形處理器(Graphic Processing Unit,GPU)技術快速發展,其浮點運算能力和記憶體頻寬已遠遠超過中央處理器(Central Processing Unit,CPU)[6]。NVIDIA公司開發的統一計算裝置架構(Compute Unified Device Architecture,CUDA)為GPU增加了一個易用的程式設計介面[7],使得GPU平行計算在群體行為模擬[8]、三維資料並行視覺化[9]、地球表面測繪[10]等領域得到廣泛應用。
本文利用CUDA對基於距離計算與比較的球面V圖生成演算法進行實現,然後從GPU共享記憶體、常量記憶體、暫存器等三種記憶體的`訪問方面,對演算法進行優化,最後利用C++和CUDA開發了實驗系統,對優化前後演算法的效率進行對比。
1 基於QTM的球面Voronoi圖並行生成演算法
若將式(1)中的ω定義為一個QTM格網,Ω定義為球面上所有QTM格網的集合,距離函式d定義為球面大弧距離,則式(1)表示的即為基於QTM的球面V圖。
基於QTM格網之間距離計算與比較的球面V圖生成演算法[5],通過計算並比較每個格網到所有種子點的距離,來確定格網單元所屬的Voronoi區域,演算法具有計算密集性、指令一致性及相互獨立性的特點,本文采用GPU單指令多資料流(Single Instruction Multiple Date,SIMD)平行計算模型來執行這些運算,演算法實現的核函式(Kernel)偽碼如下(Kernel_1)。
2 演算法的優化
在CUDA架構中有多種記憶體可供使用,如全域性記憶體、區域性記憶體、共享記憶體、常量記憶體、暫存器等,每種記憶體的空間大小、作用範圍及訪問速度都各不相同。因此,在實現演算法時使用不同的記憶體、不同的訪問方式,將會對程式的效能產生巨大的影響。本文將從GPU記憶體訪問方面(包括共享記憶體、常量記憶體及暫存器等)對上述演算法進行優化。
2.1 共享記憶體優化
2.2 常量記憶體優化
GPU中的常量記憶體是隻讀記憶體。如果半個執行緒束(HalfWarp, 16個執行緒)中的每個執行緒都從常量記憶體的相同地址讀取資料,GPU只會產生一次讀取請求並在隨後將資料廣播到每個執行緒;同時,由於常量記憶體的內容是不會發生變化的,硬體會主動把這個常量資料快取在GPU上,在第一次從常量記憶體的某個地址上讀取後,當其他半執行緒束請求同一個地址時,將命中快取,同樣減少了額外的記憶體流量。因此,與從全域性記憶體中讀取資料相比,從常量記憶體中讀取相同的資料可以節約大量的記憶體頻寬[11]。
由於演算法中的種子點資料不會發生改變,且每個執行緒都從第1個種子點資料開始讀取,因此,可將種子點資料直接從CPU記憶體複製到GPU常量記憶體中,以消除全域性記憶體訪問對演算法效率的影響。與使用共享記憶體類似,在計算能力為1.1的裝置中,GPU常量記憶體的大小隻有64KB,當種子點資料較大時,需要分成多次將資料從CPU記憶體複製到GPU常量記憶體,並多次呼叫核函式進行計算。演算法實現的偽碼與Kernel_1類似,只是將種子點資料儲存在GPU常量記憶體中。
2.3 暫存器優化
為按順序進行編號,也可以將文中的Kernel-4直接改成Kernel-3!)。
3 實驗與分析
實現本文演算法所用的程式語言為C++和NVIDIA CUDA 6.5;硬體環境為Intel Core 2 Quad CPU Q8400 @2.66GHz,2.00GB記憶體,NVIDIA GeForce 9600 GT GPU,計算能力1.1。在該環境下,將基於距離計算與比較的球面V圖生成演算法及上述各優化演算法進行實現,並進行了對比分析。
4 結語
本文利用CUDA對基於距離計算與比較的球面V圖生成演算法進行實現,並從GPU共享記憶體、常量記憶體、暫存器等三種記憶體的訪問方面對演算法進行優化,通過實驗得出如下結論:
1)僅使用GPU全域性記憶體時,演算法的效率僅與CPU序列演算法相當;
2)GPU共享記憶體、常量記憶體、暫存器的合理使用,能夠大大提高演算法的效率;
3)在一定的資料規模下,隨著種子點數的增多,GPU加速比逐漸增大。
本文僅從GPU記憶體訪問的角度對基於距離計算與比較的球面V圖生成演算法進行了優化,下一步的工作是綜合考慮演算法指令、任務劃分、記憶體訪問等因素,對演算法進一步優化。
參考文獻:
[8]HE Y, YE C, LIU Z, et al. Parallel simulation and optimization of CUDAbased realtime huge crowd behavior[J]. Journal of Comput
-
多媒體教室管理制度【優秀】
現如今,制度的使用頻率呈上升趨勢,制度泛指以規則或運作模式,規範個體行動的一種社會結構。這些規則蘊含著社會的價值,其執行表彰著一個社會的秩序。擬定製度的注意事項有許多,你確定會寫嗎?下面是小編為大家收集的多媒體教室管理制度,僅供參考,歡迎大家閱讀。多媒體教...
-
多媒體工作計劃合集六篇
時間過得真快,總在不經意間流逝,我們的工作又將在忙碌中充實著,在喜悅中收穫著,此時此刻需要為接下來的工作做一個詳細的計劃了。什麼樣的計劃才是有效的呢?以下是小編為大家整理的多媒體工作計劃6篇,希望能夠幫助到大家。多媒體工作計劃篇1本學期,本人繼續擔任了學校...
-
病理學多媒體教學的實踐與思考的教育理論論文
論文關鍵詞:病理學;教學方法;多媒體教學論文摘要:多媒體作為一種新型的教學手段在病理學教學中得到應用,相對於較傳統的教學模式有很多優勢,對教學質量的提高和教改工作的推動起到了積極的作用,但在實際工作中也存在一些不足之處。就多媒體在病理學教學應用的若千...
-
多媒體工作計劃七篇
時光飛逝,時間在慢慢推演,很快就要開展新的工作了,是時候開始寫計劃了。那麼你真正懂得怎麼制定計劃嗎?下面是小編為大家收集的多媒體工作計劃7篇,僅供參考,歡迎大家閱讀。多媒體工作計劃篇1本學期,本人繼續擔任了學校多媒體教室的管理工作,多媒體教室管理工作計劃。經...
相關文章
- 試析中職圖形影象處理Photoshop課程中專案論文
- 葡萄牙語的歷史:Revolucionários apossam-se de Porto Alegre
- 電腦是惠普Pavilion dv4 Notebook Pc筆記本
- innovation是什麼意思 innovation釋義-短語-外教教學視訊
- 《No ordinary love》歌詞
- PowerPoint流程文字轉換成漂亮的圖形流程圖教程
- How to Interview for a Job—外企面試技巧
- 《What are you doing for vacation》課文學習教案
- 英語優秀作文推薦:My View on Major Ranking
- Avril Lavigne《Tomorrow》歌詞中英對照彈唱視訊