基于GPU的圖形學加速算法在離散元法中的應用

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

(中國礦業大學機電工程學院　江蘇 徐州 221008)

?

基于GPU的圖形學加速算法在離散元法中的應用

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

(中國礦業大學機電工程學院江蘇 徐州 221008)

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

關鍵詞離散元法圖形學算法GPUCPU

0引言

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

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

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

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

1顆粒離散元法基本原理

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

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

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

其計算過程為：

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

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

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

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

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

(6) 如果迭代計算完成，則保存計算結果并退出程序，否則繼續進行顆粒接觸判斷，循環執行。

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

2基于GPU的加速算法原理

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

與傳統的依靠CPU進行圖像動畫渲染計算的服務器相比，基于GPU運算的宗旨是實現圖形加速，其設計的主要目的是優化圖形加速的相關運算，如z-buffering消隱、紋理映射、圖形的坐標位置變換與光照計算等。基于GPU的計算偏重于圖形渲染運算和大規模并行計算，依靠集群服務器實現實時光線追蹤渲染，從而保證圖形圖像的最終現實效果[13-15]。

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

3.1料斗模型的建立

圖2　料斗幾何模型

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

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

表1　不同顆粒粒徑所對應的顆粒數量

3.2充填過程模擬及結果

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

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

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

圖4　基于CPU和GPU的料斗充填過程運算時間

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

4結語

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

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

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

參考文獻

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

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

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

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

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

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

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

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

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

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

[11] 蘇統華,李東,李松澤,等.CUDA并行程序設計-GPU編程指南[M].北京:機械工業出版社,2014.

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

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

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

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

[16] 胡國明.顆粒系統的離散元素法分析仿真:離散元素法的工業應用與EDEM軟件簡介[M].武漢:武漢理工大學出版社,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。國家自然科學基金青年科學基金項目(51204181)；高等學校博士學科點專項科研基金項目(20110095120004)；中國博士后科學基金項目(20110491485，2013T60576)；中央高校基本科研業務費專項資金項目(2011QNA10)；江蘇高校優勢學科建設工程課題。鮑春永，碩士生，主研領域：計算機圖形學理論，離散元法模擬。趙啦啦，副教授。劉萬英，碩士生。楊康康，碩士生。

中圖分類號TP301.4

文獻標識碼A

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