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

許衛(wèi)明

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

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

許衛(wèi)明

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

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

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

0 引言

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

1 VAS2D解算器算法簡(jiǎn)介

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

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

圖1 非結(jié)構(gòu)自適應(yīng)四邊形網(wǎng)絡(luò)

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

網(wǎng)格的截?cái)嗾`差決定了網(wǎng)格是否被加密，在VAS2D解算器中，采用二階導(dǎo)數(shù)對(duì)網(wǎng)格截?cái)嗾`差進(jìn)行估算，公式如下所示：

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

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

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

1．2 控制方程和解算器

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

其中U、F、G分別為

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

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

2 VAS2D解算器算法映射

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

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

2．1 流場(chǎng)解算

在GPU上進(jìn)行流場(chǎng)的計(jì)算相對(duì)容易，1．1中對(duì)網(wǎng)格的自適應(yīng)中網(wǎng)格和邊采用的是Cell－Face的數(shù)據(jù)結(jié)構(gòu)，計(jì)算時(shí)只需分別對(duì)網(wǎng)格和邊進(jìn)行循環(huán)計(jì)算即可［4］?？梢詫⒘鲌?chǎng)的計(jì)算分為3部分：梯度計(jì)算、初始變量重構(gòu)、通量計(jì)算。

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

2．2 自適應(yīng)處理

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

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

圖3 網(wǎng)絡(luò)自適應(yīng)步驟

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

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

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

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

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

3 結(jié)語

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

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

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

［3］李立，白文，梁益華．基于伴隨方程方法的非結(jié)構(gòu)網(wǎng)格自適應(yīng)技術(shù)及應(yīng)用［J］．空氣動(dòng)力學(xué)學(xué)報(bào)，2011（3）：309－316．

［4］盧風(fēng)順，宋君強(qiáng)，銀?？担龋瓹PU／GPU協(xié)同并行計(jì)算研究綜述［J］．計(jì)算機(jī)科學(xué)，2011（3）：5－9．

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

［6］何冰，封衛(wèi)兵，張武，等．基于非結(jié)構(gòu)網(wǎng)格的Gas－Kinetic方法［J］．計(jì)算機(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－），男（漢），安徽懷寧，講師主要研究計(jì)算機(jī)網(wǎng)絡(luò)、軟件技術(shù)。