鮑春永　趙啦啦　劉萬(wàn)英　楊康康

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

?

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

鮑春永趙啦啦劉萬(wàn)英楊康康

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

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

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

0引言

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

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

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

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

1顆粒離散元法基本原理

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

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

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

其計(jì)算過(guò)程為：

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

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

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

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

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

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

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

2基于GPU的加速算法原理

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

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

3料斗充填過(guò)程的離散元法模擬

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)移動(dòng)虛擬邊界的位置，使其與料斗幾何模型的大端圓柱體平齊。充填顆粒的材料屬性設(shè)置為煤塊[16]，顆粒粒徑分布采用等粒徑分布，顆粒碰撞模型為HertzModel，靜態(tài)填充率設(shè)置為0.2。本文采用通過(guò)改變粒徑大小的方法來(lái)獲得不同的充填顆粒數(shù)量。表1給出了模擬過(guò)程中所采用的不同顆粒粒徑以及顆粒粒徑對(duì)應(yīng)的顆粒數(shù)量。

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

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

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

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

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

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

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

4結(jié)語(yǔ)

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

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

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

參考文獻(xiàn)

[1] 趙啦啦,趙躍民,劉初升,等.濕顆粒堆力學(xué)特性的離散元法模擬研究[J].物理學(xué)報(bào),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] 徐佩華,黃潤(rùn)秋,鄧輝.顆粒離散元法的顆粒破碎研究進(jìn)展[J].工程地質(zhì)學(xué)報(bào),2012,20(3):410-418.

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

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

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

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

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

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

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

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

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

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

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

[16] 胡國(guó)明.顆粒系統(tǒng)的離散元素法分析仿真:離散元素法的工業(yè)應(yīng)用與EDEM軟件簡(jiǎn)介[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。國(guó)家自然科學(xué)基金青年科學(xué)基金項(xiàng)目(51204181)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金項(xiàng)目(20110095120004)；中國(guó)博士后科學(xué)基金項(xiàng)目(20110491485，2013T60576)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2011QNA10)；江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程課題。鮑春永，碩士生，主研領(lǐng)域：計(jì)算機(jī)圖形學(xué)理論，離散元法模擬。趙啦啦，副教授。劉萬(wàn)英，碩士生。楊康康，碩士生。

中圖分類號(hào)TP301.4

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

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