鮑春永　趙啦啦　劉萬英　楊康康

(中國礦業(yè)大學(xué)機(jī)電工程學(xué)院　江蘇 徐州 221008)

?

基于GPU的圖形學(xué)加速算法在離散元法中的應(yīng)用

鮑春永趙啦啦劉萬英楊康康

(中國礦業(yè)大學(xué)機(jī)電工程學(xué)院江蘇 徐州 221008)

摘要顆粒離散元法是一種廣泛應(yīng)用于研究顆粒物料力學(xué)行為的數(shù)值模擬方法，而計算效率是制約其發(fā)展和應(yīng)用的主要因素之一。通過Pro/E軟件建立了料斗模型，利用Stream DEM軟件對料斗的顆粒充填過程進(jìn)行離散元法模擬研究，并對基于CPU和GPU加速算法的運(yùn)算過程和結(jié)果進(jìn)行對比。結(jié)果表明，基于GPU的計算機(jī)圖形學(xué)加速算法可大幅提高顆粒離散元法模擬過程的運(yùn)算效率。當(dāng)填充顆粒數(shù)量達(dá)到13萬時，其運(yùn)算效率比基于CPU的運(yùn)算效率提高了10倍以上。

關(guān)鍵詞離散元法圖形學(xué)算法GPUCPU

0引言

離散元法DEM(discreteelementmethod)發(fā)起于20世紀(jì)70年代。作為一種數(shù)值方法，主要用于模擬離散顆粒組合體在準(zhǔn)靜態(tài)和動態(tài)條件下的變形及破壞過程，在包括巖石力學(xué)、土力學(xué)、巖土工程、顆粒運(yùn)輸、脆性材料加工、物料分選等散體工程技術(shù)領(lǐng)域得到成功推廣和使用，是目前研究顆粒系統(tǒng)力學(xué)行為的有效數(shù)值方法。通過離散元方法能夠得到不容易測量的顆粒級微觀信息，如顆粒在運(yùn)動過程中的位置、速度、加速度、受力狀態(tài)等。這給研究人員提供顆粒離散物質(zhì)的微觀以及宏觀信息，進(jìn)而取代部分的物理實驗，減少在人力，物力以及能源損耗上的投入。經(jīng)過長時間的發(fā)展，離散元法作為一種研究顆粒系統(tǒng)運(yùn)動行為的數(shù)值方法，在國內(nèi)外已經(jīng)得到廣泛的應(yīng)用[1-3]。

基于離散元法的模擬運(yùn)算過程中包含了大量的計算機(jī)圖形學(xué)算法問題，比如，顆粒群的生成、顆粒碰撞檢測預(yù)處理等。當(dāng)利用離散元法對大數(shù)量的顆粒系統(tǒng)進(jìn)行數(shù)值模擬時，計算機(jī)的運(yùn)算量和數(shù)據(jù)存儲量都將隨著顆粒數(shù)量的增加而成幾何級數(shù)的增長，從而導(dǎo)致整個模擬過程費(fèi)時費(fèi)力。解決顆粒數(shù)量對離散元計算的限制已成為離散元法應(yīng)用和發(fā)展過程中亟待解決的重要問題之一[4-6]。

隨著GPU技術(shù)的發(fā)展，GPU除了應(yīng)用于圖形處理外，還能用于應(yīng)用計算。GPU的并行處理功能能夠在很大程度上提高計算速度?；贕PU的加速算法已經(jīng)在動畫繪制、體繪制等方面取得了應(yīng)用[7,8]。因此，基于GPU的計算機(jī)圖形學(xué)加速算法為解決離散元法應(yīng)用中大量顆粒的高效運(yùn)算問題提供了一個新方法。

基于此，本文將基于GPU的計算機(jī)圖形學(xué)加速算法應(yīng)用于顆粒離散元法模擬過程中，建立起了料斗的顆粒充填模型。并基于CPU和GPU兩種不同運(yùn)算方法對料斗充填過程進(jìn)行數(shù)值模擬。并對模擬過程的運(yùn)算時間進(jìn)行比較，驗證基于GPU的計算機(jī)圖形學(xué)加速算法應(yīng)用于顆粒離散元法模擬的可行性和有效性。

1顆粒離散元法基本原理

顆粒離散元法是由Cundall和Strack在1979年提出的研究離散顆粒物質(zhì)結(jié)構(gòu)和運(yùn)動規(guī)律的一種數(shù)值方法，其思想起源于分子動力學(xué)。與以彈性體力學(xué)和流體力學(xué)為基礎(chǔ)的連續(xù)介質(zhì)理論對顆粒物質(zhì)的描述不同，顆粒離散元法把所要研究的對象分離為剛性元素的集合，使每個元素滿足牛頓第二定律，用中心差分的方法求解各元素的運(yùn)動方程，得到顆粒組合的整體運(yùn)動狀態(tài)。顆粒離散元法理論來自于Hertz和Mindlin-Deresiewicz的球形顆粒接觸理論，使用簡化的軟球和硬球顆粒的接觸模型，實現(xiàn)對顆粒物質(zhì)的運(yùn)動以及各種微觀行為的數(shù)值計算[9]。

顆粒離散元法的基本計算流程如圖1所示。

圖1　顆粒離散元法求解流程圖

其計算過程為：

(1) 初始化系統(tǒng)，對每個顆粒給定一個起始時間時的初始位置以及初始速度，并給定數(shù)值計算的時間步長；

(2) 對顆粒進(jìn)行碰撞接觸檢測，確定當(dāng)前時刻系統(tǒng)中的所有碰撞接觸，通常分為空間劃分和空間判定兩步：

(3) 根據(jù)第(2)步中的碰撞接觸檢測結(jié)果，計算碰撞顆粒間的接觸力；

(4) 進(jìn)一步計算作用于每個顆粒上的合力以及合力矩；

(5) 根據(jù)牛頓第二運(yùn)動定律，結(jié)合給定的計算時間步長，利用迭代算法，更新顆粒的位置、速度和加速度等參數(shù)，同時數(shù)值計算的時間增加一個時間步長；

(6) 如果迭代計算完成，則保存計算結(jié)果并退出程序，否則繼續(xù)進(jìn)行顆粒接觸判斷，循環(huán)執(zhí)行。

由上述顆粒離散元法求解過程可知，當(dāng)顆粒數(shù)量大幅度增加時，顆粒群的生成和接觸判斷所需要的計算量將快速增大，計算資源將被大量地占用，從而導(dǎo)致顆粒離散元法求解過程中的效率降低，計算過程所用時間過長。因此，解決顆粒數(shù)量對離散元計算過程的影響已成為離散元法應(yīng)用和發(fā)展過程中所面臨的重要問題之一。

2基于GPU的加速算法原理

圖形圖像的負(fù)載包括復(fù)雜頂點、幾何圖形和像素處理任務(wù)圖等，這些負(fù)載是高度并行的，適合于多核高延遲的多線程處理。GPU作為一種專門的多線程并行處理器，其流處理器對于高效處理大規(guī)模的像素點，有其特有的優(yōu)勢。同時，對于CUDA(ComputeUnifiedDeviceArchitecture)的開發(fā)解決了GPU編程問題。運(yùn)用CUDA的編碼架構(gòu)，可以讓編碼器從復(fù)雜的SAD(SumofAbsoluteDifferences)計算中釋放，將計算過程交由具有并行處理能力的GPU執(zhí)行，CPU只執(zhí)行選擇控制和邏輯控制。傳統(tǒng)的信息處理模式是在CPU上進(jìn)行的，然而當(dāng)處理的信息量較大時，就會出現(xiàn)運(yùn)行緩慢的問題，GPU快速計算的編程能力和CUDA并發(fā)執(zhí)行的特點可以很好地解決這一問題。CUDA使用新的計算體系結(jié)構(gòu)來利用GPU硬件資源，能夠?qū)崿F(xiàn)比CPU更加優(yōu)越的大規(guī)模的數(shù)據(jù)計算能力。CUDA采用C語言作為編程語言提供大量的高性能計算指令開發(fā)能力，使開發(fā)者能夠在GPU的強(qiáng)大計算能力的基礎(chǔ)上建立起一種效率更高的密集數(shù)據(jù)計算解決方案[10-12]。

與傳統(tǒng)的依靠CPU進(jìn)行圖像動畫渲染計算的服務(wù)器相比，基于GPU運(yùn)算的宗旨是實現(xiàn)圖形加速，其設(shè)計的主要目的是優(yōu)化圖形加速的相關(guān)運(yùn)算，如z-buffering消隱、紋理映射、圖形的坐標(biāo)位置變換與光照計算等?；贕PU的計算偏重于圖形渲染運(yùn)算和大規(guī)模并行計算，依靠集群服務(wù)器實現(xiàn)實時光線追蹤渲染，從而保證圖形圖像的最終現(xiàn)實效果[13-15]。

3料斗充填過程的離散元法模擬

3.1料斗模型的建立

圖2　料斗幾何模型

本文利用Pro/E軟件建立了料斗的幾何模型，并將該模型作為離散元法模擬的顆粒充填的容器，其結(jié)構(gòu)形狀如圖2所示。其中，料斗模型的總體高度為2000mm，料斗大端圓柱體直徑D1為2000mm，大端圓柱體高H1為500mm，小端圓柱體直徑D2為1000mm，小端圓柱體高H3為1000mm。

利用StreamDEM軟件建立模擬運(yùn)算的虛擬邊界。新建圓柱幾何模型，其半徑為1000mm，高為1000mm，并將其設(shè)置為虛擬邊界，適當(dāng)移動虛擬邊界的位置，使其與料斗幾何模型的大端圓柱體平齊。充填顆粒的材料屬性設(shè)置為煤塊[16]，顆粒粒徑分布采用等粒徑分布，顆粒碰撞模型為HertzModel，靜態(tài)填充率設(shè)置為0.2。本文采用通過改變粒徑大小的方法來獲得不同的充填顆粒數(shù)量。表1給出了模擬過程中所采用的不同顆粒粒徑以及顆粒粒徑對應(yīng)的顆粒數(shù)量。

表1　不同顆粒粒徑所對應(yīng)的顆粒數(shù)量

3.2充填過程模擬及結(jié)果

利用StreamDEM離散元仿真軟件進(jìn)行模擬運(yùn)算。將上述利用Pro/E軟件所建立的料斗幾何模型轉(zhuǎn)化為.stl圖形格式并導(dǎo)入StreamDEM軟件中，對顆粒的充填過程進(jìn)行模擬。模擬過程中，分別采用StreamDEM軟件中內(nèi)置的CPU處理器和GPU處理器的功能模塊進(jìn)行運(yùn)算。基于CPU處理器運(yùn)算時，所利用的硬件為英特爾G41ExpressChipset(1GB/戴爾OptiPlex380MiniTower)?；贕PU處理器運(yùn)算時，所利用的硬件為NVIDIAGeForceGTX650顯卡。模擬運(yùn)算的時間步長設(shè)置為1.0～0.5s，輸出間隔為0.1s，總物理時長設(shè)置為1s。

顆粒充填料斗過程的離散元法模擬結(jié)果如圖3所示。其中，(a)為基于CPU處理器的充填過程模擬結(jié)果，(b)為基于GPU處理器的充填過程模擬結(jié)果。根據(jù)所得的模擬結(jié)果，可獲得基于CPU處理器和GPU處理器的不同數(shù)量顆粒完成充填所需的運(yùn)算時間，其對比情況如圖4所示。

圖3　顆粒充填料斗過程的離散元法模擬

圖4　基于CPU和GPU的料斗充填過程運(yùn)算時間

由圖4可以看出，基于CPU處理器進(jìn)行模擬時，所需的運(yùn)算時間隨著顆粒數(shù)量的增多而快速增加。而基于GPU處理器進(jìn)行模擬時，所需的運(yùn)算時間隨著顆粒數(shù)量的增多而緩慢增加。當(dāng)顆粒數(shù)量相同時，基于CPU處理器模擬所需時間均多于基于GPU處理器模擬所需時間，并且隨著顆粒數(shù)量的增加，兩者的運(yùn)算效率差別越顯著。當(dāng)顆粒數(shù)量約為1萬個時，CPU運(yùn)算需要1258s，而GPU運(yùn)算僅需132s，運(yùn)算效率相差近10倍。當(dāng)顆粒數(shù)量增加至約為13萬個時，CPU運(yùn)算時間極大增加至14 010s，而GPU運(yùn)算則僅需1270s，兩者運(yùn)算效率相差達(dá)10倍以上?？梢姡趫D形處理器GPU的加速算法能顯著提高離散元法的運(yùn)算效率。

4結(jié)語

本文利用StreamDEM離散元仿真軟件對料斗的顆粒充填過程進(jìn)行了數(shù)值模擬，并對基于CPU和基于GPU加速算法的運(yùn)算過程進(jìn)行了比較，得出以下結(jié)論：

(1) 隨著模擬顆粒數(shù)量的增加，基于CPU的運(yùn)算時間急劇增加，而基于GPU的運(yùn)算時間則緩慢增加。當(dāng)顆粒數(shù)量相同時，基于GPU的計算機(jī)圖形學(xué)加速算法的運(yùn)算效率比基于CPU的運(yùn)算效率提高了10倍。

(2) 基于GPU的計算機(jī)圖形學(xué)加速算法可顯著提高離散元程序的運(yùn)算效率，為提高大數(shù)量顆粒系統(tǒng)的離散元法模擬效率提供了新方法。

參考文獻(xiàn)

[1] 趙啦啦,趙躍民,劉初升,等.濕顆粒堆力學(xué)特性的離散元法模擬研究[J].物理學(xué)報,2014,63(3):265-273.

[2] 田瑞霞,焦紅光,白璟宇.離散元法在礦物加工工程中的應(yīng)用現(xiàn)狀[J].選煤技術(shù),2012,2(1):72-76.

[3]ZhuHP,ZhouZY,YangRY.Discreteparticlesimulationofparticulatesystems:Areviewofmajorapplicationsandfindings[J].ChemicalEngineeringScience,2007,62(13):3378-3396.

[4] 徐佩華,黃潤秋,鄧輝.顆粒離散元法的顆粒破碎研究進(jìn)展[J].工程地質(zhì)學(xué)報,2012,20(3):410-418.

[5] 趙魏,鄒聲勇,姬建剛,等.離散元法在磨機(jī)設(shè)計中的應(yīng)用[J].礦山機(jī)械,2013,41(2):66-70.

[6] 趙啦啦.振動篩分過程的三維離散元法模擬研究[D].徐州:中國礦業(yè)大學(xué),2010.

[7] 王妙一,王斌,雍俊海.GPU上的水彩畫風(fēng)格實時渲染及動畫繪制[J].圖學(xué)學(xué)報,2012,33(3):73-79.

[8] 袁斌.基于曲率的GPU光線投射[J].圖學(xué)學(xué)報,2012,33(6):24-30.

[9] 王國強(qiáng),郝萬軍,王繼新.離散單元法及其在EDEM上的實踐[M].西安:西北工業(yè)大學(xué)出版社,2010.

[10] 張云泉,張先軼,賈海鵬,等.OpenCL異構(gòu)計算[M].2版.北京:清華大學(xué)出版社,2013.

[11] 蘇統(tǒng)華,李東,李松澤,等.CUDA并行程序設(shè)計-GPU編程指南[M].北京:機(jī)械工業(yè)出版社,2014.

[12] 姚勇,王小琴.GPU精粹-實時圖形編輯的技術(shù)、技巧和技藝[M].北京:人民郵電出版社,2006.

[13] 楊柏林,陳根浪,王聰.GPU精粹3[M].北京:清華大學(xué)出版社,2010.

[14] 劉旭江,徐圓,齊洪亮,等.基于GPU的醫(yī)學(xué)圖像多功能可視化的實現(xiàn)[J].計算機(jī)應(yīng)用與軟件,2013,30(5):52-55,64.

[15] 鄭曉薇,侯立斐,于夢玲.GPU并行計算在LSSVM股票預(yù)測上的研究與應(yīng)用[J].計算機(jī)應(yīng)用與軟件,2013,30(1):34-36.

[16] 胡國明.顆粒系統(tǒng)的離散元素法分析仿真:離散元素法的工業(yè)應(yīng)用與EDEM軟件簡介[M].武漢:武漢理工大學(xué)出版社,2010.

APPLICATION OF GPU-BASED GRAPHICS ACCELERATION ALGORITHMINDISCRETEELEMENTMETHOD

Bao ChunyongZhao LalaLiu WanyingYang Kangkang

(School of Mechanical and Electrical Engineering,China University of Mining and Technology,Xuzhou 221008,Jiangsu,China)

AbstractParticle discrete element method is a kind of numerical simulation method widely used in the research of granular material mechanics behaviour. Computation efficiency is one of the main factors that restricts its development and application. In this paper, we build a hopper model by using Pro/E software, and use Stream DEM software to study the stimulations of discrete element method in regard to hopper’s particles filling process. We also compare the operation processes and results of CPU-based and GPU-based acceleration algorithms. Results show that the GPU-based computer graphics acceleration algorithm can dramatically improve the computation efficiency of the simulation process of particle discrete element method. When the number of particles to be filled reaches 130 000, its computational efficiency improves over 10 times than that of the CPU-based acceleration algorithm.

KeywordsDiscrete element methodGraphics algorithmGPUCPU

收稿日期：2014-10-27。國家自然科學(xué)基金青年科學(xué)基金項目(51204181)；高等學(xué)校博士學(xué)科點專項科研基金項目(20110095120004)；中國博士后科學(xué)基金項目(20110491485，2013T60576)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項資金項目(2011QNA10)；江蘇高校優(yōu)勢學(xué)科建設(shè)工程課題。鮑春永，碩士生，主研領(lǐng)域：計算機(jī)圖形學(xué)理論，離散元法模擬。趙啦啦，副教授。劉萬英，碩士生。楊康康，碩士生。

中圖分類號TP301.4

文獻(xiàn)標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.018