常立博，杜慧敏，韓俊剛

(1.西安郵電大學(xué) 電子工程學(xué)院,陜西 西安 710121; 2.西安郵電大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安 710121)

?

基于CUDA的SMAC算法并行化

常立博1，杜慧敏1，韓俊剛2

(1.西安郵電大學(xué) 電子工程學(xué)院,陜西 西安 710121; 2.西安郵電大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安 710121)

改進(jìn)SMAC(Simplified Marker and Cell)算法，增強(qiáng)其對(duì)流體模擬的實(shí)時(shí)處理能力。采用點(diǎn)差分格式對(duì)求解壓力場(chǎng)和速度更新的偏微分方程進(jìn)行離散化；引入消除數(shù)據(jù)相關(guān)性的存儲(chǔ)算法以減少數(shù)據(jù)傳輸，并借助分層存儲(chǔ)機(jī)制提高訪存比，采用并行歸約增加線程并行度；在統(tǒng)一計(jì)算設(shè)備架構(gòu)平臺(tái)下，對(duì)離散化的SMAC算法進(jìn)行改進(jìn)、優(yōu)化及并行化實(shí)現(xiàn)。純粹計(jì)算及多次迭代模擬實(shí)驗(yàn)結(jié)果顯示，改進(jìn)算法提速明顯，可實(shí)現(xiàn)對(duì)一般場(chǎng)景的實(shí)時(shí)模擬。

計(jì)算流體力學(xué)；統(tǒng)一計(jì)算設(shè)備架構(gòu)；并行算法

流體流動(dòng)現(xiàn)象的模擬不僅是計(jì)算機(jī)動(dòng)畫、游戲、影視和飛行模擬等領(lǐng)域不可或缺的元素，也是科學(xué)計(jì)算可視化領(lǐng)域的研究熱點(diǎn)之一[1]。常用的流體模擬算法有基于Stable Fluids[2]和基于SMAC[3]兩類。Stable Fluids算法雖然可以較好地完成一般場(chǎng)景的模擬工作，但其本身存在嚴(yán)重的數(shù)值耗散，從而失去了模擬的物理真實(shí)感[1]。SMAC是MAC(Maker and Cell)方法的一種改進(jìn)，具有良好的數(shù)值特性、求解精度和計(jì)算效率，已廣泛應(yīng)用于計(jì)算機(jī)圖形學(xué)領(lǐng)域[4]。但基于SMAC的流體模擬算法存在復(fù)雜度較高、計(jì)算耗時(shí)過(guò)長(zhǎng)等問(wèn)題，無(wú)法用于實(shí)時(shí)性要求較高的場(chǎng)合。以提高計(jì)算密集型算法速度而發(fā)展起來(lái)的圖形處理器(Graphic Processing Unit, GPU)，為提高計(jì)算機(jī)動(dòng)畫實(shí)時(shí)模擬速度提供了新的解決方法，尤其是統(tǒng)一計(jì)算設(shè)備架構(gòu)(Compute Unified Device Architecture, CUDA)平臺(tái)的推出，進(jìn)一步發(fā)揮了GPU的數(shù)據(jù)級(jí)并行計(jì)算能力，其強(qiáng)大的并行計(jì)算能力和浮點(diǎn)運(yùn)算能力，以及可編程能力使得流體模擬加速成為可能。

文獻(xiàn)[5]利用CUDA提供的庫(kù)函數(shù)實(shí)現(xiàn)流體模擬的方法，模擬結(jié)果質(zhì)量較好，但具體的實(shí)現(xiàn)原理并沒(méi)有說(shuō)明；針對(duì)求解偏微分方程的迭代算法的并行化設(shè)計(jì)方法,采用GPU實(shí)現(xiàn)了算法加速，雖然最高已達(dá)到9倍的加速，但依然不能滿足實(shí)時(shí)流體模擬的需求[6]。文獻(xiàn)[7]通過(guò)對(duì)SMAC算法離散化過(guò)程進(jìn)行分析，為該算法并行化提供了理論依據(jù)，基于OpenGL和Cg語(yǔ)言在NV40顯卡上得以實(shí)現(xiàn)，但限于當(dāng)時(shí)的軟硬件條件，很多步驟并沒(méi)有在GPU上執(zhí)行，導(dǎo)致加速比都不是很高，無(wú)法達(dá)到實(shí)時(shí)處理的要求。

本文擬采用點(diǎn)差分方法完成SMAC算法的離散化操作，討論該算法在CUDA平臺(tái)上實(shí)現(xiàn)時(shí)的數(shù)據(jù)存儲(chǔ)算法、數(shù)據(jù)訪存機(jī)制及線程分配，采用并行SMAC算法實(shí)現(xiàn)流體實(shí)時(shí)模擬。

1　SMAC算法原理及CUDA平臺(tái)概述

1.1SMAC算法原理

流體模擬的基本方程N(yùn)-S方程[8]采用交錯(cuò)網(wǎng)格離散化整個(gè)求解域。二維N-S方程的無(wú)量綱表達(dá)式為[7]

(1)

(2)

(3)

其中，x和y分別表示流場(chǎng)的橫坐標(biāo)和縱坐標(biāo)，p表示壓力值，fx和fy分別表示流場(chǎng)在x和y方向受到的外力，u和v分別表示在x和y方向的流場(chǎng)速度，Re表示雷諾系數(shù)。

針對(duì)每個(gè)模擬節(jié)點(diǎn)，令中間變量F和G表示為

(4)

(5)

其中δt表示時(shí)間步進(jìn)長(zhǎng)度，n為模擬的迭代步數(shù)，將式(4)和式(5)分別代入式(1)和式(2)，可得到

(6)

(7)

為保證速度場(chǎng)滿足無(wú)源條件，引入壓力投影映像來(lái)修正速度場(chǎng)，將式(6)和式(7)代入式(3)，得到壓力項(xiàng)的求解方程為

(8)

顯式求解SMAC算法必須滿足式柯朗-弗里德里希斯-列維(Courant-Friedrichs-Lewy Condition，CFL)條件[9]，即最大速度值滿足

(9)

|umax|δt<δx,|vmax|δt<δy。

(10)

其中δx和δy分別表示x和y的步進(jìn)長(zhǎng)度，umax和vmax分別表示速度場(chǎng)在x和y方向的極大值。所以，在流場(chǎng)中計(jì)算更新仿真步長(zhǎng)，其核心是找到速度場(chǎng)中的極大值。

1.2CUDA并行設(shè)計(jì)架構(gòu)

CUDA將GPU視為一個(gè)并行數(shù)據(jù)計(jì)算的設(shè)備，對(duì)所進(jìn)行的計(jì)算進(jìn)行分配和管理。CUDA主要有線程執(zhí)行模式和存儲(chǔ)組織形式兩個(gè)顯著特點(diǎn)[10-11]。

(1)線程執(zhí)行模式

CUDA采用單指令多線程(Single Instruction Multiple Threads, SIMT)的執(zhí)行模式，即每個(gè)處理單元(Streaming Processor, SP)執(zhí)行1個(gè)線程、多個(gè)SP組成1個(gè)流處理器簇(Streaming Multiprocessor, SM)。每個(gè)SM的SP單元以連續(xù)的32個(gè)線程(稱為1個(gè)warp)為單位來(lái)創(chuàng)建、管理、切換和執(zhí)行指令，調(diào)試器不檢查指令流內(nèi)的依賴性，所以1個(gè)線程塊內(nèi)的線程數(shù)最好是32的整數(shù)倍。

(2)存儲(chǔ)組織形式

CUDA結(jié)構(gòu)中存儲(chǔ)單元可分為全局存儲(chǔ)器、常數(shù)存儲(chǔ)器、共享存儲(chǔ)器和寄存器，如圖1所示。所有線程都可讀寫1塊相同的全局存儲(chǔ)器和1個(gè)只供讀取的常數(shù)存儲(chǔ)器；每個(gè)線程塊都擁有1個(gè)共享存儲(chǔ)器，同一線程塊內(nèi)的所有線程可以讀寫本塊內(nèi)的共享存儲(chǔ)；每個(gè)線程都有1個(gè)容量較小但速度快的私有寄存器。由于訪問(wèn)共享存儲(chǔ)比訪問(wèn)全局存儲(chǔ)快數(shù)百倍，所以針對(duì)同一個(gè)線程塊內(nèi)的線程之間的通信，應(yīng)當(dāng)盡可能地使用共享存儲(chǔ)以減少數(shù)據(jù)訪存延時(shí)。

圖1　CUDA存儲(chǔ)結(jié)構(gòu)

2　SMAC算法改進(jìn)

2.1SMAC算法離散化求解

采用點(diǎn)差分格式離散純二次項(xiàng)及混合二次項(xiàng)[12],則速度場(chǎng)在x和y方向二階偏導(dǎo)的具體差分格式可表示為

(11)

(12)

式中χ為人工粘性系數(shù)(χ=0.9)。

(13)

速度場(chǎng)主離散求解格式為

(14)

(15)

2.2SMAC算法并行實(shí)現(xiàn)步驟

根據(jù)SMAC離散化的過(guò)程，實(shí)現(xiàn)SMAC算法具體步驟如下。

步驟1初始化流場(chǎng)、邊界條件和流場(chǎng)中障礙物分布。

步驟2初始化速度場(chǎng)和壓力場(chǎng)。

步驟3計(jì)算每一個(gè)節(jié)點(diǎn)的F,G。

步驟4根據(jù)式(13)計(jì)算每一個(gè)節(jié)點(diǎn)的p。

步驟5根據(jù)式(14)和式(15)更新速度場(chǎng)。

步驟6根據(jù)式(9)和式(10)重新仿真步長(zhǎng)。

步驟7根據(jù)壓力場(chǎng)計(jì)算流場(chǎng)的密度場(chǎng)。

步驟8繪制密度。

如果速度場(chǎng)變化大于閾值或超過(guò)仿真時(shí)間則結(jié)束模擬過(guò)程，否則從步驟3開(kāi)始下一次迭代。

可以看出，計(jì)算各節(jié)點(diǎn)的F，G和p參數(shù)只與相鄰的4個(gè)節(jié)點(diǎn)和本節(jié)點(diǎn)的上一次迭代狀態(tài)相關(guān)，而與以前的狀態(tài)無(wú)關(guān)，具有時(shí)空局部性，可進(jìn)行并行計(jì)算，從而減少計(jì)算時(shí)間，提高算法的運(yùn)行速度。

3　基于CUDA加速的SMAC流體模擬

采用CPU和GPU協(xié)同的方式完成流體模擬。在CPU中設(shè)定流體的邊界條件，將初始化場(chǎng)景數(shù)據(jù)傳輸?shù)紾PU存儲(chǔ)中，并將每一格點(diǎn)上的計(jì)算任務(wù)分配給一個(gè)計(jì)算核上，當(dāng)?shù)竭_(dá)時(shí)間閾值時(shí)完成流體模擬計(jì)算；最后將模擬完成的場(chǎng)景數(shù)據(jù)傳回CPU端，并利用圖形渲染混合接口實(shí)現(xiàn)流體模擬的可視化操作，具體過(guò)程如圖2所示。

圖2　CUDA加速的SMAC流體模擬流程

3.1數(shù)據(jù)預(yù)處理

在建立場(chǎng)景時(shí)，對(duì)塊間的ghost數(shù)據(jù)(邊緣填充數(shù)據(jù))進(jìn)行預(yù)處理：在各塊的四周用相鄰塊的數(shù)據(jù)進(jìn)行填充，各塊在計(jì)算之前，將填充好的ghost數(shù)據(jù)和本分塊數(shù)據(jù)一同合并讀入共享存儲(chǔ)。中央塊的ghost數(shù)據(jù)將由它周圍的8個(gè)數(shù)據(jù)塊中對(duì)應(yīng)的數(shù)據(jù)組成。從而減少在模擬迭代過(guò)程中進(jìn)行全局存儲(chǔ)訪問(wèn)的操作次數(shù)。數(shù)據(jù)填充如圖3所示。

圖3　數(shù)據(jù)填充

假設(shè)流體模擬場(chǎng)景m×n，將其分解為T×T大小的塊。原始場(chǎng)景用I(i,j)表示，變換后的場(chǎng)景用O(i,j) 表示，則流體模擬場(chǎng)景數(shù)據(jù)預(yù)處理過(guò)程可劃分為兩個(gè)主要部分，偽代碼如下。

(1)對(duì)邊界及ghost元素的處理

for (i=0;i<(m+2(m/T-1)+2);i++)

for (j=0;j<(n+2(n/T-1)+2);j++)

if(i==0)

O(i,j) =左邊界；

else if(j==0)

O(i,j) =上邊界；

else if(i==(m+2(m/T-1)+1))

O(i,j) =右邊界；

else if(j==(n+2(n/T-1)+1))

O(i,j) =下邊界；

else if(m%((i-1)*T)==0) {

if(n%((j-2)*T)==0)

O(i,j) = I(i-1,j+1);//右上角ghost元素

else if(n%(j-1)*T)==0)

O(i,j) = I(i-1,j-1); //左上角ghost元素

else

O(i,j)= I(i-1,j); //上邊ghost元素

}

else if(m%((i-2)*T)==0) {

if(n%((j-2)*T)==0)

O(i,j) = I(i+1,j+1);//右下角ghost元素

else if(n%(j-1)*T)==0)

O(i,j) = I(i-1,j+1); //左下角ghost元素

else

O(i,j) = I(i+1,j); //下邊ghost元素

}

else if(n%((j-1)*T)==0)

O(i,j) = I(i,j-1);//左邊ghost元素

else if(n%((j-2)*T)==0)

O(i,j) = I(i,j+1);//右邊ghost元素

(2)對(duì)真實(shí)場(chǎng)景數(shù)據(jù)的處理

for(k=0;k

for(l=0;l

for(j=0;j

for(i=0;i

O(k*T+j+1,l*T+i+1) =I(k*T+j,l*T+i);

}

3.2數(shù)據(jù)傳輸單元設(shè)計(jì)

在場(chǎng)景初始化時(shí)將速度場(chǎng)、壓力場(chǎng)和受力場(chǎng)由CPU傳輸?shù)紾PU，完成場(chǎng)景模擬之后再將速度場(chǎng)和壓力場(chǎng)由GPU傳輸?shù)紺PU；而數(shù)據(jù)填充、對(duì)各節(jié)點(diǎn)的速度場(chǎng)和壓力場(chǎng)計(jì)算及更新均在GPU端完成，從而減少數(shù)據(jù)在顯存和主存中傳輸?shù)拇螖?shù)。

3.3核心計(jì)算單元設(shè)計(jì)

為了避免同1個(gè)warp中出現(xiàn)分支，使用1個(gè)線程計(jì)算1個(gè)節(jié)點(diǎn)的F、G、p信息及速度更新操作，將16×16或32×32個(gè)線程組成1個(gè)線程塊，并根據(jù)模擬場(chǎng)景自動(dòng)確定線程塊數(shù)量。如果要模擬的場(chǎng)景不規(guī)則，則在進(jìn)行模擬之前先對(duì)場(chǎng)景進(jìn)行無(wú)用數(shù)據(jù)填充，再進(jìn)行場(chǎng)景模擬。

利用共享存儲(chǔ)作為數(shù)據(jù)“中轉(zhuǎn)站”以降低非合并訪問(wèn)。同時(shí)經(jīng)過(guò)數(shù)據(jù)填充處理過(guò)的狀態(tài)信息，塊與塊之間的信息是完全不相關(guān)的。利用CUDA提供的訪存延時(shí)隱藏技術(shù)，即在處理過(guò)程中，先啟動(dòng)所有塊對(duì)全局存儲(chǔ)訪問(wèn)，再進(jìn)行計(jì)算，這樣幾乎可以隱藏所有的訪存延時(shí)。

3.4求解迭代步長(zhǎng)單元設(shè)計(jì)

方程解隨著時(shí)間步的遞進(jìn)而更新，直到計(jì)算時(shí)間溢出。設(shè)定空間步長(zhǎng)為1，由式(10)確定各時(shí)間步之間的時(shí)間推進(jìn)量。采用并行歸約方法計(jì)算每一個(gè)時(shí)間步的速度最大值[12]，具體如圖4所示。假如對(duì)N個(gè)數(shù)據(jù)進(jìn)行求極大值操作，開(kāi)啟N/2個(gè)線程分別進(jìn)行兩兩比較大小，如0號(hào)線程求第0和第N/2+1個(gè)數(shù)據(jù)中的較大值，結(jié)果寫入第0個(gè)數(shù)據(jù)的存儲(chǔ)空間，同理可推其他線程計(jì)算的數(shù)據(jù)；每個(gè)循環(huán)參與計(jì)算的線程數(shù)減半，最后，0號(hào)單元的數(shù)據(jù)和1號(hào)單元的數(shù)據(jù)比較以計(jì)算出極大值，此算法將求極大值運(yùn)算復(fù)雜度降為log2(n)。在實(shí)現(xiàn)過(guò)程中，首先在同一個(gè)線程塊內(nèi)完成速度場(chǎng)每行極大值的計(jì)算，然后將各線程塊的極大值(即各行的極大值)放在0號(hào)線程塊中計(jì)算出速度極大值。

圖4　并行歸約求極大值

4　實(shí)驗(yàn)方法與結(jié)果分析

為了驗(yàn)證改進(jìn)后的SMAC算法在流體模擬中的有效性和效率，采用基于Intel i7 5500U的CPU、基于nVIDIA GTX560處理器的GPU和分別基于gcc 和nvcc3.0平臺(tái)的編譯器，分別完成了基于SMAC算法流體模擬的串行及并行實(shí)現(xiàn)。并且，對(duì)不同計(jì)算規(guī)模下的單次迭代及相同計(jì)算規(guī)模下多次迭代的性能進(jìn)行了分析。

4.1單次迭代的性能分析

表1為模擬1個(gè)時(shí)間步長(zhǎng)的運(yùn)行時(shí)間分布，在不同計(jì)算規(guī)模下，CPU耗費(fèi)的時(shí)間同GPU耗費(fèi)的時(shí)間對(duì)比。其中GPU計(jì)算時(shí)間只包括GPU上由原始速度場(chǎng)u、v，力場(chǎng)fx、fy，初始?jí)毫?chǎng)p計(jì)算得到1個(gè)時(shí)間步的速度場(chǎng)和壓力場(chǎng)的時(shí)間，不包括GPU和CPU之間數(shù)據(jù)傳輸時(shí)間，即純粹計(jì)算時(shí)間。

表1　單步長(zhǎng)的加速時(shí)間分布

從表1可看出，當(dāng)模擬的流場(chǎng)較大(1 024×1 024)時(shí)，采用CPU實(shí)現(xiàn)的串行計(jì)算方法每秒僅可完成約6次流體場(chǎng)景計(jì)算，無(wú)法實(shí)現(xiàn)實(shí)時(shí)流體場(chǎng)景模擬。然而，采用并行SMAC算法每秒僅可完成數(shù)百次對(duì)流體場(chǎng)景模擬計(jì)算，所以完全可實(shí)現(xiàn)實(shí)時(shí)流體場(chǎng)景模擬。

4.2多次迭代性能分析

表2為計(jì)算規(guī)模(512×512)一定時(shí)，不同迭代次數(shù)CPU的時(shí)間同GPU的時(shí)間對(duì)比。其中GPU計(jì)算時(shí)間表示GPU+CPU的計(jì)算總時(shí)間，包括將原始速度場(chǎng)u、v，力場(chǎng)fx、fy，初始?jí)毫?chǎng)p由CPU傳輸?shù)紾PU，和將模擬后的速度場(chǎng)u、v、壓力場(chǎng)p傳輸回CPU的傳輸時(shí)間，和在GPU上多次迭代的運(yùn)算時(shí)間。CPU計(jì)算時(shí)間表示CPU串行模擬時(shí)間。

表2　多步長(zhǎng)的加速時(shí)間分布

從表2可以看出，針對(duì)中等規(guī)模(512×512)的流體模擬場(chǎng)景，在場(chǎng)景不是十分復(fù)雜(即在迭代次數(shù)小于100時(shí)求解方程收斂)的情況下，采用GPU并行實(shí)現(xiàn)方法模擬速度可達(dá)到20～30 fps，基本可滿足實(shí)時(shí)流體模擬的要求。

從實(shí)驗(yàn)結(jié)果可以看出，采用點(diǎn)差分離散方法對(duì)SMAC算法進(jìn)行離散化，并采用數(shù)據(jù)填充算法及各種優(yōu)化計(jì)算方面可以完成對(duì)一般流體場(chǎng)景進(jìn)行實(shí)時(shí)模擬的工作。

5　結(jié)語(yǔ)

采用點(diǎn)差分離散方法實(shí)現(xiàn)SMAC算法中求解壓力場(chǎng)、速度更新等操作的并行化處理。然后，從減少數(shù)據(jù)傳輸、提高訪存比及增加線程并行度等方面，對(duì)離散化的SMAC算法在CUDA平臺(tái)下進(jìn)行改進(jìn)和優(yōu)化。最后，將改進(jìn)后的算法在CUDA架構(gòu)下實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，基于CUDA架構(gòu)的SMAC并行算法提速效果明顯，可實(shí)現(xiàn)對(duì)一般場(chǎng)景的實(shí)時(shí)模擬工作。

[1]佟志忠, 姜洪洲, 韓俊偉. GPU加速的二維流體實(shí)時(shí)流動(dòng)仿真[J/OL]. 哈爾濱工程大學(xué)學(xué)報(bào), 2008, 29(3):278-284[2015-12-22]. http://d.wanfangdata.com.cn/Periodical/hebgcdxxb200803015. DOI:1006-7043( 2008) 03-0278-07.

[2]STAM J. Stable fluids[J/OL]. Acm Transactions on Graphics, 1999:121-128[2015-12-20]. http://www.dgp.toronto.edu/people/stam/reality/Research/pdf/ns.pdf.

[3]AMSDEN A A, HARLOW F H. A Simplified MAC Technique for Incompressible Fluid Flow Calculations Physics[J/OL]. Journal of Computational , 1970, 6(2): 322-325[2015-12-20]. http://dx.doi.org/10.1016/0021-9991(70)90029-X.

[4]張永學(xué), 曹樹(shù)良, 祝寶山. 求解不可壓三維湍流的隱式SMAC方法[J/OL]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2005, 45(11):1561-1564[2015-12-30]. http://dx.chinadoi.cn/10.3321/j.issn%3a1000-0054.2005.11.031.

[5]KRAUS J, SCHLOTTKE M, ADINETZ A, et al. Accelerating a C++ CFD code with OpenACC[C/OL]// 2014 First Workshop on Accelerator Programming using Directives (WACCPD), New Orleans, LA:IEEE, 2014:47-54[2015-12-30]. http://dx.doi.org/10.1109/WACCPD.2014.11.

[6]AMADOR G, GOMES A. CUDA-Based Linear Solvers for Stable Fluids[C/OL]// 2010 International Conference on Information Science and Applications (ICISA), Texas , LA:IEEE, 2010:1-8[2015-12-30]. http://dx.doi.org/10.1109/ICISA.2010.5480268.

[7]SCHEIDEGGER C E, COMBA J L D, Da C R D. Practical CFD Simulations on Programmable Graphics Hardware using SMAC[J/OL]. Computer Graphics Forum, 2005, 24(24):715-728[2015-12-30]. http://dx.doi.org/10.1111/j.1467-8659.2005.00897.x.

[8]CHORIN A J. Numerical Solution of the Navier-Stokes Equations*[J/OL]. Mathematics of Computation, 1968, 22(104):17-34 [2016-1-1]. http://dx.doi.org/10.1016/B978-0-12-174070-2.50005-8.

[9]LAX P D, HERSH R, JELTSCHR, et al. The Courant-Friedrichs-Lewy (CFL) Condition[J/OL]. Communications on Pure & Applied Mathematics, 1962, 15(4):363-371[2016-1-1]. http://link.springer.com/978-0-8176-8394-8.DOI: 10.1007/978-0-8176-8394-8.

[10]KIRK D B. Programming Massively Parallel Processors[M/OL].北京：清華大學(xué)出版社, 2010：24-46[2016-1-10]. http://www.doc88.com/p-2939593408781.html.

[11]COOK S. CUDA Programming: A Developer’s Guide to Parallel Computing with GPUs[M/OL]. Morgan Kaufmann Publishers Inc., 2012：155[2016-1-10].http://download.csdn.net/detail/niexiao2008/5780159.

[12]HIRSCH C.Numerical computation of internal and external flows [M/OL]. Butterworth-Heinemann, 2007:491-539[2016-1-10].http://dx.doi.org/10.1016/B978-075066594-0/50053-9.

[13]李大力，張理論，徐傳福,等. 雅可比迭代的CPU/GPU并行計(jì)算及在CFD中的應(yīng)用[C/OL]// 2012全國(guó)高性能計(jì)算學(xué)術(shù)年文集.張家界:中國(guó)計(jì)算機(jī)學(xué)會(huì),中國(guó)軟件行業(yè)協(xié)會(huì)，2012：1-8[2016-1-10].http://www.ccf.org.cn/sites/ccf/gxnjs.jsp#8.

[責(zé)任編輯：祝劍]

SMAC algorithm parallelization based on CUDA

CHANG Libo1，DU Huimin1，HAN Jungang2

(1. School of Electronic Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China;2. School of Computer Science and Technology, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

SMAC (Simplified Marker and Cell) algorithm is improved in order to enhance the ability of real time processing for fluid simulation. The algorithm is discretized for solving pressure field and update speed used by central difference scheme. A data storage algorithm that can eliminate data correlation is proposed to reduce data transmission. Usage of memory is optimized based on CUDA and the parallel computing threads into appropriate blocks is organized to make better use of stream multiprocessor in GPU. The discretization of the SMAC algorithm is improved, optimized and parallel implemented under the CUDA (unified computing device architecture) platform. Result show that GPU-based implementation of SMAC can achieve a significant speedup compared with CPU based counterpart both in the SMAC algorithm and in real simulation. Therefore the improved algorithm can achieve real-time simulation of the general scene.

computational fluid dynamics, compute unified device architecture, parallel algorithm

10.13682/j.issn.2095-6533.2016.05.007

2016-03-14

國(guó)家自然科學(xué)基金資助項(xiàng)目(61136002)；西安市科技發(fā)展計(jì)劃資助項(xiàng)目(CXY1440(10))

常立博(1985-)，男，助教，碩士，從事計(jì)算機(jī)體系結(jié)構(gòu)、高性能計(jì)算研究。E-mail: changlibo@xupt.edu.cn

杜慧敏(1967-)，女，教授，博士，CCF會(huì)員。從事計(jì)算機(jī)體系結(jié)構(gòu)、計(jì)算機(jī)圖形學(xué)研究。E-mail: duhuimin0529@126.com

TP338.6

A

2095-6533(2016)05-0033-06