基于MPI的網絡并行計算系統構建及分析

張克非， 梅 栴， 趙振江

(沈陽化工大學計算機科學與技術學院，遼寧沈陽110142)

現代計算技術顯著地促進了科學計算的發展，高效的計算速度是目前科學計算中迫切需要解決的問題.目前，在尖端科學研究領域諸如地震預報、氣候模擬和地質研究中存在著巨大的計算任務［1］.如此龐大計算任務的解決依靠單處理器是無法實現的.在這些領域，迫切需要高效的計算方法.與此同時，隨著PC機性能的提高和網絡產品的更新換代使一種新的計算形式——網絡并行計算應運而生.網絡并行計算是目前解決大規模計算問題一個可行的有效途徑.本文主要闡述了基于MPI的并行計算系統搭建過程，并利用一個并行計算實例對此方法進行驗證，取得了良好結果.

1 網絡并行計算系統的體系結構

網絡并行計算［2］是一種并行計算技術，它通過網絡連接多個計算機系統來實現高效的并行處理任務.網絡并行計算能夠充分利用整個系統的資源進行統一調度和協調處理，是目前并行計算研究領域的一個新的發展趨勢.

1.1 硬件結構

隨著網絡的普及和發展使得利用集群作為網絡并行計算的開發平臺成為一種新趨勢.集群是將一組計算機連接起來實現高效并行計算的系統.集群中的各臺計算機之間聯系緊密，在某種程度上可將整個系統理解成一臺計算機.集群中的計算節點可以是PC或工作站，每一個節點有獨立的內存、輸入輸出設備和操作系統，節點之間通過高速局域網絡互相連接.對于用戶和應用程序而言，集群如同一個單一的系統.通過消息傳遞機制實現節點之間的互相通信，并提供上層的API接口方便用戶編程.集群以低廉的價格獲得強大的計算能力，是目前網絡并行計算領域的優秀開發平臺.一個典型包含4個節點的集群的體系結構［3］如圖1所示.

圖1 4個節點的集群的體系結構圖Fig.1 The architecture diagram of cluster include four nodes

1.2 集群的互連網絡

網絡數據交換是影響網絡并行計算系統性能的瓶頸.因此，采用高速的網絡將會明顯提高系統性能.目前，集群一般通過ATM、Myrinet、以太網［4］等網絡進行互連.

ATM是異步傳輸模式的縮寫，是以信元為基礎的一種分組交換和復用技術.它具有高速數據傳輸率，適用于局域網和廣域網，但ATM網絡的硬件設備價格非常昂貴，限制了它的普及和應用.

Myrinet是一項高性能的分包通信和交換技術，被廣泛應用于工作站、PC、服務器的互聯集群.它以一種經濟的方式實現高性能以及高可用性.它最具有吸引力的特征是同時具有高帶寬和低時延，并且成本上更接近于以太網.Myrinet具有廣闊的應用前景，國內外許多高性能的集群系統都是基于它構建的.

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

1.3 網絡并行計算環境

網絡并行計算需要一個可移植的網絡并行計算環境，這對整個并行計算系統尤為重要.目前，較為流行的網絡并行計算環境有 MPI、PVM、Express、P4等.其中，MPI具有較好的可移植性、高效性和強大的功能，并且具有不同的免費實現版本［5］.MPI是一種標準或規范的代表，而并不特指某一個對它的具體實現.迄今為止，所有的并行計算機制造廠商都提供對MPI的支持，可以在網上免費得到MPI在不同并行計算機上的實現［5］.一個正確的MPI程序，可以不加修改地在所有的并行機上運行.MPI已經成為國際間并行程序設計的標準，它具有如下的顯著優點:

(1)MPI支持點對點通信和集體通信;

(2)MPI的可移植性強，能同時支持同構和異構的并行計算;

(3)MPI的可伸縮性強，允許系統中節點的任意增加或減少;

(4)MPI是一個消息接口傳遞的標準，用于開發基于消息傳遞的并行程序.其目的是為用戶提供一個可移植的、實際可用的、高效靈活的消息傳遞接口庫.MPI以語言獨立的形式來定義這個接口庫，并提供了與C和FORTRAN的綁定.

MPI作為一個并行程序庫的優秀開發平臺，為用戶編寫和運行并行程序提供了便利的條件.因此，MPI在業界被廣泛的接受和采用.

2 系統的實現

2.1 硬件平臺

將所有的計算機配置在同一局域網內.筆者所搭建的集群由8臺相同配置的計算機和1臺交換機組成.每個節點機的配置為:2.4 GHz CPU，512 MB DDR內存，80 GB硬盤.100 Mbps高速以太網作為集群的互聯網絡.每個從節點只有1塊網卡，而主節點安裝2塊網卡，一塊用于連接集群系統，另一塊用于連接Internet.將主節點命名為node1，其余的結點依次為node2～node8.IP地址分別設為192.168.1.1～192.168.1.8.各個節點之間通過網線連接成星型拓撲結構.為各個節點機配置相同的/etc/host文件以實現計算機名稱和IP地址之間的轉換.

2.2 網絡操作系統

集群系統中的節點機操作系統絕大部分選用Linux、Windows NT/2000/XP，它們都有很強的網絡支持功能和可靠性.Linux是一個領先的操作系統，是全面多任務和真正32位的網絡操作系統.它是一款免費的操作系統，具有眾多的誘人之處.其中，它提供的豐富的網絡功能和可靠的安全穩定性能使之更適合網絡并行計算.因此，Linux是目前主流集群系統采用的操作系統.本文搭建的集群系統采用的是Red Hat 9.0.

2.3 基本的網絡服務

Linux集群每個節點有自己的處理器、內存和操作系統，各臺機器之間不能直接訪問.MPI卻需要這樣的互訪，這就需要網絡協議的支持.

由于需要實現互訪和并行計算中每個節點運行相同的程序這一特點，就要求每個節點能載入同一個程序并進行初始化.NFS［6］可以實現這個功能.NFS允許一個系統在網絡上與他人共享目錄和文件.通過使用NFS，用戶和程序可像訪問本地文件一樣訪問遠端系統上的文件.用戶在任何一個節點登陸，看見的是單一的系統印象，感覺不到多臺計算機的存在.

集群還需要有高效的身份驗證，并且能執行用戶發出的計算指令.這個功能由NIS和RSH服務實現.NIS是網絡信息服務.由于集群系統中的節點數目多，每個節點的賬號和密碼都需要進行管理.NIS通過一臺主控節點來管理集群中所有節點的賬號，當其他主機有使用者登陸的需求時，到主控節點上要求賬號和密碼資料.因此，可通過主控節點來實現增加、修改或刪除節點，這樣可降低重復設定使用者賬號的步驟.RSH是遠程通信協議.基于MPI的并行計算需要在各個節點啟動并行計算任務，用戶需要在各個節點登陸，然后進行計算，這種做法效率很低.RSH提供這樣一種機制，不需要登錄遠程機器就可以進行計算并提交任務.

2.4 MPICH的安裝和配置

MPI具有多種實現版本.MPICH［7］是MPI標準的一種最重要的實現，它的開發主要由Argonne National Laboratory和 Mississippi State University共同完成.MPI的安裝和配置主要有下載、配置、安裝和編譯幾個步驟.本系統采用mpich2-1.0.6版本作為并行環境，由于已經安裝和開啟了相關的網絡服務，安裝和配置只需要在主節點進行1次即可.

3 性能測試

3.1 FFT變換

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

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

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

3.2 實驗結果與分析

測試用例是計算數據規模從215～220的序列的FFT變換.圖4所示為并行FFT算法的加速比，圖5所示為并行FFT算法的效率.圖4、圖5中P是計算節點的數目.

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

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

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

4 結論

利用局域網構建的網絡并行計算系統對于小規模的計算任務是一個較好的解決方案，值得推廣和普及.這種系統更適合于粗粒度的并行計算任務而不適于細粒度的并行任務.對于不同的并行計算任務選擇合適的并行計算環境是實現高效并行計算的一個不可忽視的重要因素.

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

［2］ 都志輝.高性能計算之并行編程技術——MPI并行程序設計［M］.北京:清華大學出版社，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］ 張晨曦.計算機體系結構教程［M］.北京:清華大學出版社，2009:12－15.

［5］ 陳國良.并行計算——結構、算法、編程［M］.北京:高等教育出版社，2009:121－125.

［6］ 楊曉東，陸松，牟勝梅.并行計算及體系結構技術與分析［M］.北京:科學出版社，2009:147－152.

［7］ 陳國良.并行計算——結構、算法、編程［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.