基于Hadoop MapReduce的大規(guī)模線性有限元法并行實現(xiàn)

林 海 銘

(廣東省建筑科學(xué)研究院集團股份有限公司 廣東 廣州 510500)

基于Hadoop MapReduce的大規(guī)模線性有限元法并行實現(xiàn)

林 海 銘

(廣東省建筑科學(xué)研究院集團股份有限公司 廣東 廣州 510500)

面對越來越復(fù)雜的工程問題，單機上的有限元計算不能達到完全解決問題的程度，可以考慮利用新興云計算技術(shù)來解決。設(shè)計合適的桿單元數(shù)據(jù)結(jié)構(gòu)，提出基于MapReduce框架的線性有限單元法并行算法，包括總體剛度陣組裝和CG法求解線性方程組。在6節(jié)點Hadoop實驗集群上，通過大規(guī)?？臻g桁架結(jié)構(gòu)進行數(shù)值驗證。結(jié)果表明采用該算法求解大規(guī)模空間桁架結(jié)構(gòu)簡潔、易用；在總剛組裝階段，網(wǎng)格模型越大，計算節(jié)點越多，計算性能越好；但求解方程組階段，計算性能不理想，有待改善。

云計算 Hadoop MapReduce 線性有限元 空間桁架 并行計算

0 引 言

云計算[1]概念自2007年提出以來，引起了學(xué)術(shù)界和產(chǎn)業(yè)界的極大關(guān)注，許多學(xué)者、業(yè)內(nèi)專家從自己關(guān)注的角度對云計算進行定義。結(jié)合維基百科、伯克利云計算白皮書和美國NIST的定義，本文認為云計算是以虛擬化技術(shù)為基礎(chǔ)，以網(wǎng)絡(luò)為載體，以用戶為主體，以IaaS、PaaS、SaaS服務(wù)為形式，整合大規(guī)模、可擴展的分布式資源進行協(xié)同工作的超級計算范式。簡單地說，云計算是傳統(tǒng)分布式計算在商業(yè)模式上的發(fā)展，用戶通過互聯(lián)網(wǎng)提交計算任務(wù)，云計算將計算任務(wù)拆分成較小的任務(wù)，交給云平臺上的眾多虛擬資源處理，最后將結(jié)果返回給用戶，用戶只需繳納相應(yīng)的計算費用。

云計算的興起，給IT界帶來了巨大的改變，谷歌、IBM、亞馬遜、微軟、臉書等IT巨頭紛紛提出自己的云計算計劃項目，推動云計算技術(shù)的快速發(fā)展，為科學(xué)研究提供了新的計算工具，許多學(xué)者嘗試在科學(xué)計算中使用這一新興技術(shù)。Matsunaga等[2]提出了基于MapReduce的序列比對算法BLAST的并行實現(xiàn)——CloudBLAST，跟BLAST的主流并行算法mpi-BLAST進行比較，結(jié)果表明CloudBLAST在分配任務(wù)方面性能更好。Srirama等[3]建立了面向科學(xué)計算的云框架SciCloud，通過具體問題實例驗證科學(xué)計算中的4類算法，結(jié)果表明Hadoop MapReduce框架實現(xiàn)高度并行的算法時計算效率很高，但實現(xiàn)迭代算法是不如另一個云計算框架Twister。Zhang等[4]提出了求解異步累計迭代計算的通用計算模型，包含單源最短路徑算法SSSP、Jacobi算法、PageRank、Rooted PageRank、 Katz metric、 Adsorption和HITS算法等，設(shè)計分布式框架Maiter實現(xiàn)計算模型，在EC2上進行算例驗證，結(jié)果顯示相對于Hadoop，Maiter在求解迭代算法能獲得60倍的加速比。Jorissen等[5]開發(fā)了一個能無縫控制EC2虛擬計算資源的云計算接口SC2IT，并實現(xiàn)了材料學(xué)中的FEFF9、WIEN2k、MEEP-mpi三個經(jīng)典應(yīng)用。Jakovits等[6]提出了完全適合科學(xué)計算的基于大量協(xié)同并行(BSP)模型的分布式框架Stratus，并用科學(xué)計算常用算法CG法進行性能驗證，對于小規(guī)模問題，Stratus的求解時間跟MPI和mpijava接近，對于大規(guī)模問題，Stratus快很多。Hadoop框架的Map/Reduce任務(wù)必須序列化，這對于科學(xué)計算效率有限，Bai等[7]在Hadoop中加入MPI模塊，使得Hadoop能更好地給任務(wù)分配合適的資源，提高其并行效率，并用分子動力學(xué)仿真算法RESTMD進行驗證。

目前，云計算技術(shù)主要運用于數(shù)據(jù)統(tǒng)計學(xué)和生物信息學(xué)中的一些高度并行算法，還未運用到數(shù)據(jù)密集型、計算密集型的有限元算法中，與有限元計算相關(guān)的線性方程組求解也僅僅只是作為云計算的運用例子進行簡單介紹。本文結(jié)合有限元計算分析和云計算各自的特點，以空間桁架系統(tǒng)的線性有限元方法為例，研究Hadoop MapReduce框架下的有限元網(wǎng)格模型生成計算文件，計算單元剛度陣，組裝有限元系統(tǒng)總體剛度陣，施加位移邊界條件和CG法求解大規(guī)模線性方程組等過程的具體實現(xiàn)細節(jié)。

1 有限元數(shù)據(jù)結(jié)構(gòu)設(shè)計

參考主流有限元計算商業(yè)軟件(如Abaqus、LS-dyna、Dytran等)，將網(wǎng)格模型信息(包含節(jié)點坐標、單元、材料、邊界約束、外力等)按一定格式寫成計算文件，具體格式如下(*表示計算關(guān)鍵字，#表示注釋行，I為整型數(shù)、R為浮點數(shù))：

*material

# mat-NO., E, Mu

I, R, R

*Node

# node-NO., x-Coords, y-Coords, z-Coords

I, R, R, R

*Element

# elem-NO., mat-NO., node-I, node-J, area

I, I, I, I, R

*Constraints

# node-NO., type

I, I

*Force

# node-NO., direction, force

I, I, R

*END

自定義數(shù)據(jù)結(jié)構(gòu)trussElement描述三維桿單元，形式如下：

trussElement {

elemId;

//單元編號

xyz;

//單元節(jié)點坐標

E;

//楊氏模量

A;

//橫截面積

locId;

//節(jié)點全局自由度

}

2 總體剛度陣組裝

由文獻[8]得到桿單元的剛度矩陣如下：

由上式計算出系統(tǒng)中所有單元剛度陣，通過全局自由度映射、組裝成總體剛度陣。有限元系統(tǒng)的剛度陣通常是稀疏對稱正定矩陣，本文采取COO格式壓縮存儲，對于非零元素，存儲格式為(i,j,value)，其中，i、j為矩陣元素行列號，value為矩陣元素。

單剛計算相互獨立，適合并行處理，但在總剛組裝時，傳統(tǒng)并行方法對同一內(nèi)存空間寫數(shù)據(jù)時會有沖突，需要通過特殊的策略來解決。而在MapReduce過程中，Mapper階段各個worker獨立計算單元剛度陣并映射到總體剛度陣中，Reducer階段對Mapper的輸出進行規(guī)約即可完成總體剛度陣的組裝，這個過程中不用顯式存儲總體剛度陣，且worker之間相互獨立，不起讀寫沖突。基于MapReduce的線性有限單元法總體剛度陣組裝的具體實現(xiàn)過程如圖1所示。

圖1 總體剛度陣組裝的MapReduce實現(xiàn)過程

如圖1所示，為自定義的key/value，其中key為桿單元編號，trussElement為自定義的桿單元，包含有限元計算所需的材料、節(jié)點等信息。采用自定義key/value，需要自定義數(shù)據(jù)輸入輸出的類型InputFormat和OutFormat，通過自定義的三個類trussInputForm、trussInputSplit、trussRecordReader完成對數(shù)據(jù)的讀寫和分塊。將包含單元完整信息的格式化計算文件作為輸入文件，NameNode根據(jù)指定格式劃分輸入文件，并將數(shù)據(jù)塊分配到各個DataNode上，分別執(zhí)行Mapper、Combiner和Reducer三個過程完成總體剛度陣的組裝，下面設(shè)計這三個過程的具體實現(xiàn)：

Mapper類：計算單剛，并映射到總剛中。計算節(jié)點將數(shù)據(jù)塊以key/value形式讀入，key為單元的全局編號，value為單元信息trussElement。map()函數(shù)從trussElement中獲取數(shù)據(jù)，計算單剛，得到一個6×6的矩陣。trussElement中單元節(jié)點自由度的全局編號跟單元剛度陣在總體剛度陣中的行列號相對應(yīng)，這樣就能實現(xiàn)單元剛度陣向總體剛度陣的映射。輸出的key/value為：key<行編號，列編號>，value<單剛矩陣元素值>，其中key的類型需要自定義。

Combiner類：規(guī)約Mapper輸出，減少數(shù)據(jù)交換量。在worker上規(guī)約合并本地節(jié)點的Mapper輸出，輸出合并后的結(jié)果，減少本地節(jié)點的數(shù)據(jù)輸出量，從而減少Reducer準備階段節(jié)點之間數(shù)據(jù)的交換，獲得更好的網(wǎng)絡(luò)性能，提高計算效率。

Reducer類：組裝總體剛度陣，并進行COO格式壓縮存儲。Hadoop自動將Combiner輸出結(jié)果中key相同的value合并為>作為Reducer的輸入，reduce()函數(shù)將valuelist中各個元素進行求和操作，并剔除零元素，即實現(xiàn)總剛度矩陣的組裝和COO壓縮，最后將key/value輸出到HDFS上。

3 CG法求解線性方程組的MapReduce實現(xiàn)

在有限元法的求解過程中，得到有限元系統(tǒng)的總體剛度陣后，接下來是施加外力和邊界約束條件。對于桿單元，外力的處理比較簡單，在讀入網(wǎng)格模型數(shù)據(jù)時，只需將節(jié)點力映射到全局自由度上，即可形成載荷向量p。邊界約束條件的引入有許多方法，結(jié)合MapReduce框架的特點，本文采用總體剛度陣對角元素乘大數(shù)法[8]：根據(jù)輸入文件里的邊界約束(零位移約束)，將全局自由度j所對應(yīng)的總剛元素kjj改為αkjj(α為一大數(shù)，通常為1010量級)，載荷向量相應(yīng)的元素pj改為0。到此，得到了系統(tǒng)方程組Ax=p，下面討論CG法求解Ax=p的MapReduce實現(xiàn)。

由CG法的流程圖(圖2)可知，實現(xiàn)CG法的并行化，關(guān)鍵在于矩陣與向量乘法、向量內(nèi)積與向量更新這三個子過程的并行實現(xiàn)，下面介紹MapReduce框架下的實現(xiàn)過程。

圖2 CG法的串行流程圖

3.1 稀疏矩陣與向量乘法的MapReduce實現(xiàn)

基于MapReduce的稀疏矩陣與向量的乘法計算y=Ax的流程如圖3。通過COO壓縮存儲的總體剛度陣A作為輸入文件，向量x通過Hadoop的分布式緩存機制DistributedCache[9]共享到各個計算節(jié)點上。在map階段，采用TextInputFormat類[9]將輸入數(shù)據(jù)塊以鍵值對形式讀入，TextInputFormat類默認“鍵”為數(shù)據(jù)在文件中的偏移量，“值”為一整行數(shù)據(jù)。map計算前，需要從DistributedCache中讀取共享向量來初始化x。在map()函數(shù)中，計算Aijxj，輸出鍵值對(i,Aijxj)。主節(jié)點對map輸出進行整合，將“鍵”相同的鍵值對集合起來傳給從節(jié)點執(zhí)行Reducer過程。在reduce()函數(shù)中直接對輸入鍵值對的“值”求和就能得到結(jié)果向量，輸出并保持到HDFS上，供后續(xù)兩個子過程使用。

圖3 MapReduce框架下并行計算y=Ax

3.2 向量內(nèi)積的MapReduce實現(xiàn)

向量內(nèi)積b=α·β的MapReduce實現(xiàn)跟矩陣向量乘法相似，向量α作為輸入文件，向量β通過DistributedCache共享到各個計算節(jié)點上，向量內(nèi)積的MapReduce實現(xiàn)流程如圖4所示。在map階段，先從DistributedCache中讀取共享向量，然后在map()函數(shù)中將輸入向量元素跟共享變量對應(yīng)的元素相乘，乘積作為map輸出。在reduce階段，直接求和即可完成b=α·β的計算。

圖4 MapReduce框架下b=α·β的并行實現(xiàn)

3.3 向量更新的MapReduce實現(xiàn)

向量更新v=v+αp需要傳遞常數(shù)α到map()函數(shù)中，傳統(tǒng)的編程習(xí)慣就是將其定義成全局變量或者全局常量。但在MapReduce框架下map和reduce是在不同節(jié)點上分布式計算，不能將α定義成全局變量，只能定義成全局常量，在配置Job時通過set()函數(shù)設(shè)置全局常量的值，然后在Mapper階段通過get()函數(shù)獲取。跟向量內(nèi)積相同，向量v作為輸入，向量p共享。map階段，讀取全局常量α并更新v中的每個元素；reduce階段，輸出key/value并保持到HDFS上。

3.4CG法的MapReduce實現(xiàn)

CG法3個子過程的MapReduce實現(xiàn)分別在3.1-3.3節(jié)中作了詳細介紹，本文定義3個類SPMV、VecDot、VecUpdate分別實現(xiàn)這3個過程。在Hadoop平臺上，必須將每個子過程看成一個單獨的Job來處理，實現(xiàn)CG法的關(guān)鍵在于控制Job的啟動、結(jié)束、清理和收斂判斷，為此本文定義類CGSolver來完成這些控制。Job的啟動參數(shù)包含輸入矩陣文件名、結(jié)果文件名、輸入向量文件名、中間數(shù)據(jù)文件名、map數(shù)和reduce數(shù)等，通過定義runSPMVjob()、runVecDotjob()、runVecUpdatejob()這三個驅(qū)動方法配置相應(yīng)子類的啟動參數(shù)。CG法的MapReduce實現(xiàn)算法如下：

算法1MRimplementationofCGmethod

1. set iterative errorε=1e-14,iterativevariablei=0,getmaxiterationfromvectorb;

2.executesub-stepSPMV,computep=Ax,outputtheresultfile;

3.executesub-stepVecUpdate,computep=r=b-Ax,outputtheresultfile;

4.executesub-stepVecDot,computeerror_norm= (r，r);

5.fori=1,2,…,n

5.1setr2 =error_norm;

5.2executesub-stepSPMV,computev=Ap;

5.3executesub-stepVecDot,computeα=r2/(p,v) ;

5.4executesub-stepVecUpdate,computex=x+αpandr=r-αvrespectively;

5.5executesub-stepVecDot,computeerror_norm= (r，r);

5.6if(error_norm<ε)exit;

5.7computeβ=error_norm/r2 ;

5.8executesub-stepVecUpdate,computep=r+βp;

endfor

end

4 算例驗證

采用4個空間桁架結(jié)構(gòu)(表1)驗證總體剛度陣組裝并行算法和CG法求解線性方程組并行算法的正確性、有效性和加速效率。

表1 空間桁架模型信息

4.1 總體剛度陣組裝

在總體剛度陣組裝階段，4個計算模型在不同map數(shù)、不同task數(shù)下的執(zhí)行時間如圖5所示。

圖5 執(zhí)行時間隨Mapper、Rducer變化圖

從圖5可以看出，當(dāng)map數(shù)量足夠多，即有更多計算節(jié)點參與計算時，reduce數(shù)目的增加并不能明顯提高計算性能，在某些情況下甚至?xí)驗橛嬎愎?jié)點將中間數(shù)據(jù)的交換分配和計算任務(wù)的排隊等待而降低計算性能，如圖(a)中mapper=40。本文搭建的Hadoop+Spark集群平臺中每個節(jié)點上配置的map數(shù)和reduce數(shù)均為2，集群平臺總的map數(shù)和reduce數(shù)均為12。當(dāng)計算模型足夠大，能滿足map數(shù)等于或大于12時，集群系統(tǒng)處于飽和狀態(tài)，這種情況下，如果reduce數(shù)設(shè)置為12，各個節(jié)點上map節(jié)點的計算結(jié)果直接進入reduce階段，節(jié)點之間不需要交換計算結(jié)果，這樣能降低通信開銷，提升計算效率，如圖(d)中mapper=20、reducer=12這種情形。但當(dāng)reducer數(shù)目繼續(xù)增多時會因為資源之間的競爭而使計算效率降低，如圖(d)中reducer等于16和20的計算時間總體上都reducer=12的大。

測試4個計算模型在mapper=40、reducer=12和mapper=20、reducer=12兩種情形下的執(zhí)行時間，并跟mapper=1、reducer=1的比較，加速比如圖6所示。加速比隨著計算規(guī)模的增大而增大，由于任務(wù)等待時間更多，情形1的加速比小于情形2的。

圖6 不同模型的加速比(reducer=12)

4.2CG法求解線性方程組

測試4個計算模型每一迭代步內(nèi)1次SPMV、2次VecDot和3次VecUpdate的執(zhí)行時間，結(jié)果如圖7、圖8所示。圖7顯示，計算時間明顯地隨模型規(guī)模的增大而增大，VecDot和VecUpdate的計算量遠小于SPMV，卻需要不少計算時間。這是由于無縫連接SPMV、VecDot、VecUpdate三個過程，將VecDot和VecUpdate的reducer設(shè)置為1，只有一個節(jié)點計算reduce任務(wù)，其他節(jié)點空閑，資源利用率不高，同時其他計算節(jié)點上的map結(jié)果都必須傳送到該節(jié)點上執(zhí)行reduce，節(jié)點之間的數(shù)據(jù)交換量較多，加大了網(wǎng)絡(luò)負載，導(dǎo)致計算效率下降。圖8顯示，隨著計算規(guī)模的增大，SPMV所需計算時間的比重也明顯的增大，這是由于模型增大，計算量增加，用于節(jié)點間的通信和數(shù)據(jù)交換方面的開銷所占比例減?。涣硪环矫?，隨著計算規(guī)模的增大，SPMV比重的增大也說明reducer設(shè)置為1對計算性能的影響減小了，這是因為SPMV、VecDot和VecUpdate的計算量主要集中在map階段，reduce階段的計算量很小。

圖7 3個子過程所需的執(zhí)行時間

圖8 3個子過程計算時間的餅狀圖

不同計算節(jié)點下Model1-Model3的加速比如圖9所示，算法獲得的最大加速比只有1.5，加速效率很低。主要兩個原因：子過程以新的Job提交，HadoopJob的提交和結(jié)束需要花費一定的時間；每個計算過程都需要從HDFS上讀寫數(shù)據(jù)，HDFS的讀寫速度有限，而算法本身的中間數(shù)據(jù)就是可重復(fù)利用的，顯然，MapReduce+HDFS沒辦法實現(xiàn)數(shù)據(jù)的可重復(fù)利用。

圖9 加速比隨節(jié)點數(shù)的變化圖

5 結(jié) 語

本文設(shè)計了合適的桿單元數(shù)據(jù)結(jié)構(gòu)，提出基于MapReduce框架的線性有限單元法并行算法，包括總體剛度陣組裝和CG法求解線性方程組，在6節(jié)點Hadoop實驗集群上，通過大規(guī)?？臻g桁架結(jié)構(gòu)進行數(shù)值驗證。結(jié)果表明采用本文所提的并行算法求解大規(guī)?？臻g桁架結(jié)構(gòu)簡潔、易用；在總剛組裝階段，計算模型越大，參與計算的節(jié)點越多，得到的計算性能越好。但求解方程組階段，計算性能不理想，這是由于子過程以新的Job提交，HadoopJob的提交和結(jié)束需要花費一定的時間。同時，每個計算過程都需要從HDFS上讀寫數(shù)據(jù)，HDFS的讀寫速度有限，而算法本身的中間數(shù)據(jù)就是可重復(fù)利用的，但MapReduce+HDFS沒辦法實現(xiàn)數(shù)據(jù)的重復(fù)利用。

[1]ArmbrustMichael,FoxArmando,GriffithRean,etal.AviewofCloudComputing[J].Commun.ACM,2010,53(4):50-58.

[2]AndréaMatsunaga,MaurícioTsugawa,JoséFortes.CloudBLAST:CombiningMapReduceandvirtualizationondistributedresourcesforbioinformaticsapplications[C]//ProceedingsofIEEEFourthInternationalConferenceoneScience,2008,NewYork:IEEE,2008.

[3]SatishSrirama,OlegBatrashev,EeroVainikko.SciCloud:ScientificComputingontheCloud[C]//Proceedingsof2010 10thIEEE/ACMInternationalConferenceonCluster,CloudandGridComputing,2010,NewYork:IEEE,2010.

[4]YanfengZhang,QixinGao,LixinGao,etal.Acceleratelarge-scaleiterativecomputationthroughasynchronousaccumulativeupdates[C]//Proceedingsofthe3rdworkshoponScientificCloudComputingDate,2012,NewYork:ACM,2012.

[5]KevinJorissen,WilliamJohnson,FernandoDVila,etal.High-performancecomputingwithoutcommitment:SC2IT:Acloudcomputinginterfacethatmakescomputationalscienceavailabletonon-specialists[C]//Proceedingsof2012IEEE8thInternationalConferenceonE-Science,2012,NewYork:IEEE,2012.

[6]PelleJakovits,SatishNarayanaSrirama.IljaKromonov:Adistributedcomputingframeworkforscientificsimulationsonthecloud[C]//Proceedingsof2012IEEE14thInternationalConferenceonHighPerformanceComputingandCommunication,2012.NewYork:IEEE,2012.

[7]ShujuBai,EbrahimKhosravi,Seung-JongPark.AnMPI-enabledMapReduceframeworkformoleculardynamicssimulationapplications[C]//Proceedingsof2013IEEEInternationalConferenceonBioinformaticsandBiomedicine,2013.NewYork:IEEE,2013.

[8] 王勖成.有限單元法[M].北京:清華大學(xué)出版社,2003.

[9]LamChuck.Hadoopinaction[M].NewYork,America:ManningPublicationsCo.,2010.

PARALLEL IMPLEMENTATION OF LARGE-SCALE LINEAR FEM BASEDON HADOOP MAPREDUCE FRAMEWORK

Lin Haiming

(GuangdongProvincialAcademyofBuildingResearchGroupCo.Ltd.,Guangzhou510500,Guangdong,China)

In the face of increasingly complex engineering problems, we cannot completely solve these problems through finite element method(FEM) on a single machine, but we can consider using emerging cloud computing technology. In this paper, we design an appropriate data structure of truss element and propose a parallel algorithm of linear finite element method based on MapReduce framework, including assembling global stiffness matrix and conjugate gradient (CG) method for solving linear equation groups. On the six-node Hadoop experimental cluster, numerical verification is carried out through large-scale spatial truss structures. The results show that it is simple and easy to solve large-scale spatial truss structures by using the proposed algorithm. At the stage of assembling global stiffness matrix, as the size of the mesh model and the number of cluster’s nodes increase, the computing performance becomes better. However, at the stage of solving equation groups, the computing performance is not ideal and should be improved in the future.

Cloud computing Hadoop MapReduce Linear finite element Spatial truss Parallel computing

2015-12-03。林海銘，碩士，主研領(lǐng)域：計算機仿真，大規(guī)模計算。

TP3

A

10.3969/j.issn.1000-386x.2017.03.004