林 海 銘

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

?

基于Hadoop MapReduce的大規(guī)模雷電電磁傳播數(shù)值仿真

林 海 銘

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

面對大規(guī)模雷電電磁問題，單機計算不能達到完全解決問題的程度，可以考慮利用新興云計算技術(shù)來解決。提出基于Hadoop MapReduce框架的域分解時域有限差分并行算法，在6節(jié)點的Hadoop實驗室集群上，對上海浦東某地區(qū)發(fā)生的大規(guī)模雷電電磁傳播過程進行數(shù)值仿真，并測試不同計算子域所獲得的加速比。計算結(jié)果顯示，所提出的并行算法能有效地求解大規(guī)模雷電電磁傳播問題，且計算模型越大、計算節(jié)點越多，加速比也大，在設(shè)定的計算環(huán)境下，最大加速比為2.4，受硬盤空間限制，最大計算規(guī)模為1 368萬節(jié)點。

云計算 Hadoop MapReduce 雷電 有限差分法 并行計算

0 引 言

自2007年IBM正式提出云計算[1]的概念以來，許多學者、研究機構(gòu)和IT公司都從不同角度定義了云計算。云計算是以虛擬化技術(shù)為基礎(chǔ)，以網(wǎng)絡(luò)為載體，以用戶為主體，以IaaS、PaaS、SaaS服務(wù)為形式，整合大規(guī)模、可擴展的分布式資源進行協(xié)同工作的超級計算范式。云計算的基礎(chǔ)設(shè)施架構(gòu)在普通機器上，能夠無縫地擴展到包含數(shù)千個節(jié)點的大規(guī)模集群上，擴展性好，最大限度地利用廉價計算資源。云計算通過普通機器的冗余獲得高可用性，能夠容忍節(jié)點失效。同時，用戶通過即付即用方式使用云中心資源，可以避免在基礎(chǔ)設(shè)備上的投資，也脫離技術(shù)與部署的復雜性。

云計算的興起，為科學計算提供了新的工具，基于云計算的科學計算稱為研究熱點。Jakovits等[2]在Hadoop MapReduce框架上實現(xiàn)基于Monte Carlo的線性方程組求解，并跟Hadoop CG和Twister CG進行比較，結(jié)果顯示Hadoop Monte Carlo的效率高于Hadoop CG，但低于Twister CG，同時隨著Markov鏈的增加，Monte Carlo不容易收斂。Xuan等[3]在Hadoop框架頂層加了包含Dataflow DAG、Controllers、Resource Manager等數(shù)據(jù)流層，形成適合科學工作流的數(shù)據(jù)流驅(qū)動云模型SciFlow，整合了分子動力學MD程序GROMACS和前向流采樣FFS算法，設(shè)計其基于數(shù)據(jù)流驅(qū)動的MapReduce實現(xiàn)。Yang等[4]提出基于MapReduce的圖形算法Mapper-side Schimmy來實現(xiàn)神經(jīng)網(wǎng)絡(luò)仿真，用包含10萬個神經(jīng)元23億個邊的算例進行驗證，此算法能提高性能64%，但MapReduce框架不適合迭代算法，在Hadoop頂層增加了適用于大規(guī)模圖形處理的框架Giraph，性能提升了60%。Dalman等[5]在Amazon云平臺上無縫集成了Hadoop MapReduce框架和生物醫(yī)學工程的C-MFA框架，在Hadoop streaming接口上獲得加速比17(64核)，通過自定義數(shù)據(jù)類型和參數(shù)調(diào)優(yōu)，加速比提高到48。Gu等[6]提出科學工作流SWF建模方法和XML數(shù)據(jù)管理模型XML-DMM，其中SWF建模負責數(shù)據(jù)的處理，XML-DMM確保了云環(huán)境中數(shù)據(jù)的一致性和分布式資源的利用率，并設(shè)計了Rollback、Break-Point和Release Resource三種動態(tài)執(zhí)行機制來提高SWF的執(zhí)行效率，在Hadoop平臺上實現(xiàn)，并用計算大海表面溫度SST的例子進行驗證。Vijayakumar等[7]使用FASTA算法提出了生物信息學中的基因序列比對優(yōu)化方法，并在Hadoop和Greenplum MPP 數(shù)據(jù)庫組合的平臺上實現(xiàn)，實驗結(jié)果表明這種組合平臺上的計算時間比Hadoop+PostgreSQL平均減少了48%。

空間雷電電磁傳播問題具有計算/數(shù)據(jù)密集型的特性，隨著計算規(guī)模和精度的不斷提高，單機即使是高性能計算機已經(jīng)不能完全求解問題，本文在云計算環(huán)境下實現(xiàn)有限差分法求解大規(guī)模電磁傳播問題，具有重要的探索意義和實用價值。

1 Hadoop平臺

Hadoop是一個應用最為廣泛的開源MapReduce實現(xiàn)，通過廉價PC組建成具有強大數(shù)據(jù)處理能力的計算平臺，每個PC提供本地計算和存儲，通過高度抽象的編程模型實現(xiàn)分布式計算。Hadoop通過數(shù)據(jù)復制和局部重新計算實現(xiàn)錯誤容忍和失效恢復，而不是通過硬件的高可靠性，既能解決傳統(tǒng)高性能計算中容錯性不足的問題，也降低了基礎(chǔ)設(shè)備的購置、維護費用。Hadoop平臺包含HDFS、MapReduce、YARN、HBase、Hive、Pig等模塊，用于計算的Hadoop平臺主要包括分布式文件系統(tǒng)HDFS和并行計算框架MapReduce兩部分。

1.1 HDFS

Hadoop的分布式文件系統(tǒng)HDFS采用Master/Slaver架構(gòu)，典型的HDFS由一個NameNode和一定數(shù)目的DataNode組成。其中，NameNode是中心服務(wù)器，負責管理文件系統(tǒng)的Namespace并接受客戶端對文件的訪問；DataNode是數(shù)據(jù)存儲節(jié)點，在Namenode的指揮下進行數(shù)據(jù)塊的創(chuàng)建、刪除和復制[8]。HDFS通過硬件的冗余和數(shù)據(jù)塊的備份實現(xiàn)高容錯性，通過流式訪問實現(xiàn)高數(shù)據(jù)吞吐量，提供高傳輸帶寬實現(xiàn)海量數(shù)據(jù)管理，要求每個時刻只能一個用戶寫入數(shù)據(jù)，實現(xiàn)數(shù)據(jù)的一致性。

1.2 MapReduce

MapReduce[8]是當前最為流行的分布式編程模型，用戶只要根據(jù)自身需求實現(xiàn)Mapper和Reducer接口，就能自動并行化自己的應用程序。Mapper接口通過map()函數(shù)對輸入進行映射操作。在各個工作節(jié)點上，map()函數(shù)獲得一串由主節(jié)點分配的鍵值對(key/value)作為輸入。對于一個key/value，在map()中進行相應的操作，可以產(chǎn)生一串key/value作為輸出，這個過程的可以表示為map :: (key1; value1) to list(key2; value2)。Reducer接口通過reduce()函數(shù)對輸入進行規(guī)約。reducer()函數(shù)獲得一串key相同的鍵值對作為輸入，規(guī)約成新的值作為輸出，形式為reduce::(key2;list(value2)) to list(value3)。

2 FDTD并行化

2.1 Yee’s FDTD

在各向同性、時間無關(guān)的電磁空間中，電磁傳播過程可用以下矢量方程表示：

(1)

(2)

其中，E為電場強度矢量，H為磁場強度矢量，ε為介電常數(shù)，μ為磁導率，σ為電導率。

通過Yee晶格把計算空間沿3個軸向劃分成長方體小網(wǎng)格，將計算空間中的連續(xù)變量離散化，節(jié)點(i,j,k)處的電磁場分量如圖1所示。

圖1 Yee晶格

通過中心差分法并假設(shè)網(wǎng)格為方體(Δx=Δy=Δz=δ)，式(1)和式(2)可離散為：

(3)

(4)

(5)

(6)

(7)

(8)

2.2 Mur邊界條件

在一長方體(0

(9)

(10)

圖2中，P0為邊界節(jié)點，Q0為P0相對的節(jié)點，P1、P2、P3、P4是P0相鄰的節(jié)點，Q1、Q2、Q3、Q4為Q0相鄰的節(jié)點，假設(shè)網(wǎng)格單元長度為δ，式(9)和式(10)可離散為：

(11)

fn(P3)+fn(P4)+fn(Q1)+fn(Q2)+fn(Q3)+fn(Q4)]

(12)

圖2 節(jié)點示意圖

為保證FDTD的計算穩(wěn)定性，對截斷邊界上網(wǎng)格節(jié)點(圖3所示)做如下處理，可以避免對棱邊及角頂點處網(wǎng)格節(jié)點(圖中空心圓節(jié)點)的計算：與長方體棱邊相鄰的節(jié)點(圖中方形節(jié)點)采用式(11)近似計算；內(nèi)部節(jié)點(圖中實心圓節(jié)點)則采用式(12)近似計算。

圖3 邊界節(jié)點處理示意圖

2.3 DD-FDTD

根據(jù)迭代方程式(3)至式(8)，得到FDTD算法的數(shù)據(jù)相關(guān)性圖(圖4)。每一網(wǎng)格點上的電磁計算都與相鄰網(wǎng)格點存在數(shù)據(jù)相關(guān)聯(lián)，但當把一個完整的計算域劃分為若干個子區(qū)域時，子域邊界處網(wǎng)格節(jié)點上的電磁計算用到臨域邊界處網(wǎng)格節(jié)點上的切向場量，存在數(shù)據(jù)依賴性，而子域內(nèi)部網(wǎng)格節(jié)點上的電磁計算所需的數(shù)據(jù)都在本域內(nèi)，與其他子域不存在數(shù)據(jù)依賴性，可以獨立完成計算。

圖4 數(shù)據(jù)相關(guān)性

DD-FDTD的基本原理如圖5所示。在計算第N個時間步時，首先計算電場分量，根據(jù)式(8)，計算子區(qū)域1內(nèi)部網(wǎng)格節(jié)點的電場分量Ez所需的磁場分量Hx、Hy全在該區(qū)域中，能獨立完成。但計算子域邊界處網(wǎng)格節(jié)點的電場分量Ez所需的磁場分量Hy位于臨域2邊界處的網(wǎng)格節(jié)點上，開始計算Ez之前必須將上一時間步的磁場分量Hy從臨域2傳遞到1中。計算磁場分量情況類似。

圖5 DD-FDTD的基本原理

3 基于MapReduce的DD-FDTD

計算前，對計算網(wǎng)格進行分區(qū)，對計算節(jié)點進行編號，標記分塊邊界節(jié)點(不同于物理邊界，物理邊界通過節(jié)點編號判斷)，初始化電/磁場6個計算分量。網(wǎng)格節(jié)點信息存儲到輸入文件中，主要包括塊編號、邊界標記、節(jié)點編號、電磁場分量初始值等。

根據(jù)上述的FDTD算法基本理論及其域分解并行化技術(shù)，設(shè)計一個類DD_FDTDSolver實現(xiàn)基于MapReduce的DD-FDTD并行化。在DD-FDTD中，各個分塊內(nèi)部的計算都是獨立的，只有邊界節(jié)點上的計算需要用到相鄰分塊中的數(shù)據(jù)。因此，MapReduce過程只需要Mapper過程，每個Mapper負責一個分塊的計算，不需要Combiner和Reducer對Mapper的結(jié)果進行歸約。

在Mapper中，輸入文件為上述的格式化文件，在Job的配置中用Hadoop的NLineInputFormat類設(shè)置輸入格式，master將N行數(shù)據(jù)分配給一個Mapper，N的大小由屬性mapreduce.input.lineinputformat.linespermap控制。在此N設(shè)置為每個分塊里的數(shù)據(jù)量，從而實現(xiàn)每個Mapper獨立計算一個分塊，Mapper數(shù)為FDTD域分解的分塊數(shù)。Mapper將所分配到的數(shù)據(jù)塊以鍵值對的形式傳給map()函數(shù)，作為其輸入，其中“鍵”為該行數(shù)據(jù)在整個輸入數(shù)據(jù)文件中的偏移量，“值”為一整行數(shù)據(jù)，即為一個網(wǎng)格節(jié)點信息數(shù)據(jù)。在每個迭代步中，每個節(jié)點上的電/磁場分量的計算所需的數(shù)據(jù)都是前邊迭代步的計算結(jié)果。因此可以在setup()函數(shù)中，根據(jù)塊編號從HDFS上的文件讀取相應的相鄰分塊邊界節(jié)點的結(jié)果數(shù)據(jù)和本塊內(nèi)部節(jié)點的結(jié)果數(shù)據(jù)，分別存儲在數(shù)組A和數(shù)組B中。在map()函數(shù)中根據(jù)節(jié)點編號，判斷是節(jié)點類別，若為物理邊界節(jié)點，則利用式(11)和式(12)進行計算；若為分塊邊界節(jié)點，則從數(shù)組A獲取臨域邊界節(jié)點數(shù)據(jù)根據(jù)迭代式(3)至式(8)進行計算。否則，從數(shù)組B中獲取本塊節(jié)點數(shù)據(jù)按照迭代式(3)至式(8)進行計算。最后更新“值”中的6個分量值，輸出到HDFS上相應的文件中作為下一迭代步的輸入數(shù)據(jù)。

Hadoop Job的基本配置參數(shù)可以采用系統(tǒng)默認的，而關(guān)鍵配置參數(shù)往往是通過啟動命令進行傳遞給Job啟動函數(shù)，在此需要通過啟動命令配置的關(guān)鍵參數(shù)包括：輸入數(shù)據(jù)文件路徑、輸出結(jié)果路徑、行數(shù)Nline和分塊數(shù)Nsplit?；贛apReduce框架DD-FDTD并行實現(xiàn)的算法流程如圖6所示。

圖6 基于MapReduce的DD-FDTD流程圖

4 算例驗證

4.1 雷電電磁傳播

以上海浦東某地區(qū)發(fā)生的雷電電磁傳播過程為例，驗證上述所提的算法。忽略小型建筑物，只對大型建筑物及長方體空間(1500 m×1500 m×750 m)內(nèi)的空氣介質(zhì)進行建模，網(wǎng)格模型如圖7所示(只顯示建筑物的網(wǎng)格)。

圖7 網(wǎng)格模型

將雷電流近似為線電流源進行加載，要在電磁場中添加線電流源，只需將下邊子項加到式(8)的右邊。

其中，I為線電流隨時間變化的表達式，is，js為雷電流所在節(jié)點在x、y方向上的坐標。

本文采用IEEE推薦的8/20 μs雙指函數(shù)波形雷電流模型，形式為：

In(is,js,k)=I0(e-α(Δt·n-kδ/v)-e-β(Δt·n-kδ/v))

其中，I0=23.3 kA，α=7.714×104，β=2.489×105，v=1.3×108m/s。雷電電磁場的頻率范圍就要集中在102～106Hz，計算時將頻率設(shè)置為1 MHz，波長300 m，取Yee晶格大小δ=10 m，足以滿足穩(wěn)定性條件。計算域為1500 m×1500 m×750 m的長方體，由空氣和建筑物構(gòu)成，其中，空氣的電磁參數(shù)為εr1=1、μr1=1、σ=0；假設(shè)建筑物各項同性，其電磁參數(shù)為εr2=6.0、μr2=1.13、σ=0.05 S/m。雷電流位于z=0平面的中心，在10 μs時達到峰值，此時x方向的電/磁場的云圖如圖8、圖9(兩截面分別在z=0 m和z=375 m處)和圖10、圖11(兩截面分別在z=150 m和z=600 m處)所示。從截面圖可以看出建筑物貫穿電磁場，引起電磁場傳播不均勻，對電磁場起一定的屏蔽作用。

圖8 Ex云圖

圖9 Hx云圖

圖10 Ex云圖

圖11 Hx云圖

4.2 加速比

用三種不同尺寸的網(wǎng)格離散化計算域，得到三種不同規(guī)模的網(wǎng)格模型，分別由21 375、1 710 000、13 680 000個節(jié)點構(gòu)成(受硬盤空間限制，不繼續(xù)加密)。采用MATLAB將網(wǎng)格模型分為數(shù)目不等的計算子域并生成輸入文件。在Hadoop實驗集群(配置的最大map數(shù)為12)上測試其加速比，測試結(jié)果如圖12所示。對于每一個網(wǎng)格模型，加速比隨map數(shù)的增加而增加，但曲線的斜率隨map數(shù)的增加逐漸減小，即加速比增長逐漸減緩。對于不同網(wǎng)格模型，網(wǎng)格模型的規(guī)模越大，獲得更好的加速效率。對于同一個網(wǎng)格模型，map數(shù)的增加意味著Hadoop集群中更多的worker分配到計算任務(wù)參與計算，從而使得整體計算的并行度增大，獲得更好的加速效果。但節(jié)點增加會引起數(shù)據(jù)讀寫和節(jié)點之間通信等方面的性能開銷增加，而導致加速比的增長率變小。對于小模型，數(shù)據(jù)讀寫和節(jié)點之間通信等方面的開銷所占的比重大于計算的開銷，計算節(jié)點的增加提高了計算并行度，加速比增加，但節(jié)點處于未飽和狀態(tài)并且未飽和狀態(tài)越來越嚴重，增長速度下降比較快。對于大模型，數(shù)據(jù)讀寫和節(jié)點通信方面的開銷比小模型的大，但其屬于計算密集型，即計算方面的開銷占絕大部分，計算模型規(guī)模的增大使得計算的開銷在整體開銷中所占的比重也增大，計算節(jié)點的增加加大了計算并行度，加速比增加，計算節(jié)點的狀態(tài)隨節(jié)點數(shù)的增加從超飽和狀態(tài)向飽和狀態(tài)、未飽和狀態(tài)轉(zhuǎn)變，加速比的增長速度逐漸變小。

圖12 不同map任務(wù)下的加速比

5 結(jié) 語

本文設(shè)計了合適的數(shù)據(jù)結(jié)構(gòu)，提出了基于MapReduce框架的DD-FDTD并行算法，并給出了詳細的設(shè)計步驟和程序執(zhí)行流程，最后通過上海某地區(qū)發(fā)生的雷電傳播過程為數(shù)值實例，驗證算法的并行性能。結(jié)果表明加速比隨著計算節(jié)點的增加而增加，但當計算節(jié)點到達一定數(shù)量時，集群處于未飽和狀態(tài)，加速比的增長速度下降；當集群規(guī)模與求解問題的計算量匹配時，集群處于飽和狀態(tài)，系統(tǒng)的計算性能最佳；在本文所配置的6節(jié)點集群環(huán)境下，最大計算規(guī)模為1368萬節(jié)點，最大的加速比為2.4。

[1] Armbrust Michael,Fox Armando,Griffith Rean,et al.A view of Cloud Computing[J].Commun.ACM,2010,53(4):50-58.

[2] Pelle Jakovits,Ilja Kromonov,Satish Narayana Srirama.Monte Carlo Linear System Solver using MapReduce[C]//Proceedings of 2011 Fourth IEEE International Conference on Utility and Cloud Computing, Victoria, December 5-8, 2011.New York: IEEE,2011.

[3] Xuan Pengfei,Zheng Yueli,Sarupria Sapna,et al.SciFlow:A Dataflow-driven Model Architecture for Scientific Computing Using Hadoop[C]//Proceedings of 2013 IEEE International Conference on Big Data, Silicon Valley, October 6-9, 2013.New York:IEEE,2013.

[4] Yang Shuo,Spielman N D,Jackson J C,et al.Large-scale Neural Modeling in MapReduce and Giraph[C]//Proceedings of 2014 IEEE International Conference on Electro/Information Technology, Milwaukee,June 5-7, 2014.New York: IEEE,2014.

[5] Tolga Dalmana,Tim D?rnemannb,Ernst Juhnke,et al.Cloud MapReduce for Monte Carlo Bootstrap Applied to Metabolic Flux Analysis[J].Future Generation Computer Systems,2013,29(2):582-590.

[6] Gu R,Wu S,Dong H,et al.A Modeling Method of Scientific Workflow Based on Cloud Environment[C]//Proceedings of 2012 IEEE/ACIS 11th International Conference on Computer and Information Science,Shanghai, May 30-June 1, 2012.New York: IEEE,2012.

[7] Vijayakumar S,Bhargavi A,Praseeda U,et al.Optimizing Sequence Alignment in Cloud Using Hadoop and MPP Database[C]//Proceedings of 2012 IEEE 5th International Conference on Cloud Computing, Honolulu, June 24-29,2012.New York:IEEE,2012.

[8] Lam Chuck.Hadoop in action[M].New York,America: Manning Publications Co.,2010.

NUMERICAL SIMULATION OF LARGE-SCALE LIGHTNING ELECTROMAGNETIC PROPAGATION BASED ON HADOOP MAPREDUCE

Lin Haiming

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

Single computer cannot reach the extent of completely solving the problem of large-scale lightning electromagnetic propagation simulation, but it may consider to use emerging cloud computation technology as the solution. This paper proposes a Hadoop MapReduce frame-based parallel algorithm of domain decomposition finite difference time domain (DD-FDTD). On a 6-nodes Hadoop laboratory cluster we carried out numerical simulation on the large-scale lightning electromagnetic propagation process occurred in an area in Pudong District, Shanghai, and tested the speedup ratios obtained in different computational sub-domains. It is shown by computational results that the proposed parallel algorithm can calculate the electromagnetic propagation of large-scale lightning effectively, and the speedup ratio increases along with the augment in computation model and the number of computational nodes, and the maximum speedup ratio is about 2.4 under the computation environment introduced in the paper. With the limitation of the capability of hard disk, the maximum computation scale is 13.68 million nodes.

Cloud computing Hadoop MapReduce Lightning FDTD Parallel computing

2015-09-07。林海銘，助理工程師，主研領(lǐng)域：計算機仿真，大規(guī)模計算。

TP3

A

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