短程力分子模擬在Hadoop上的實現(xiàn)及優(yōu)化＊

焦善飛，何 晨，豆育升，唐 紅

（1.重慶郵電大學(xué)計算機科學(xué)與技術(shù)學(xué)院，重慶 400065）；2.重慶郵電大學(xué)高性能計算與應(yīng)用研究所，重慶 400065）

1 引言

Hadoop是目前比較流行的開源分布式計算框架，它大大簡化了并行程序的設(shè)計和開發(fā)，使開發(fā)者集中精力分析復(fù)雜的應(yīng)用，擺脫并行化過程中的各種困擾。傳統(tǒng)的分子動力學(xué)模擬研究一般是基于MPI、OpenMP 或Condor網(wǎng)格平臺，在可靠性、可擴展性、容錯性和動態(tài)負載均衡方面均有所欠缺。在傳統(tǒng)平臺上，個別節(jié)點死機時有發(fā)生，所有運行的作業(yè)都將會受到影響，平臺本身缺少自動重新調(diào)度子任務(wù)的機制，無法在單步內(nèi)對每個計算節(jié)點容錯，也不容易在各節(jié)點上實現(xiàn)動態(tài)負載均衡，以充分利用有限的硬件資源。因此，在Hadoop云計算平臺上運行分子模擬程序，具有克服傳統(tǒng)平臺固有的缺陷、節(jié)省各種軟硬件投資和縮短模擬時間等意義。

本文在深入研究Hadoop框架及其相關(guān)原理的基礎(chǔ)上，結(jié)合計算化學(xué)相關(guān)理論，將需要大量計算的短程力有效的分子動力學(xué)模擬應(yīng)用到這種新型平臺上來。本文在使用分子動力學(xué)模擬常用并行算法，即原子分解法的基礎(chǔ)上，提出了三種可行方案并主要實現(xiàn)和測試了其中的“讀寫HDFS 同步法”，克服了Hadoop實現(xiàn)科學(xué)計算類應(yīng)用的難點——全局通信、同步方式和快速迭代，達到優(yōu)化模擬、克服傳統(tǒng)平臺的缺點和提高硬件資源利用率等目的，豐富了Hadoop 在科學(xué)計算領(lǐng)域中的應(yīng)用。

2 云計算和Hadoop

云計算［1］是并行計算、分布式計算、網(wǎng)格計算和虛擬化等技術(shù)的綜合發(fā)展和商業(yè)實現(xiàn)，它將大規(guī)模的計算任務(wù)分解成多個子任務(wù)并行運行在大量廉價PC或中低端服務(wù)器構(gòu)成的集群上，具有超大規(guī)模、高可靠性、可伸縮性、極其廉價、用戶按需使用虛擬化資源池等優(yōu)點。

Hadoop作為一個分布式系統(tǒng)基礎(chǔ)架構(gòu)，克隆了Google運行系統(tǒng)的主要框架，在底層可以實現(xiàn)對集群的管理和控制，在上層可以快速構(gòu)建企業(yè)級應(yīng)用。它為應(yīng)用程序提供了一系列接口，包括分布式計算編程模型MapReduce、分布式文件系統(tǒng)HDFS、分布式數(shù)據(jù)庫Hbase、分布式鎖服務(wù)Zoo－Keeper等組件。

Hadoop的主從架構(gòu)如圖1 所示，各slave通過網(wǎng)絡(luò)不斷地向master發(fā)送heartbeat，獲取所要執(zhí)行的task 或其它操作命令。數(shù)據(jù)按塊（默認64MB）存儲在各個DataNode上，NameNode保存元數(shù)據(jù)并向client提供查詢服務(wù)。JobTracker接受client提交的作業(yè)后將作業(yè)劃分為多個任務(wù)（task），并分發(fā)到各個TaskTracker的mapslot／reduceslot（如圖1 中mapslot等，表示任務(wù)槽）上執(zhí)行，最后進入reduce 階段輸出執(zhí)行結(jié)果到HDFS。

Figure 1 Structure model of Hadoop圖1 Hadoop的主從架構(gòu)模型［2］

Hadoop特別適合高吞吐量、一次寫入多次讀取類應(yīng)用，雅虎、淘寶和百度等互聯(lián)網(wǎng)公司都有多個上千節(jié)點規(guī)模的Hadoop集群，用于日志分析、數(shù)據(jù)挖掘和搜索引擎等具體應(yīng)用，每天運行數(shù)萬個MapReduce作業(yè)，處理PB 級的數(shù)據(jù)。但是，在科學(xué)計算方面的應(yīng)用還不夠廣泛，尤其是計算化學(xué)中的分子模擬領(lǐng)域，目前在國內(nèi)外極少有人嘗試。

3 分子動力學(xué)模擬的概念和原理

分子動力學(xué)MD（Molecular Dynamics）模擬是一種在原子級模擬固體、液體和分子性質(zhì)的常用的計算機模擬方法，廣泛應(yīng)用于物理學(xué)、材料科學(xué)和生命科學(xué)等領(lǐng)域［3］。它主要是通過求解粒子的運動方程，獲得其運動軌跡并計算各種宏觀物理量。

在模擬過程中需要大量的計算，普通服務(wù)器早已不能滿足要求，大型機［4］、并行向量機又非常昂貴。使用云計算服務(wù)商提供的彈性云計算等方案是比較好的選擇，可省去大筆的購置和運維費用，僅需花較少的機時費就可在很短的時間內(nèi)獲得模擬結(jié)果，縮短科研周期。因此，將分子動力學(xué)模擬這類應(yīng)用從傳統(tǒng)的并行平臺遷移到云計算平臺上，有著較高的研究意義和實用價值。

下面將分別介紹MD 串行和傳統(tǒng)并行算法的基本原理和步驟。

3.1 串行算法

典型的MD 串行算法步驟如圖2所示。

Figure 2 Steps of serial MD圖2 串行MD 的步驟

模擬體系中每個粒子的運動遵守牛頓運動方程：

本文使用有限差分法中最常用的verlet－velocity法求解粒子的運動方程：

在計算中需要知道上一個時刻的位置、速度和力，首先由方程（5）計算新的位置，然后計算新的力F（t＋dt），再由方程（6）計算新時刻的速度。最后，運用統(tǒng)計物理的方法來計算徑向分布函數(shù)、總動能、總能量、熱傳導(dǎo)系數(shù)等，達到與實驗對照檢驗，以及指導(dǎo)后續(xù)實驗研究和預(yù)測物質(zhì)性質(zhì)等目的［6］。

3.2 并行方案

在模擬過程中，分子間作用力的計算最為耗時，占整體模擬時間的80%左右。有三種并行算法［7］可計算分子間作用力：力分解法、空間分解法和原子分解法。由于Hadoop系統(tǒng)中各計算節(jié)點通信時額外開銷比較大，不宜頻繁通信。而前兩種方法都需要頻繁的節(jié)點間通信，并且并行算法本身也不易負載平衡；原子分解法容易實現(xiàn)，可以實現(xiàn)負載均衡（忙節(jié)點少分原子，閑節(jié)點多分原子）。因此，本文的程序MRmd采用原子分解法。

傳統(tǒng)的MD 并行化是基于MPI、OpenMP［8］或MPI＋OpenMP［9］兩級并行的并行機制。MPI是跨節(jié)點、消息傳遞型、進程級并行的編程模型，比較擅長計算密集型應(yīng)用。OpenMP 是在單機多核平臺上、線程級并行的編程模型，由于四路以上服務(wù)器價格昂貴，總線和IO 帶寬有限，OpenMP 的擴展能力不強。

本文在Hadoop平臺上使用MapReduce開源分布式框架來解決MD 這一科學(xué)計算問題。采用Hadoop實現(xiàn)MD 相比傳統(tǒng)方案有以下優(yōu)勢：

（1）較高的容錯性。各節(jié)點平等地訪問HDFS，每個計算節(jié)點（TaskTracker）同時又是數(shù)據(jù)節(jié)點（DataNode）。主節(jié)點會把失敗的子任務(wù)重新調(diào)度到另一個節(jié)點重新執(zhí)行，這樣就減少浪費寶貴的硬件資源。此外，分布式文件系統(tǒng)的副本策略保證每個數(shù)據(jù)塊都有若干個副本，個別磁盤損壞對整體系統(tǒng)沒有影響。而MPI在底層上缺少這種分布式文件系統(tǒng)，一旦中途某個節(jié)點宕機，只能將整個作業(yè)重新提交；另一方面，在MPI上通常每五個時間步保存一次運行結(jié)果，而Hadoop上可以做到保存每一時間步的模擬結(jié)果。

（2）較高的資源利用率。每個TaskTracker有多個mapslot或reduceslot，可并行運行多個子任務(wù)，最大限度地發(fā)揮SMP 和CMP 體系結(jié)構(gòu)的優(yōu)勢，提高資源利用率；另一方面，也不存在MPI上常見的死鎖問題。

（3）較強的伸縮性。傳統(tǒng)的并行框架伸縮性有限，隨著計算規(guī)模不斷擴大或數(shù)據(jù)的指數(shù)級上升而出現(xiàn)各種瓶頸。而在Hadoop中只需簡單地增加節(jié)點就能輕松應(yīng)對新的業(yè)務(wù)需求。

綜上，Hadoop在科學(xué)計算類應(yīng)用和海量數(shù)據(jù)處理方面都表現(xiàn)出了較好的優(yōu)勢。

4 設(shè)計與實現(xiàn)

4.1 難點

常規(guī)的Hadoop 應(yīng)用程序執(zhí)行流程是：每個maptask（某時刻在mapslot上執(zhí)行的map 任務(wù)）從HDFS取一部分數(shù)據(jù)作為輸入，把每條記錄以鍵值對的形式處理后送到reduce進行規(guī)約，再寫回HDFS，中間產(chǎn)生的臨時數(shù)據(jù)是先寫到本地硬盤再通過網(wǎng)絡(luò)傳輸給reducetask（某時刻在reduceslot上執(zhí)行的reduce任務(wù)）。在Hadoop框架中，reduce階段是實現(xiàn)節(jié)點通信的惟一途徑。顯然，對MD 這種數(shù)據(jù)相關(guān)比較嚴重并且需要很多次迭代的應(yīng)用來說，常規(guī)執(zhí)行流程不能滿足要求，下一時間步需要上一時間步的全局位置信息。

在Hadoop平臺實現(xiàn)MD 的主要困難體現(xiàn)在全局通信、同步方法和快速迭代等方面。當(dāng)然，在MPI平臺上也存在編程困難、通信延遲大、負載不平衡和同步耗時之類的問題。

4.2 解決方案

目前解決方案有：

（1）每個Job計算一個時間步，由Distributed－Cache將上一時間步的全局位置信息分發(fā)到各節(jié)點的內(nèi)存中，maptask 負責(zé)計算，reducetask 負責(zé)匯總?cè)值男挛恢眯畔ⅲ缓笾匦聠右粋€Job，再進行下一步分發(fā)、計算和匯總。這種方法可以用來進行迭代次數(shù)不多的模擬，每次迭代要占用大量的作業(yè)初始化時間［10］。限于篇幅，本文對該方案的實現(xiàn)和測試不做詳細介紹。

（2）讀寫HDFS同步法。各計算節(jié)點平等地訪問HDFS，從HDFS 取上一時間步的全局位置信息，把計算好的新位置信息寫入到HDFS 供下一時間步的計算節(jié)點讀取，這是一個很好的實現(xiàn)全局通信的途徑。但是，HDFS有自身的缺點——不支持文件的追加，HDFS作為Google GFS的簡化版和開源實現(xiàn)，去掉了GFS最復(fù)雜的部分，即多個客戶端對同一文件的并發(fā)追加。程序使用的同步方式為阻塞式通信，直到最慢的節(jié)點的計算完成，才能進入下一輪計算。本文的程序MRmd正是采用了這一方案，在設(shè)計部分有詳細闡述。

（3）使用專門的節(jié)點負責(zé)同步和分發(fā)新的位置信息。此方法又可分為兩種：一種是在應(yīng)用程序上實現(xiàn)，選一個節(jié)點（比如taskid＝0所在節(jié)點）來收集各計算節(jié)點報告的新位置信息，并回復(fù)全局位置信息以進行下一時間步的模擬；另一種方法是在Hadoop系統(tǒng)底層實現(xiàn)，各計算節(jié)點使用消息傳遞機制來實現(xiàn)通信。理論上后者能進一步降低全局通信在總時間中的比重，但還未得到實驗證明。

4.3 設(shè)計

MapReduce采用key－value即鍵值對的形式序列化每條數(shù)據(jù)記錄［11］，maptask 中有一個用戶自定義的map（）函數(shù)，該函數(shù)接受一個鍵值對，處理后輸出。maptask 處理完split內(nèi)的鍵值對后，reducetask便開始復(fù)制其輸出，以進行shuffle、sort和reduce等工作［12］。

在圖3中各模塊的具體任務(wù)是：

（1）initialize：包括Java JVM 的啟動及初始化和為當(dāng)前 maptask 做的初始化工作，如取maptaskID、分得的原子號列表，申請內(nèi)存空間保存全局原子的三維坐標、速度和加速度等。

（2）read global：讀HDFS中指定的目錄下的所有文件，這些文件是由上步計算完成后寫入的，提取全局原子ID 及位置信息。

（3）force：對分得的原子號列表中的每一個原子，分別用verlet－velocity 差分和Lennard－Jones作用勢計算其新的位置信息。

（4）sync wait：把分得的原子列表中所有原子新位置信息寫到 HDFS 中以時間步序號和maptaskID 命名的文件上，進入同步等待階段，不斷檢查HDFS的目錄下本輪輸出文件是否齊全，若不齊全則說明仍有未完成的子任務(wù)，循環(huán)等待直到所有子任務(wù)都完成再進入下一時間步的計算。

（5）reduce phase：map phase完成后輸出一個鍵值對，該鍵值包括子任務(wù)ID、各部分耗時等信息，reduce phase對所有輸出匯總，并寫到HDFS，以便分析。

Figure 3 Flow of MRmd圖3 MRmd的執(zhí)行流程圖

在模擬結(jié)束后，啟用另一個Hadoop 程序MRmdEnergy來對所有時間步的位置信息生成統(tǒng)計信息，如每一時間步的溫度、動能、勢能、總能量、可供jmol軟件導(dǎo)入演示動畫用的坐標文件和每個子任務(wù)的各部分耗時情況。比如maptask0取1～100時間步的所有位置信息，計算其各步的統(tǒng)計信息。為了保證兩個reduce phase輸出都按時間步有序，設(shè)計了特殊的key 并重寫了Partitioner－Class。

5 測試與分析

根據(jù)Amdahl定律，加速比的定義為：

由Amdahl公式知，加速比是有最大限度的，最大值取決于不可并行部分所占的比重。

本文的測試環(huán)境為：1個主節(jié)點，17個計算節(jié)點，配置均為Intel Q6600＠2.4GHz四核CPU，8GB內(nèi)存，1 500GB 硬盤，百兆網(wǎng)絡(luò)。每個計算節(jié)點配置4 個mapslot，即最多可同時執(zhí)行4 個maptask。

經(jīng)典的分子動力學(xué)模擬在研究階段常選用液態(tài)氬的分子運動作為研究對象。當(dāng)氬原子數(shù)分別為36 000、60 000和108 000，模擬200步，分別使用maps個子任務(wù)對該體系進行測試，測得的加速比（對比MPI＋OpenMP混合并行）如圖4所示。從圖4中可看出，當(dāng)原子數(shù)為36 000時，Hadoop平臺的性能稍遜于傳統(tǒng)并行平臺，具體原因為上文中所指出的與HDFS通信開銷大有關(guān)。同步時間、IO 時間和各種附加開銷都是不可并行的，即使再增加節(jié)點數(shù)，加速比也不會有大幅提高。當(dāng)模擬體系增加到60 000和108 000時，Hadoop表現(xiàn)出了一定優(yōu)勢，在本文實驗結(jié)果中模擬時間縮短5%。隨模擬原子增加，該優(yōu)勢會逐漸凸顯，輸出文件中模擬體系的總能量隨時間變化在十萬分位守恒，說明了模擬程序在可接受誤差范圍內(nèi)的準確性。

Figure 4 Speedup圖4 加速比

當(dāng)原子數(shù)為60 000時，隨maps 增加，在所有節(jié)點上各部分的平均時間比重如圖5所示。

Figure 5 Ratio of cost－time圖5 各部分時間比重

（1）其它開銷（other）：包括作業(yè)初始化1s，分發(fā)子任務(wù)到所有計算節(jié)點、啟動JVM、初始化各類參數(shù)3s，reduce 階 段 的shuffle、sort、reduce 占12s，總計16s左右，都是分布式系統(tǒng)框架內(nèi)必不可少的開銷。

（2）平均IO 時間（IO）：讀取HDFS得到全局位置信息、寫入新位置信息到HDFS 的總時間。由于HDFS是網(wǎng)絡(luò)上的分布式文件系統(tǒng)，IO 開銷＝網(wǎng)絡(luò)開銷＋磁盤開銷。

（3）平均同步等待時間（sync）：每一輪檢查各子任務(wù)是否都同步完成的等待時間。同步越來越耗時是因為每個節(jié)點有4個mapslot，可能占了1～4個不等的slot，造成節(jié)點負載有輕有重，以及受操作系統(tǒng)的進程調(diào)度機制、系統(tǒng)進程不斷變化和其他用戶進程的影響。

（4）平均計算時間（calculate）：所有子任務(wù)有效計算時間的平均值。

總體分析來看，第二種方案本身的通信方式以及集群中百兆網(wǎng)絡(luò)的低帶寬、高延遲，各節(jié)點負載不平衡造成同步等待比較耗時，是制約加速比繼續(xù)提高的重要原因。正因為讀寫HDFS法實現(xiàn)同步與通信的代價略高，適合用于節(jié)點間通信不太頻繁、通信量也不大的場合中，所以本程序在大體系模擬時表現(xiàn)更好。

進一步優(yōu)化程序以實現(xiàn)動態(tài)負載平衡，即每一輪都要對比上一輪各子任務(wù)的執(zhí)行時間，如果差值超過一定范圍，就把原子重新分配來調(diào)整任務(wù)粒度，把運算慢的節(jié)點上的原子減少，增加給運算快的節(jié)點。實驗表明，當(dāng)原子數(shù)大于36 000時，負載平衡所引入的額外開銷遠小于改進前的同步時間。

6 結(jié)束語

本文采用MapReduce分布式編程模型結(jié)合原子分解法這一并行算法實現(xiàn)并優(yōu)化了短程力下的分子動力學(xué)模擬的并行算法，通過增加適量的IO就可以應(yīng)對節(jié)點失效問題和實現(xiàn)全局通信，并在集群上以模擬不同體系大小的液態(tài)氬為例進行了多種測試，取得了較好的加速比、擴展性和容錯性。實驗證明，Hadoop并行平臺在應(yīng)用于大體系的分子模擬時，不僅在性能上優(yōu)于傳統(tǒng)并行平臺，而且彌補了傳統(tǒng)平臺在負載均衡和容錯等方面的不足。但是，Hadoop在科學(xué)計算應(yīng)用上仍然有很多挑戰(zhàn)和不足，比如節(jié)點間通信不便和實時性不強。為了解決這些問題，下一步將從Hadoop底層通信機制進行改進，探索一種適合此類科學(xué)計算的二次開發(fā)的并行框架。MD 方面將引入verlet近鄰表［13］降低算法復(fù)雜度，以加速模擬體系使其盡快達到平衡態(tài)。

［1］Weinhardt C，Anandasivam A，Blau B，et al.Cloud computing—a classification，business models，and research directions［J］.Business ＆ Information Systems Engineering，2009，1（1）：391－399.

［2］Liu Peng.Cloud computing［M］.Beijing：Publishing House of Electronics Industry，2010.（in Chinese）

［3］He Mu－jun，Guo Li，Yan Li.Research and analyze of commu－nication performance optimization in large－scale particle simulation system［J］.Computers and Applied Chemistry，2008，25（9）：1－3.（in Chinese）

［4］Zhang Bao－yin，Mo Ze－yao，Cao Xiao－lin.Performance optimization of a molecular dynamics code based on computational caching［J］.Computer Engineering ＆ Science，2009，31（11）：77－83.（in Chinese）

［5］Verlet L.Computer experiments on classical fluids thermodynamical properties of Lennard－Jones molecules［J］.Phys－Rev，1967，159（1）：98－103.

［6］Zhang Qin－yong，Jiang Hong－chuan，Liu Cui－h(huán)ua.Research of optimization and parallelization for molecular dynamics simulation［J］.Application Research of Computers，2005，22（8）：84－86.（in Chinese）

［7］Wang Bing，Shu Ji－wu，Zheng Wei－min.Hybird decomposition method in parallel molecular dynamics simulation based on SMP cluster architecture［J］.Tsinghua Science and Technology，2005，10（2）：183－188.

［8］Bai Ming－ze，Cheng Li，Dou Yu－sheng，et al.Performance analysis and improvement of parallel molecular dynamics algorithm base on OpenMP［J］.Journal of Computer Applications，2012，32（1）：163－166.（in Chinese）

［9］Li Hong－jian，Bai Ming－ze，Tang Hong，et al.Application of hybrid parallel algorithm for simulating photochemical reaction［J］.Journal of Computer Applications，2010，30（6）：1687－1689.（in Chinese）

［10］Chen He.Molecular dynamics simulation based on hadoop MapReduce［D］.University of Nebraska－Lincoln，2011.

［11］Dean J，Ghemawat S.MapReduce：Simplified data processing on large clusters［C］∥Proc of the 6th Symposium on operating Systems Design and Implentation，2008：1－12.

［12］White T.Hadoop：The definitive guide［M］.California：O’Reilly Media，2009.

［13］Shu Ji－wu，Wang Bing，Chen Min，et al.Optimization techniques for parallel force decomposition algorithm in molecular dynamic simulations［J］.Computer Physics Communications，2003，154（2）：101－103.

附中文參考文獻：

［2］劉鵬.云計算［M］.北京：電子工業(yè)出版社，2010.

［3］何牧君，郭力，嚴歷.大規(guī)模并行粒子模擬系統(tǒng)通信性能優(yōu)化研究與分析［J］.計算機與應(yīng)用化學(xué)，2008，25（9）：1－3.

［4］張寶印，莫則堯，曹小林.基于計算緩存方法的分子動力學(xué)程序性能優(yōu)化［J］.計算機工程與科學(xué)，2009，31（11）：77－83.

［6］張勤勇，蔣洪川，劉翠華.分子動力學(xué)模擬的優(yōu)化與并行研究［J］.計算機應(yīng)用研究，2005，22（8）：84－86.

［8］白明澤，程麗，豆育升，等.基于OpenMP的分子動力學(xué)并行算法的性能分析與優(yōu)化［J］.計算機應(yīng)用，2012，32（1）：163－166.

［9］李鴻健，白明澤，唐紅，等.混合并行技術(shù)在激光化學(xué)反應(yīng)模擬中的應(yīng)用［J］.計算機應(yīng)用，2010，30（6）：1687－1689.