基於圖形處理器的球面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