基于Hadoop MapReduce的大規模雷電電磁傳播數值仿真

林 海 銘

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

?

基于Hadoop MapReduce的大規模雷電電磁傳播數值仿真

林 海 銘

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

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

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

0 引 言

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

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

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

1 Hadoop平臺

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

1.1 HDFS

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

1.2 MapReduce

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

2 FDTD并行化

2.1 Yee’s FDTD

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

(1)

(2)

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

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

圖1 Yee晶格

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

(3)

(4)

(5)

(6)

(7)

(8)

2.2 Mur邊界條件

在一長方體(0

(9)

(10)

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

(11)

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

(12)

圖2 節點示意圖

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

圖3 邊界節點處理示意圖

2.3 DD-FDTD

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

圖4 數據相關性

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

圖5 DD-FDTD的基本原理

3 基于MapReduce的DD-FDTD

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

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

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

Hadoop Job的基本配置參數可以采用系統默認的，而關鍵配置參數往往是通過啟動命令進行傳遞給Job啟動函數，在此需要通過啟動命令配置的關鍵參數包括：輸入數據文件路徑、輸出結果路徑、行數Nline和分塊數Nsplit。基于MapReduce框架DD-FDTD并行實現的算法流程如圖6所示。

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

4 算例驗證

4.1 雷電電磁傳播

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

圖7 網格模型

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

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

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

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，計算時將頻率設置為1 MHz，波長300 m，取Yee晶格大小δ=10 m，足以滿足穩定性條件。計算域為1500 m×1500 m×750 m的長方體，由空氣和建筑物構成，其中，空氣的電磁參數為εr1=1、μr1=1、σ=0；假設建筑物各項同性，其電磁參數為ε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 加速比

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

圖12 不同map任務下的加速比

5 結 語

本文設計了合適的數據結構，提出了基于MapReduce框架的DD-FDTD并行算法，并給出了詳細的設計步驟和程序執行流程，最后通過上海某地區發生的雷電傳播過程為數值實例，驗證算法的并行性能。結果表明加速比隨著計算節點的增加而增加，但當計算節點到達一定數量時，集群處于未飽和狀態，加速比的增長速度下降；當集群規模與求解問題的計算量匹配時，集群處于飽和狀態，系統的計算性能最佳；在本文所配置的6節點集群環境下，最大計算規模為1368萬節點，最大的加速比為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。林海銘，助理工程師，主研領域：計算機仿真，大規模計算。

TP3

A

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