基于GPU的并行Voronoi圖柵格生成算法

具體步驟如下：(這里假設柵格的規模為M×N)：

Step1：根據柵格圖像的規模，確定GPU端線(xiàn)程塊和線(xiàn)程的分配方式和分配數量，初始化GPU端的參數。

Step2：程序調用GPU端內核函數，同時(shí)將待處理柵格圖像數據傳入GPU中。數據主要是圖像的柵格距離，一般是二維數組，0表示空白柵格，其他各生長(cháng)目標可由1，2等不同的數字定義。

Step3：GPU分配M×N個(gè)thread對柵格進(jìn)行處理，當M×N大于所有的thread的總數時(shí)，可以將M×N個(gè)柵格分塊處理，即將其分成A行×B列×C塊，其中A×B小于thread的總數。對于分成了C塊的柵格來(lái)說(shuō)，每個(gè)線(xiàn)程只需要處理C個(gè)柵格。

Step4：當生長(cháng)目標數目不多時(shí)，每一個(gè)線(xiàn)程計算其對應的柵格到所有的生長(cháng)目標點(diǎn)的距離，取距離最小的生長(cháng)目標，為此線(xiàn)程對應的空白柵格的歸屬，轉Step6。當生長(cháng)目標過(guò)多時(shí)，則轉Step5。

Step5：當生長(cháng)目標較多時(shí)，為了減少遍歷生長(cháng)目標的時(shí)間，通過(guò)借鑒王新生的算法，不計算柵格點(diǎn)到每一個(gè)生長(cháng)目標的距離，通過(guò)對空白柵格不斷的進(jìn)行鄰域擴張，直到遇到目標生長(cháng)點(diǎn)的方法確定此柵格的歸屬。

Step6將生成后的數據返回CPU端，CPU端完成柵格圖像的顯示與后處理。

3 實(shí)驗與總結

在CPU參數為IntelXeonCPUE5-2609，2.4GHz，2處理器8核心，GPU參數為T(mén)eslaC2075，448CUDA核心，顯存 5.25GB的試驗平臺下，做了不同方法在不同柵格規模下生成Voronoi圖的對比試驗，試驗中生長(cháng)目標的個(gè)數定義為100個(gè)。由于不同的方法都采用了相同的距離定義，因此各種方法的Voronoi圖生成結果都是相同的，即他們之間的生成精度是相同的，所以這里重點(diǎn)比較了不同方法的生成耗時(shí)。表1列出了不同方法生成Voronoi圖的用時(shí)，圖2為表1的折線(xiàn)圖，從圖2中可以明顯看出，當柵格數量較少時(shí)，GPU并行技術(shù)的使用并不能提升生成速度，但是當柵格點(diǎn)數量增加時(shí)，逐點(diǎn)法和距離變換法用時(shí)明顯增加，但GPU并行算法用時(shí)幾乎不變。

4 結語(yǔ)

通過(guò)實(shí)驗結果可以看出，采用GPU對Voronoi圖的生成進(jìn)行并行加速，能夠很好的提高生成速度。其生成Voronoi圖所需時(shí)間與只與生長(cháng)目標的數量有關(guān)，而與柵格規模沒(méi)有關(guān)系，當生長(cháng)目標數量為n時(shí)，其時(shí)間復雜度近似于O(n)，為線(xiàn)性的生成時(shí)間。相對于前面的幾種CPU下串行算法，尤其是在柵格規模過(guò)大的情況下，能夠很好的提高Voronoi圖的生成速度。