基于網格自適應加密技術的GPU 高效運行實現研究

許衛明

（馬鞍山師范高等專科學校，安徽馬鞍山243041）

基于網格自適應加密技術的GPU 高效運行實現研究

許衛明

（馬鞍山師范高等專科學校，安徽馬鞍山243041）

針對傳統解算器未能實現GPU上運行網格自適應加密過程，造成GPU與CPU之間繁瑣的數據交換的問題，本文發展優化了一種GPU加速的基于非結構自適應加密網格的解算器VA2DG。利用加密網格表的方式實現網格自適應加密過程在GPU上高速運行，并通過原子操作并行生成網格加密表，對廢棄的網格及時回收，節約存儲空間，加快運行速度。

GPU；自適應加密；網格；解算器

0 引言

GPU做運算起始于計算機圖形學語言編程的實現，早期由于架構上的設計，在科學計算領域只做一些粒子算法，隨著GPU計算的優勢被發覺，開始將GPU設計成流式結構，使之更適合通用計算，不再依賴計算機圖形學，使得程序設計更加容易。在各種學科特別是流體力學方面的數值方法，通過GPU運算實現了加速［1］。基于網格的CFD方法在GPU上實現時，運算性能跟網格的類型有很大關系，網格自適應加密可以得到動態網格，有利于提升計算精度和速度，但是傳統的自適應加密只能對截斷誤差較大的網格進行加密，同時GPU與CPU之間交流頻繁，消耗的計算機資源較多，嚴重影響程序的性能。因此發展一種能在GPU上高效運行的自適應加密方法對于加速GPU高效運行是非常必要的。

1 VAS2D解算器算法簡介

1．1 網格與自適應加密原理

VAS2D解算器采用的是非結構自適應四邊形網格，網格結構如圖1所示，網格自適應通過Cell－Face網格結構將網格和邊聯系起來，網格和鄰邊發生通信，與相鄰網格不直接通信［2］。每一個網格會把自己的鄰邊儲存在表Neighbor edge list中，而每條邊將其相鄰的網格存放在Neighbor cell list之中，這種基于Cell－Face數據結構的通信方式適用于并行計算，易擴展到多維度的計算，計算時對網格和邊做循環即可。

圖1 非結構自適應四邊形網絡

在自適應加密的各種方法中，基于網格的自適應加密技術使用的網格數量最少，在加密的過程中，以一個網格為例，將原網格命名為Father，將原邊命名為Mother，加密運行時，該網格分成4個小網格，小網格成為son，加密的同時，網格的4條邊也會各自分成兩條子邊，稱這些子邊為daughter，加密完成后，將網格的編號編入Father list之中［2］，將網格的邊編入Mother list中，加密后網格和邊所帶的信息不變，只是被稀疏。

網格的截斷誤差決定了網格是否被加密，在VAS2D解算器中，采用二階導數對網格截斷誤差進行估算，公式如下所示：

式中：V為原始變量；αf為常數通常取0．03；i，j為編號；rji為網格之間的向量；ρc為網格的平均密度；為網格的梯度為網格梯度在網格向量的投影。

計算出截斷誤差之后，取4條邊的最大值，判斷自適應的依據如下，其中ετ是判斷加密的依據，一般取0．08，εο為網格稀疏的閾值，一般取0．05。

Refine，ν＞ετ；Coarsen，ν＜εο

1．2 控制方程和解算器

在可壓縮流動計算的應用中，根據Euler方程［3］，解算器的控制方程為

其中U、F、G分別為

利用近似原理達到時空二階精度，網格上的變化有網格的四條邊的通量決定。

數值通量為Fi，k，其值的大小由邊的左右狀態得出。

2 VAS2D解算器算法映射

在計算機進行計算時應該盡量避免GPU和CPU之間的數據傳輸，此次設計旨在將解算器的計算全部放在GPU上，從而達到提升計算速度的目的，計算的流程如圖2所示，計算之前先分配出一定的空間預留數據，之后對網格信息進行讀取，完成數據的初始化，并進行自適應的初始化，將數據傳輸給GPU，執行解算器中的kernel函數的計算，數據處理完成后再將數據傳輸回去進行輸出。

圖2 GPU程序執行步驟

2．1 流場解算

在GPU上進行流場的計算相對容易，1．1中對網格的自適應中網格和邊采用的是Cell－Face的數據結構，計算時只需分別對網格和邊進行循環計算即可［4］。可以將流場的計算分為3部分：梯度計算、初始變量重構、通量計算。

在計算梯度時，先完成網格邊的并行處理，對每條邊相鄰網格的初始變量的差值進行儲存，將所有值的計算完成后，利用最小二乘法來計算梯度。在初始變量重構的過程中，利用MINMOD限制器對網格的梯度進行限制，并對網格中心的原始變量進行推測，然后由中間向兩邊進行差值計算，求各個邊的形態，之后采用AUFS格式進行通量計算。

2．2 自適應處理

本次設計中的自適應處理分為網格標記和網格自適應，步驟結構框圖如圖3所示。在網格標記的過程中首先進行網格截斷誤差的估計，將加密的網格標記的為Refine，稀疏的網格標記為Coarsen，選擇網格鄰邊中最大作為網格的截斷誤差，之后按程序運行Father list得到父網格編號，并用加密依據進行判定，滿足加密條件標記的為Refine，不滿足的則標記為Coarsen。利用截斷誤差判定網格是否加密并不是唯一的方式，有時候還取決于網格的級別（level）限制，網格的level需在設定的范圍內，同時，若一個網格被加密或者稀疏，level和相鄰的網格的level值相差必須滿足≤1［5］的條件，正是因為網格標記的步驟對于所有網格各邊是單獨運算的，因此才容易在GPU上實現并行運算。

網絡的自適應在GPU上較難實現并行運算，傳統的算法證明了通過對表進行處理實現部分向量化可以實現網格的自適應，但傳統的算法并不能實現這一功能，主要在兩方面難以克服：實現向量化的表是通過串行操作的，程序處理起來難以實現，同時，廢舊的網絡不做任何處理使得內存的消耗越來越嚴重［6］。本文利用原子操作將表生成并行化，同時對不用的表進行回收，降低內存消耗，這樣克服了傳統算法的不足，實現的網格自適應在GPU上高速運行。

圖3 網絡自適應步驟

網格自適應過程分為稀疏被標記的父網格，回收廢棄的網格和邊，同時加密被標記的網格。在稀疏被標記的父網格過程中，將Coarsen的網格從Father list中選出放入Temp list中，之后將Father list壓縮，被選出來的進行稀疏，取出內部4條邊，對于子邊能去除的去除，去除的邊或網格標記為Null，之后更新物理量，如果去除4個網格，則將其父網格標記為Non，同理，去除邊的母邊從Mother list中去除，之后進行壓縮，然后進行廢棄網格和表的回收。回收的具體算法如下：

網格加密的過程最為復雜，包括以下3步：

1）增加子網格。將標記的Refine的網格導入臨時表Temp list中，在Temp list中的網格均被加密，形成父網絡，然后將其導入Father list，新形成的父網格形成新的子網格和邊。

2）分裂標記過的邊。對標記為Refine的需要分裂的進行分裂，分裂產生兩條子邊，被標記加入Mother list之中新產生的邊的信息由母邊計算得到。

3）完成子網絡的構建。由于重新產生了子邊，需要重新更新鄰居關系，當新的邊和網格的鄰居關系產生之后，就可以通過鄰邊的信息計算新產生的網格的信息。

3 結語

采用原子操作表生成并行化可以避免串行操作生成表的程序瓶頸，實現表的向量化，同時在運算中增加回收廢棄網格和邊的操作，降低了內存的消耗，使得網格自適應加密過程在GPU上高效、高速的運行。

［1］曹建，曾麗娟，陳建軍．面向粘性繞流計算的二維混合網格生成算法［J］．計算機工程，2013（10）：290－293．

［2］楊猛，劉金剛．一種穩定、高效且保持細節的粘性流模擬算法［J］．軟件學報，2011（12）：2994－3003．

［3］李立，白文，梁益華．基于伴隨方程方法的非結構網格自適應技術及應用［J］．空氣動力學學報，2011（3）：309－316．

［4］盧風順，宋君強，銀福康，等．CPU／GPU協同并行計算研究綜述［J］．計算機科學，2011（3）：5－9．

［5］劉瑩，菅立恒，梁莘燊，等．基于CUDA架構的GPU的并行數據挖掘技術研究［J］．科研信息化技術與應用，2010（4）：38－51．

［6］何冰，封衛兵，張武，等．基于非結構網格的Gas－Kinetic方法［J］．計算機輔助工程，2009（1）：14－17．

The Research and Implementation of GPU Based on Grid Adaptive Encryption Technology

XU Wei－ming
（Maanshan TeacherCollege，Maanshan Anhui 243041，China）

Aiming at the problem that the traditional solution can not implement the adaptive encryption of GPU，which results in the complex data exchange between CPU and GPU，this paper develops a kind of speed GPU based on unstructured adaptive encryption mesh VA2DG．It is to realize that the grid adaptive encryption process can be fast running on CPU by using encryption grid table，and the grid encryption table can be generated by atomic operations．The waste is collected in time to save the storage space and increase the running speed．

GPU；adaptive encryption；grid；solution

TP301

A

1009－8984（2016）02－0116－03

10．3969／j．issn．1009－8984．2016．02．029

2015－11－17

許衛明（1981－），男（漢），安徽懷寧，講師主要研究計算機網絡、軟件技術。