基于GPU的加鎖并行化非結構網格生成方法研究

蔡云龍，肖素梅，齊龍

西南科技大學制造科學與工程學院，四川綿陽 621010

基于GPU的加鎖并行化非結構網格生成方法研究

蔡云龍，肖素梅，齊龍

西南科技大學制造科學與工程學院，四川綿陽 621010

非結構網格的生成在時間和內存上有一定的缺陷，這里提出了一種新的方法，命名為GPU-PDMG，是基于CUDA架構的GPU并行非結構網格生成技術。該技術結合了GPU的高速并行計算能力與Delaunay三角化的優點，在英偉達GPU模塊下采用CUDA程序模型，開發出了加鎖并行區劃分技術，通過對NACA0012翼型、多段翼型等算例進行測試，分析此方法的加速比和效率，對其計算性能展開評估。實驗結果表明，GPU-PDMG優于現存在的CPU算法的速度，在保證網格質量的同時，提高了效率。

非結構網格；并行域；加鎖；圖形處理單元（GPU）；加速比

為了提高飛行器的氣動性能，網格生成可以說是至關重要的一步，需要優質的網格來準確捕捉復雜的物理現象[1]。計算網格按網格點之間的鄰接關系可分為結構網格、非結構網格和混合網格等。上述網格均已成功地應用于實際外形的計算中，并取得較大的成功，各有優點，但也各有不足。

非結構網格對描述和離散復雜幾何外形有良好的通用性，但是由于其數據的隨機性[2]，導致需要大量的存儲空間和計算時間。現如今擁有大型計算能力的計算系統解決了具有數以千萬節點網格的問題。然而，在單一機器上生成如此大規模、高質量的網格，還是給CPU帶來了時間和內存需求上的挑戰[3]。比如說，即使在目前工藝水平所能提供的浮動運算速度最快、容量最大的超級計算機上進行計算一個三維非定常問題的數值模擬可能也要花費較長的時間，數值模擬精度的提高勢必要求有更大規模的網格量網格的細化，必然要求更大的儲存量、計算量和更多的迭代步數，這都將使計算時間增加、效率降低。所以，一方面需要高速度、大容量的計算機，另一方面要開發并行軟件程序，以實現大規模高效并行計算。

加鎖并行的網格生成技術研究正是在這一背景下展開的。圖形處理單元（簡稱GPU）由于自身強大的并行計算能力，被應用于各種算例的數值計算中。采用基于GPU的CUDA[4]程序模型擁有健全的數值計算能力，比現如今存在的CPU數值算法都要優越[5]。

因此本文提出一種基于GPU的加鎖并行化非結構網格生成技術[6]，用于解決生成大規模網格的CPU內存和時間上的瓶頸。

1 并行方案設計

為對某些復雜工程進行更精細的模擬和分析，往往要生成包含多達幾千萬甚至上億單元的體網格。為解決由此帶來的內存和時間性能瓶頸，國外十幾年前開始關注并行網格生成算法的研究，目前國內的浙江大學和南京航空航天大學在這一領域取得了一定的進展。南航采取的陣面推進方法[7]實現網格的并行生成，而浙大方面利用Delaunay三角剖分法[8]。雖然方法不同，但兩者都是通過多CPU的并行實現的。

基于上述已經探究的并行方案，將采取在GPU上實現網格劃分功能，結合GPU高速性能的優點，來達到網格加速生成的目的，得出方案如下：

首先，在CPU端上初始化算法的基本參數；再者，從CPU端上讀取輸入文件，即劃分區域的離散化文件；隨后，在CPU端生成背景網格文件，將其存入內存中；最后，將背景網格數據傳入GPU端的顯存。數據導入工作結束后，就可以正式在GPU上進行非結構網格的劃分工作了。利用主機端控制著算法的迭代過程，而迭代中的每個步驟都在設備端上執行。主機端通過循環變量控制著循環體中的各個步驟，都由CUDA內核函數[9]來實現。通過這種方式，就可達到在非結構網格劃分算法的每一次迭代中能并行地實現多區域自動插點的目的。當主機端控制的循環結束后，設備端上的運算告一段落，算法迭代產生的網格數據被傳回CPU中。

這種方案減少了CPU與GPU二者之間的通信，只有讀取輸入文件和生成待剖分區域的背景網格在主機端完成，剩余的工作交給GPU來執行。這種方案加速了程序的運行效率，解決了基于GPU的非結構網格生成技術改造的關鍵問題。因此，本文采取該方案作為并行分區的研究方向。

2 基于CUDA程序的GPU算法框架

與傳統的非結構網格并行生成（簡稱為CPU-PDMG）方法相比，本文提出的基于GPU的加鎖并行化非結構網格生成方法（簡稱為GPU-PDMG），不用在多個CPU上分別執行序列化網格生成算法[10]生成子網格，而是將劃分網格的工作交給GPU來做，利用其自身的特點來達到并行化的目的。

基于GPU的加鎖并行化非結構網格生成方法的整體框架如圖1所示。

圖1 GPU-PDMG基本框架

3 GPU-PDMG框架具體流程設計

3.1 搜索背景網格中滿足條件的狹長單元

將傳入設備端的背景網格數據，以三角單元elem的形式分配給每個GPU線程，并計算出在GPU中對應的線程位置tx，用線程塊blockId和線程threadId進行表示，對應的公式如下：

在每個線程tx上同時進行三角單元狀態的搜索，找個滿足條件的三角單元，其狀態設為活躍，將這些三角單元的編號存入狹長單元Ugly。然后，采用分步歸約的方法，獲得最狹長的單元ugly，該單元要滿足條件：

elem[tid].R為單元外接圓的半徑，elem[tid].r為單元內切圓的半徑。

3.2 獲得每次迭代的并行域

初始化時，所有單元的鎖初始化為0（即沒有上鎖狀態），然后依據最狹長單元得到待插入新節點的位置坐標(x，y)，利用空外接圓性質，當滿足待插入點到單元外接圓圓心(xv，yv)的距離小于該單元外接圓半徑時，單元就被存入鎖域中。

判斷鎖域中單元的鎖是否為0：如果鎖域中單元鎖全部為0，則將單元鎖修改為1（即上鎖狀態）；如果鎖域中單元鎖不全部為0，則放棄加鎖，將該狹長單元的鎖修改為2。單元鎖全部為1的鎖域就是一個并行區，然后將結果存入并行域中。

圖2 連續線程的歸約

3.3 對當前并行域執行逐步插點操作

由上一步得到的插入點坐標位置，便可找到包含該點的單元，隨后將插入點與該單元的三個頂點連接起來，這樣就增加兩個新單元和三條新邊，對新增加的單元和邊進行編號。最后，新單元進行循環操作。

3.4 對并行域內進行邊交換操作

首先在搜索前將邊的交換狀態初始化為0，接著對并行區域內的每條邊進行搜索，從第一條邊開始，在此利用Delaunay法則進行判斷，共邊三角形單元是否需要交換對角線。如果符合條件，則邊的交換狀態為1，執行邊交換操作；反之，進入下一次迭代，直至并行域內所有的邊都被搜索過。

4 核心技術與算法設計

4.1 搜索最狹長單元

首先要獲得背景網格中的狹長單元集，其次要計算出這些狹長單元的外接圓半徑R，內切圓半徑r，最后通過比較函數得到狹長單元集中，其外接圓半徑與內切圓半徑比值最大的一個。具體見以下幾步：

步驟1對單元的狀態進行分類，可分為可接受單元和不可接受單元。不可接受的單元又可以分為活躍的（Active）和等待的（Waiting）。活躍狀態的單元是該單元位于剖分區域邊界上或鄰單元至少有一個是可接受的，等待狀態的單元是該單元的鄰單元都是不可接受的。將處于活躍狀態的單元存入狹長單元集中。

步驟2計算出外接圓半徑R和內切圓半徑r，采用向量方式求解，在二維情況下，令A(xA，yA)，B(xB，yB)，C(xC，yC)。首先可以得到AB邊的中點坐標AB(xAB，yAB)和BC邊的中點坐標BC(xBC，yBC)，令：

當Den＞0時，則可得到外接圓的圓心坐標：

令三條邊分別為sA，sB，sC周長為C=sA+sB+sC，則內切圓的半徑r=Det/C。

步驟3尋找狹長單元集中比值R/r最大的狹長單元。

為了減少比較大小的操作次數，采用排序法，將狹長單元集中所有的元素從大到小排序，把結果存入數組中。隨著網格數量的增加，排序耗時也線性增加，不利于大規模網格的生成。為了解決排序耗時的問題，采取并行歸約的方法。把歸約抽象為一般形式：對一個輸入數組執行某種計算，然后產生一個更小的結果數組，如圖2所示。

在GPU中有大量的線程可以使用，因此以并行的方式來執行歸約運算，這樣所花的時間將與數組長度的對數成正比。故此，狹長單元集中元素的排序時間大幅度縮減。

4.2 加鎖機制

非結構網格的并行生成，首要的就是待剖分區域的劃分。而本文的目的是實現剖分區域的自動劃分，將每個剖分動作交付給一個線程去執行，達到GPU并行加速的目的。目前常用的做法是人為進行分塊，然后將每塊交給一個CPU核來處理，最后再將各個子區域的網格進行合并。但這種方法不適用在GPU上實現大規模的并行，且目前還沒有很好的手段來解決公共邊界的問題。針對上述的問題，本文采取加鎖機制，將各個子區域之間的耦合關系切斷，這就可避開公共邊界的問題，大大減小了算法的復雜度，將并行效率得到提升。

步驟1初始化單元鎖，在實際編程中，在單元結構體中設定一個全局變量lock：

當lock為0時，單元未被鎖上，lock為1時表示該單元被鎖上，lock為2時，表示此時的狹長單元所關聯的區域內，有元素處于上鎖狀態，這時放棄為子區域加鎖，將該鎖的狀態記為2。

步驟2人為給單元鎖賦值，假如令335號單元的鎖為2，得到劃分后的效果圖如圖3所示。

圖3335 號單元加鎖的效果圖

從圖3（a）中可以看出，給單元加鎖的機制已經實現了，但不是理想中的效果，加上鎖的單元本應該不能被修改，圖中的335號單元被修改過，將這種現象稱為“單元漂移”。圖3（b）是正確的335號單元加鎖效果圖。

4.3 并行區域的劃分技術

非結構網格的并行生成，首先是剖分區域的分塊問題，分塊的思想在加鎖機制中已經涉及到。文中借鑒多塊分區的思想，將每個子區域在GPU上執行劃分工作。在程序結構設計方面：程序采用雙層循環設計，內層循環迭代一次就可找到當前所有的并行區域，外層循環控制著并行區域的數量，直至沒有并行區域。

圖4即NACA0012并行區域劃分效果圖，（a）圖表示的是整個剖分區域，（b）圖表示的是外層循環迭代一次產生的所有并行區。

圖4 NACA0012翼型并行區劃分

從圖4中可以發現三點現象：

（1）NACA0012翼型第一次循環產生9個并行區；

（2）每個并行區大小不同，形狀各異；

（3）產生并行區后圖與待剖分區域圖相比，有空白區域。

5 研究結果與分析

本實驗是基于這樣的平臺開展的：CPU為Intel?CoreTMCPU i3-2120，主頻為3.30 GHz，安裝內存為8.00 GB，系統類型為Win7 64位操作系統，顯卡采用NVIDIA GeForce GTX 560 SE，該顯卡擁有288個CUDA Cores，其計算能力為2.1，GPU的驅動版本為CUDA 4.2。通過該平臺，對NACA0012與多段翼型進行了兩組實例的網格劃分實驗，得出以下結論：

隨著迭代次數的增加，每次迭代時產生并行區的數量也在增加；當并行區的數量達到峰值時，迭代次數的值增加，并行區的數量反而降低，直至并行區的數量為零，網格劃分結束。二者的關系呈類拋物線變化。

將對NACA0012翼型與多段翼型的網格劃分結果進行分析，圖5與圖6是串行非結構網格生成方法生成的網格和GPU下并行方法生成的網格之間的對比。從這兩組對比圖可以看出，串行的非結構網格生成技術產生的網格單元排列有序，而基于GPU并行的網格單元看上去有些雜亂無章。產生這一現象的原因是，串行非結構網格生成技術采用的是逐步插點的思想，程序每迭代一次只插入一個點，然后交換邊，接著網格優化；而基于GPU的并行技術采取的是隨機分配并行區，采用多線程并行分塊插點方法，所以產生的網格單元排列比較混亂。

圖5 NACA0012翼型網格圖

圖6 多段翼型網格圖

表1與表2給出了NACA0012翼型與多段翼型在兩種情況下網格生成時間以及加速比等對比數據。在并行算法的設計中，采用加鎖機制，避開公共邊界的問題，并行效率得到提升。時間消耗在狹長單元的搜索上，逐點插入與狹長單元判據使得整體效率被拉低。所以，在狹長單元搜索存在缺陷的情況下，比對數據，得到的加速比效果理想，達到了要求。在NACA0012翼型整體加速比在網格單元為6萬級別時約為3.6，多段翼型整體加速比在網格單元為5萬級別時約為2.3，可見加速效果明顯。

表1 NACA0012翼型在CPU和GPU下網格生成情況

表2 多段翼型在CPU和GPU下網格生成情況

6 結束語

本文提出了一種基于GPU的加鎖并行化非結構網格生成技術，建立了GPU-PDMG框架模型，針對其算法與核心技術進行了設計，應用于NACA0012翼型與多段翼型的二維網格劃分，并對網格生成效率產生了積極影響，得出以下結論：

（1）選取逐點插入算法[11]實現了并行化改造并針對目前分布式并行技術的不足，提出了并行域劃分加鎖機制，實現了計算域網格的自動劃分。

（2）對比串行CPU非結構網格生成，并行GPU加速明顯，且生成網格效果理想，驗證了這種基于GPU的并行非結構網格生成技術的加速效果。

（3）受制于實驗條件與技術尚不成熟，存在一些不足，例如測試算例處于一般規模的二維網格的實驗驗證，網格生成算法效率過低，在以后的工作中會加入對三維復雜網格的驗證并改進設計技術。

[1]Yasushi I，Alan M S，Anil K E.Parallel unstructured mesh generation by an advancing front method[J].Mathematics and Computers in Simulation，2007，75（5/6）：200-209.

[2]Baker T J.Mesh generation：art or science?[J].Progress in Aerospace Sciences，2005，41：29-63.

[3]Frey P J，Loic M.Fast adaptive quadtree mesh generation[C]//Proceedings of the7th International Meshing Round table，1998.

[4]NVIDIA.CUDA C programming guide[S].2010.

[5]Qi Meng，Cao Thanh-Tung，Tan Tiow-Seng.Computing 2D constrained delaunay triangulation using graphics hardware[R].School of Computing，National University of Singapore，Singapore，2011.

[6]齊龍，肖素梅，蔡云龍，等.基于GPU的并行非結構網格生成技術研究[J].機械設計與制造，2013，2（2）：184-186.

[7]Pirzadeh S.Structured background grids for generation of unstructured grids by advancing front method[J].AIAA J，1993，31（2）.

[8]Kallmann M，Bieri H，Thalmann D.Fully dynamic constrained delaunay triangulations[M]//Geometric Modelling for Scientific Visualization.New York：Springer-Verlag，2003.

[9]Garland M，GrandS L，Nickolls J，et al.Parallel graph component experiences with CUDA[J].Micro，IEEE，2008，28（4）：13-27.

[10]Rebay S.Efficient unstructured mesh generation by means of delaunay triangulation and Bowyer-Watson algorithm[J]. Journal of Computational Physics，1993，106（1）：106-125.

[11]朱培燁.Delaunay非結構網格生成之布點技術[J].航空計算技術，1999，29（3）：21-25.

CAI Yunlong,XIAO Sumei,QI Long

School of Manufacturing Science and Engineering,Southwest University of Science and Technology,Mianyang,Sichuan 621010,China

Defects of consuming time and memory consist in unstructured mesh generation.This paper proposes a novel approach,terming GPU-PDMG,which is GPU parallel unstructured mesh generation based on the framework of CUDA. The technology combines the high-speed parallel GPU and advantages of Delaunay triangulation.It develops a method of locking parallel area dividing,using the CUDA programming model on nVidia GPUs.By analyzing the tested examples’speedup rate and efficiency,it has evaluated their computing performance.This result is identified in NACA0012 and multi-element airfoil experiment with both the analysis of speedup rate and efficiency and GPU-PDMG is better than any existing GPU algorithms.

unstructured mesh;parallel area;locking;Graphic Processing Unit（GPU）;speed-up ratio

A

TP311；TH16

10.3778/j.issn.1002-8331.1308-0387

CAI Yunlong,XIAO Sumei,QI Long.Locking paralleled GPU-based method research for unstructured mesh generation.Computer Engineering and Applications,2014,50（6）：56-60.

國家重點基礎研究發展規劃（973）（No.2009CB723805）。

蔡云龍（1988—），男，碩士研究生，主要研究領域為網格生產算法研究，計算流體力學；肖素梅（1966—），女，博士，教授，主要研究領域為工業工程，動力系統仿真，計算流體力學等；齊龍（1986—），男，碩士研究生，主要研究領域為網格生產算法。E-mail：cylinder1220@gmail.com

2013-08-30

2013-10-15

1002-8331（2014）06-0056-05

CNKI網絡優先出版：2013-11-25，http://www.cnki.net/kcms/detail/11.2127.TP.20131125.1535.011.html