基于MPI的網(wǎng)絡(luò)并行計(jì)算系統(tǒng)構(gòu)建及分析

張克非， 梅 栴， 趙振江

(沈陽(yáng)化工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧沈陽(yáng)110142)

現(xiàn)代計(jì)算技術(shù)顯著地促進(jìn)了科學(xué)計(jì)算的發(fā)展，高效的計(jì)算速度是目前科學(xué)計(jì)算中迫切需要解決的問(wèn)題.目前，在尖端科學(xué)研究領(lǐng)域諸如地震預(yù)報(bào)、氣候模擬和地質(zhì)研究中存在著巨大的計(jì)算任務(wù)［1］.如此龐大計(jì)算任務(wù)的解決依靠單處理器是無(wú)法實(shí)現(xiàn)的.在這些領(lǐng)域，迫切需要高效的計(jì)算方法.與此同時(shí)，隨著PC機(jī)性能的提高和網(wǎng)絡(luò)產(chǎn)品的更新?lián)Q代使一種新的計(jì)算形式——網(wǎng)絡(luò)并行計(jì)算應(yīng)運(yùn)而生.網(wǎng)絡(luò)并行計(jì)算是目前解決大規(guī)模計(jì)算問(wèn)題一個(gè)可行的有效途徑.本文主要闡述了基于MPI的并行計(jì)算系統(tǒng)搭建過(guò)程，并利用一個(gè)并行計(jì)算實(shí)例對(duì)此方法進(jìn)行驗(yàn)證，取得了良好結(jié)果.

1 網(wǎng)絡(luò)并行計(jì)算系統(tǒng)的體系結(jié)構(gòu)

網(wǎng)絡(luò)并行計(jì)算［2］是一種并行計(jì)算技術(shù)，它通過(guò)網(wǎng)絡(luò)連接多個(gè)計(jì)算機(jī)系統(tǒng)來(lái)實(shí)現(xiàn)高效的并行處理任務(wù).網(wǎng)絡(luò)并行計(jì)算能夠充分利用整個(gè)系統(tǒng)的資源進(jìn)行統(tǒng)一調(diào)度和協(xié)調(diào)處理，是目前并行計(jì)算研究領(lǐng)域的一個(gè)新的發(fā)展趨勢(shì).

1.1 硬件結(jié)構(gòu)

隨著網(wǎng)絡(luò)的普及和發(fā)展使得利用集群作為網(wǎng)絡(luò)并行計(jì)算的開(kāi)發(fā)平臺(tái)成為一種新趨勢(shì).集群是將一組計(jì)算機(jī)連接起來(lái)實(shí)現(xiàn)高效并行計(jì)算的系統(tǒng).集群中的各臺(tái)計(jì)算機(jī)之間聯(lián)系緊密，在某種程度上可將整個(gè)系統(tǒng)理解成一臺(tái)計(jì)算機(jī).集群中的計(jì)算節(jié)點(diǎn)可以是PC或工作站，每一個(gè)節(jié)點(diǎn)有獨(dú)立的內(nèi)存、輸入輸出設(shè)備和操作系統(tǒng)，節(jié)點(diǎn)之間通過(guò)高速局域網(wǎng)絡(luò)互相連接.對(duì)于用戶和應(yīng)用程序而言，集群如同一個(gè)單一的系統(tǒng).通過(guò)消息傳遞機(jī)制實(shí)現(xiàn)節(jié)點(diǎn)之間的互相通信，并提供上層的API接口方便用戶編程.集群以低廉的價(jià)格獲得強(qiáng)大的計(jì)算能力，是目前網(wǎng)絡(luò)并行計(jì)算領(lǐng)域的優(yōu)秀開(kāi)發(fā)平臺(tái).一個(gè)典型包含4個(gè)節(jié)點(diǎn)的集群的體系結(jié)構(gòu)［3］如圖1所示.

圖1 4個(gè)節(jié)點(diǎn)的集群的體系結(jié)構(gòu)圖Fig.1 The architecture diagram of cluster include four nodes

1.2 集群的互連網(wǎng)絡(luò)

網(wǎng)絡(luò)數(shù)據(jù)交換是影響網(wǎng)絡(luò)并行計(jì)算系統(tǒng)性能的瓶頸.因此，采用高速的網(wǎng)絡(luò)將會(huì)明顯提高系統(tǒng)性能.目前，集群一般通過(guò)ATM、Myrinet、以太網(wǎng)［4］等網(wǎng)絡(luò)進(jìn)行互連.

ATM是異步傳輸模式的縮寫，是以信元為基礎(chǔ)的一種分組交換和復(fù)用技術(shù).它具有高速數(shù)據(jù)傳輸率，適用于局域網(wǎng)和廣域網(wǎng)，但ATM網(wǎng)絡(luò)的硬件設(shè)備價(jià)格非常昂貴，限制了它的普及和應(yīng)用.

Myrinet是一項(xiàng)高性能的分包通信和交換技術(shù)，被廣泛應(yīng)用于工作站、PC、服務(wù)器的互聯(lián)集群.它以一種經(jīng)濟(jì)的方式實(shí)現(xiàn)高性能以及高可用性.它最具有吸引力的特征是同時(shí)具有高帶寬和低時(shí)延，并且成本上更接近于以太網(wǎng).Myrinet具有廣闊的應(yīng)用前景，國(guó)內(nèi)外許多高性能的集群系統(tǒng)都是基于它構(gòu)建的.

以太網(wǎng)是應(yīng)用最為廣泛的局域網(wǎng)，它采用帶沖突檢測(cè)的載波幀聽(tīng)多路訪問(wèn)機(jī)制.以太網(wǎng)中節(jié)點(diǎn)都可以看到在網(wǎng)絡(luò)中發(fā)送的所有信息，因此，以太網(wǎng)是一種廣播網(wǎng)絡(luò).以太網(wǎng)有共享式以太網(wǎng)和交換式以太網(wǎng)2類.共享式以太網(wǎng)所有用戶共享帶寬，每個(gè)用戶的實(shí)際可用帶寬隨用戶數(shù)的增加而遞減.當(dāng)信息繁忙時(shí)，多個(gè)用戶都可能同時(shí)“爭(zhēng)用”一個(gè)信道，而一個(gè)通道在某一時(shí)刻只允許一個(gè)用戶占用，所以大量用戶經(jīng)常處于監(jiān)測(cè)等待狀態(tài)，致使信號(hào)在傳送時(shí)產(chǎn)生抖動(dòng)、停滯或失真，嚴(yán)重影響網(wǎng)絡(luò)性能.交換式以太網(wǎng)中，交換機(jī)供給每個(gè)用戶專用的信息通道，除非2個(gè)源端口企圖將信息同時(shí)發(fā)往同一目的端口，否則各個(gè)源端口與各自的目的端口之間可同時(shí)進(jìn)行通信而不發(fā)生沖突.交換式以太網(wǎng)是目前構(gòu)建小型集群使用最多的網(wǎng)絡(luò)互聯(lián)結(jié)構(gòu).

1.3 網(wǎng)絡(luò)并行計(jì)算環(huán)境

網(wǎng)絡(luò)并行計(jì)算需要一個(gè)可移植的網(wǎng)絡(luò)并行計(jì)算環(huán)境，這對(duì)整個(gè)并行計(jì)算系統(tǒng)尤為重要.目前，較為流行的網(wǎng)絡(luò)并行計(jì)算環(huán)境有 MPI、PVM、Express、P4等.其中，MPI具有較好的可移植性、高效性和強(qiáng)大的功能，并且具有不同的免費(fèi)實(shí)現(xiàn)版本［5］.MPI是一種標(biāo)準(zhǔn)或規(guī)范的代表，而并不特指某一個(gè)對(duì)它的具體實(shí)現(xiàn).迄今為止，所有的并行計(jì)算機(jī)制造廠商都提供對(duì)MPI的支持，可以在網(wǎng)上免費(fèi)得到MPI在不同并行計(jì)算機(jī)上的實(shí)現(xiàn)［5］.一個(gè)正確的MPI程序，可以不加修改地在所有的并行機(jī)上運(yùn)行.MPI已經(jīng)成為國(guó)際間并行程序設(shè)計(jì)的標(biāo)準(zhǔn)，它具有如下的顯著優(yōu)點(diǎn):

(1)MPI支持點(diǎn)對(duì)點(diǎn)通信和集體通信;

(2)MPI的可移植性強(qiáng)，能同時(shí)支持同構(gòu)和異構(gòu)的并行計(jì)算;

(3)MPI的可伸縮性強(qiáng)，允許系統(tǒng)中節(jié)點(diǎn)的任意增加或減少;

(4)MPI是一個(gè)消息接口傳遞的標(biāo)準(zhǔn)，用于開(kāi)發(fā)基于消息傳遞的并行程序.其目的是為用戶提供一個(gè)可移植的、實(shí)際可用的、高效靈活的消息傳遞接口庫(kù).MPI以語(yǔ)言獨(dú)立的形式來(lái)定義這個(gè)接口庫(kù)，并提供了與C和FORTRAN的綁定.

MPI作為一個(gè)并行程序庫(kù)的優(yōu)秀開(kāi)發(fā)平臺(tái)，為用戶編寫和運(yùn)行并行程序提供了便利的條件.因此，MPI在業(yè)界被廣泛的接受和采用.

2 系統(tǒng)的實(shí)現(xiàn)

2.1 硬件平臺(tái)

將所有的計(jì)算機(jī)配置在同一局域網(wǎng)內(nèi).筆者所搭建的集群由8臺(tái)相同配置的計(jì)算機(jī)和1臺(tái)交換機(jī)組成.每個(gè)節(jié)點(diǎn)機(jī)的配置為:2.4 GHz CPU，512 MB DDR內(nèi)存，80 GB硬盤.100 Mbps高速以太網(wǎng)作為集群的互聯(lián)網(wǎng)絡(luò).每個(gè)從節(jié)點(diǎn)只有1塊網(wǎng)卡，而主節(jié)點(diǎn)安裝2塊網(wǎng)卡，一塊用于連接集群系統(tǒng)，另一塊用于連接Internet.將主節(jié)點(diǎn)命名為node1，其余的結(jié)點(diǎn)依次為node2～node8.IP地址分別設(shè)為192.168.1.1～192.168.1.8.各個(gè)節(jié)點(diǎn)之間通過(guò)網(wǎng)線連接成星型拓?fù)浣Y(jié)構(gòu).為各個(gè)節(jié)點(diǎn)機(jī)配置相同的/etc/host文件以實(shí)現(xiàn)計(jì)算機(jī)名稱和IP地址之間的轉(zhuǎn)換.

2.2 網(wǎng)絡(luò)操作系統(tǒng)

集群系統(tǒng)中的節(jié)點(diǎn)機(jī)操作系統(tǒng)絕大部分選用Linux、Windows NT/2000/XP，它們都有很強(qiáng)的網(wǎng)絡(luò)支持功能和可靠性.Linux是一個(gè)領(lǐng)先的操作系統(tǒng)，是全面多任務(wù)和真正32位的網(wǎng)絡(luò)操作系統(tǒng).它是一款免費(fèi)的操作系統(tǒng)，具有眾多的誘人之處.其中，它提供的豐富的網(wǎng)絡(luò)功能和可靠的安全穩(wěn)定性能使之更適合網(wǎng)絡(luò)并行計(jì)算.因此，Linux是目前主流集群系統(tǒng)采用的操作系統(tǒng).本文搭建的集群系統(tǒng)采用的是Red Hat 9.0.

2.3 基本的網(wǎng)絡(luò)服務(wù)

Linux集群每個(gè)節(jié)點(diǎn)有自己的處理器、內(nèi)存和操作系統(tǒng)，各臺(tái)機(jī)器之間不能直接訪問(wèn).MPI卻需要這樣的互訪，這就需要網(wǎng)絡(luò)協(xié)議的支持.

由于需要實(shí)現(xiàn)互訪和并行計(jì)算中每個(gè)節(jié)點(diǎn)運(yùn)行相同的程序這一特點(diǎn)，就要求每個(gè)節(jié)點(diǎn)能載入同一個(gè)程序并進(jìn)行初始化.NFS［6］可以實(shí)現(xiàn)這個(gè)功能.NFS允許一個(gè)系統(tǒng)在網(wǎng)絡(luò)上與他人共享目錄和文件.通過(guò)使用NFS，用戶和程序可像訪問(wèn)本地文件一樣訪問(wèn)遠(yuǎn)端系統(tǒng)上的文件.用戶在任何一個(gè)節(jié)點(diǎn)登陸，看見(jiàn)的是單一的系統(tǒng)印象，感覺(jué)不到多臺(tái)計(jì)算機(jī)的存在.

集群還需要有高效的身份驗(yàn)證，并且能執(zhí)行用戶發(fā)出的計(jì)算指令.這個(gè)功能由NIS和RSH服務(wù)實(shí)現(xiàn).NIS是網(wǎng)絡(luò)信息服務(wù).由于集群系統(tǒng)中的節(jié)點(diǎn)數(shù)目多，每個(gè)節(jié)點(diǎn)的賬號(hào)和密碼都需要進(jìn)行管理.NIS通過(guò)一臺(tái)主控節(jié)點(diǎn)來(lái)管理集群中所有節(jié)點(diǎn)的賬號(hào)，當(dāng)其他主機(jī)有使用者登陸的需求時(shí)，到主控節(jié)點(diǎn)上要求賬號(hào)和密碼資料.因此，可通過(guò)主控節(jié)點(diǎn)來(lái)實(shí)現(xiàn)增加、修改或刪除節(jié)點(diǎn)，這樣可降低重復(fù)設(shè)定使用者賬號(hào)的步驟.RSH是遠(yuǎn)程通信協(xié)議.基于MPI的并行計(jì)算需要在各個(gè)節(jié)點(diǎn)啟動(dòng)并行計(jì)算任務(wù)，用戶需要在各個(gè)節(jié)點(diǎn)登陸，然后進(jìn)行計(jì)算，這種做法效率很低.RSH提供這樣一種機(jī)制，不需要登錄遠(yuǎn)程機(jī)器就可以進(jìn)行計(jì)算并提交任務(wù).

2.4 MPICH的安裝和配置

MPI具有多種實(shí)現(xiàn)版本.MPICH［7］是MPI標(biāo)準(zhǔn)的一種最重要的實(shí)現(xiàn)，它的開(kāi)發(fā)主要由Argonne National Laboratory和 Mississippi State University共同完成.MPI的安裝和配置主要有下載、配置、安裝和編譯幾個(gè)步驟.本系統(tǒng)采用mpich2-1.0.6版本作為并行環(huán)境，由于已經(jīng)安裝和開(kāi)啟了相關(guān)的網(wǎng)絡(luò)服務(wù)，安裝和配置只需要在主節(jié)點(diǎn)進(jìn)行1次即可.

3 性能測(cè)試

3.1 FFT變換

圖2是8點(diǎn)的頻率抽取法蝶形運(yùn)算流圖.圖2中，N=2R，其中R是迭代次數(shù).L指的是第L級(jí)迭代，0≤L≤R－1.從圖2可以看出，求解N點(diǎn)序列的FFT變換是多步驟的迭代操作.每一級(jí)的迭代都是由多對(duì)數(shù)據(jù)之間的蝶形運(yùn)算組成;每次蝶形運(yùn)算都是在2個(gè)數(shù)據(jù)間進(jìn)行操作.蝶形運(yùn)算的規(guī)則完全相同，不同之處在于每次蝶形運(yùn)算的原始數(shù)據(jù)不同，運(yùn)算過(guò)程中的旋轉(zhuǎn)因子不同.因此，N點(diǎn)序列的FFT運(yùn)算具有并行性.對(duì)N點(diǎn)序列的FFT運(yùn)算的并行求解過(guò)程實(shí)質(zhì)上就是將數(shù)據(jù)進(jìn)行分塊處理.并行FFT算法的流程圖如圖3所示.

圖2 N=8的頻率抽取法蝶形運(yùn)算流圖Fig.2 The butterfly computing flowchart of 8-point FFT

圖3 并行FFT變換的流程圖Fig.3 The flow chart of parallel FFT

3.2 實(shí)驗(yàn)結(jié)果與分析

測(cè)試用例是計(jì)算數(shù)據(jù)規(guī)模從215～220的序列的FFT變換.圖4所示為并行FFT算法的加速比，圖5所示為并行FFT算法的效率.圖4、圖5中P是計(jì)算節(jié)點(diǎn)的數(shù)目.

圖4 并行FFT算法的加速比Fig.4 The speedups of parallel FFT

圖5 并行FFT算法的效率Fig.5 The efficiencies of parallel FFT

從圖4和圖5可知，加速比隨計(jì)算節(jié)點(diǎn)的增加而增大，效率卻相反，它隨節(jié)點(diǎn)數(shù)目的增加而降低，將其稱之為并行算法設(shè)計(jì)的瓶頸.圖5中效率隨參與運(yùn)算節(jié)點(diǎn)數(shù)目的增加而顯著下降，主要原因是蝶形操作之后，每個(gè)節(jié)點(diǎn)將結(jié)果返回給主處理器，同時(shí)還需要將更新的數(shù)據(jù)廣播.由于網(wǎng)絡(luò)的延遲，相對(duì)于算法本身的計(jì)算任務(wù)，這些結(jié)果數(shù)據(jù)和更新數(shù)據(jù)的傳送也是一筆不小的時(shí)間開(kāi)銷.這樣的計(jì)算通信比率較小的任務(wù)被稱為細(xì)粒度任務(wù).細(xì)粒度任務(wù)不適合用前述方式搭建的網(wǎng)絡(luò)并行計(jì)算系統(tǒng)進(jìn)行運(yùn)算.前述方式搭建的網(wǎng)絡(luò)并行計(jì)算系統(tǒng)更適合計(jì)算通信比率較大的粗粒度并行計(jì)算任務(wù).

4 結(jié)論

利用局域網(wǎng)構(gòu)建的網(wǎng)絡(luò)并行計(jì)算系統(tǒng)對(duì)于小規(guī)模的計(jì)算任務(wù)是一個(gè)較好的解決方案，值得推廣和普及.這種系統(tǒng)更適合于粗粒度的并行計(jì)算任務(wù)而不適于細(xì)粒度的并行任務(wù).對(duì)于不同的并行計(jì)算任務(wù)選擇合適的并行計(jì)算環(huán)境是實(shí)現(xiàn)高效并行計(jì)算的一個(gè)不可忽視的重要因素.

［1］ Murphy K P.Dynamic Bayesian Networks:Representation，Inference and Learning［D］.Berkley: Univ.of California，2002.

［2］ 都志輝.高性能計(jì)算之并行編程技術(shù)——MPI并行程序設(shè)計(jì)［M］.北京:清華大學(xué)出版社，2001:31－39.

［3］ Foster I，Kesselman C，Tuecke S.The Anatomy of Grid:Enabling Scalable Virtual Organization［J］.International Journal of Supercomputer Application，2001，15(13):200－222.

［4］ 張晨曦.計(jì)算機(jī)體系結(jié)構(gòu)教程［M］.北京:清華大學(xué)出版社，2009:12－15.

［5］ 陳國(guó)良.并行計(jì)算——結(jié)構(gòu)、算法、編程［M］.北京:高等教育出版社，2009:121－125.

［6］ 楊曉東，陸松，牟勝梅.并行計(jì)算及體系結(jié)構(gòu)技術(shù)與分析［M］.北京:科學(xué)出版社，2009:147－152.

［7］ 陳國(guó)良.并行計(jì)算——結(jié)構(gòu)、算法、編程［M］.北京:高等教育出版社，2001:77－80.

［8］ Gropp W，Lusk E.User's Guide for Mpich，a Portable Implementation of MPI［J］.Parallel Computing，2006，22(6):789－828.