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