許衛(wèi)明

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

基于網(wǎng)格自適應加密技術的GPU 高效運行實現(xiàn)研究

許衛(wèi)明

（馬鞍山師范高等?？茖W校，安徽馬鞍山243041）

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

GPU；自適應加密；網(wǎng)格；解算器

0 引言

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

1 VAS2D解算器算法簡介

1．1 網(wǎng)格與自適應加密原理

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

圖1 非結構自適應四邊形網(wǎng)絡

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

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

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

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

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

1．2 控制方程和解算器

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

其中U、F、G分別為

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

數(shù)值通量為Fi，k，其值的大小由邊的左右狀態(tài)得出。

2 VAS2D解算器算法映射

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

圖2 GPU程序執(zhí)行步驟

2．1 流場解算

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

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

2．2 自適應處理

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

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

圖3 網(wǎng)絡自適應步驟

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

網(wǎng)格加密的過程最為復雜，包括以下3步：

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

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

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

3 結語

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

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

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

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

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

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

［6］何冰，封衛(wèi)兵，張武，等．基于非結構網(wǎng)格的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

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