近年來隨著各種應(yīng)用計算需求的不斷增長，集群計算的規(guī)模也在不斷擴大。然而集群規(guī)模的增大并不意味著絕對計算速度和并行效率的提升,其中影響并行應(yīng)用程序計算性能發(fā)揮的主要瓶頸之一是消息傳遞通信設(shè)計不理想或使用不合理，導(dǎo)致全局通信使用頻率過高，造成通信堵塞、各種操作的響應(yīng)時間持續(xù)延長和計算性能的下降。有數(shù)據(jù)表明，在大多數(shù)集群通信中，聚合通信開銷往往占據(jù)全部消息傳遞通信開銷的80%以上。因此，合理調(diào)整消息傳遞中聚合通信機制、降低全局通信流量應(yīng)是改善現(xiàn)有集群計算環(huán)境的有效手段之一[1]。
     本文基于MPI集群框架結(jié)構(gòu)，通過分析單層型集群和樹型結(jié)構(gòu)集群的聚合通信原理，提出了一種采用樹型結(jié)構(gòu)的MPI集群系統(tǒng)設(shè)計方案，用以降低聚合通信的開銷，改善集群計算環(huán)境，同時也為集群的擴展提供更加靈活的手段。聚合通信包括很多全局操作(如廣播、同步、歸約、分發(fā)、收集)等，但很多聚合通信是由其他聚合通信的組合來實現(xiàn)的，本文選擇了有代表性的廣播和收集作為主要研究對象。
1 單層型結(jié)構(gòu)與樹型結(jié)構(gòu)
1.1 單層型結(jié)構(gòu)介紹
     單層型結(jié)構(gòu)是目前大多數(shù)MPI集群工具所采用的框架結(jié)構(gòu)。如圖1所示。該結(jié)構(gòu)由一個主控節(jié)點和多個從屬節(jié)點組成，主控節(jié)點和每個從屬節(jié)點之間都建立了通信連接，實現(xiàn)聚合通信，從屬節(jié)點相互之間可以實現(xiàn)點到點通信[2]。

　主控節(jié)點的功能主要包括與用戶進行交互，向從屬節(jié)點廣播、分發(fā)消息，收集、歸納從屬節(jié)點發(fā)來的消息，以及系統(tǒng)認證、網(wǎng)絡(luò)管理和遠程控制等。
    從屬節(jié)點的功能主要用于計算、接收主控節(jié)點發(fā)來的各種控制命令、數(shù)據(jù)，根據(jù)控制命令在其節(jié)點機上進行相應(yīng)的執(zhí)行，然后將執(zhí)行后的結(jié)果傳回給主控節(jié)點。
　單層型結(jié)構(gòu)集群的實現(xiàn)相對簡單，易于操作，且集群工具和應(yīng)用軟件較多，所以應(yīng)用廣泛。但是由于集群中只有一個主控節(jié)點，在聚合通信時，無論是一對多模式，多對多模式還是多對一模式，都要圍繞著主控節(jié)點進行,使得集群中全局通信流量所占比重較大。當(dāng)集群節(jié)點數(shù)增加或計算量很大時，網(wǎng)絡(luò)負載極易到達額定上限，使得主控節(jié)點無法正常運行，計算性能下降。
　單層型結(jié)構(gòu)的消息廣播和消息收集的時間復(fù)雜度均為：O(n)
1.2 樹型結(jié)構(gòu)介紹
      樹型結(jié)構(gòu)是針對單層型結(jié)構(gòu)在消息廣播和消息收集方面速度慢、可擴展性差的弱點而提出的新的消息傳輸結(jié)構(gòu)。圖2所示為典型的樹型結(jié)構(gòu)，和單層型結(jié)構(gòu)一樣，樹型結(jié)構(gòu)也有主控節(jié)點（根節(jié)點）和從屬節(jié)點（葉子節(jié)點），且功能與單層型結(jié)構(gòu)類似。不同的是，樹型結(jié)構(gòu)中還包含分支節(jié)點，這些分支節(jié)點是樹的內(nèi)部節(jié)點，沒有計算功能，也沒有系統(tǒng)認證、網(wǎng)絡(luò)管理和遠程控制等功能，只有對消息的轉(zhuǎn)發(fā)、分發(fā)和收集功能，所以也叫路由節(jié)點。圖2中，根節(jié)點與其下一層的分支節(jié)點有直接的通信連接，同樣每個分支節(jié)點都與其下一層的節(jié)點有直接通信連接，上層節(jié)點與下層節(jié)點可以實現(xiàn)聚合通信，而擁有同一個父親的同層節(jié)點之間可以進行點到點通信。除此以外，其他非同父節(jié)點相互之間沒有建立直接的通信連接。

      樹型結(jié)構(gòu)集群可以將全局通信域劃分為多個子通信域，并且可以將主控節(jié)點的負載量分擔(dān)到各個分支節(jié)點上，降低全局通信量進而改善集群計算環(huán)境。同時隨著樹的深度增加，使得集群更易于擴展。但該集群實現(xiàn)起來比較復(fù)雜，且沒有專用的協(xié)議、應(yīng)用軟件或集群工具的支持[3]。
      樹型結(jié)構(gòu)的消息廣播和消息收集的時間復(fù)雜度均為：O(logn)
2 樹型MPI的設(shè)計與實現(xiàn)        

    雖然使用樹型結(jié)構(gòu)的集群系統(tǒng)可以改善聚合通信的效率，但其實現(xiàn)起來則相對復(fù)雜。主要原因是常用的MPI計算通信工具基于單層型集群設(shè)計，是在主控節(jié)點與若干計算節(jié)點之間的通信基礎(chǔ)之上實現(xiàn)的。為此，本文提出了一種利用IP轉(zhuǎn)發(fā)技術(shù)和MPI并行編程技術(shù)實現(xiàn)樹型結(jié)構(gòu)的MPI集群系統(tǒng)設(shè)計方案。這里需要注意以下問題：
　(1)根節(jié)點的設(shè)計
　在構(gòu)建集群網(wǎng)絡(luò)時，網(wǎng)絡(luò)安全和通信效率既相互依賴又相互制衡。若省去頻繁的核實用戶身份等安全方面的檢查，則可以省去一部分系統(tǒng)開銷，進而提高網(wǎng)絡(luò)通信效率，但集群網(wǎng)絡(luò)的安全性就無法保障；同樣，若犧牲通信效率而實現(xiàn)網(wǎng)絡(luò)安全，則集群計算的優(yōu)勢將無法體現(xiàn)。通常的做法是采用內(nèi)外網(wǎng)模式，即從屬節(jié)點和主控節(jié)點之間由內(nèi)部網(wǎng)絡(luò)互聯(lián)，只有主控節(jié)點另有網(wǎng)絡(luò)通道通向外部網(wǎng)絡(luò)。這樣，由于內(nèi)外網(wǎng)絡(luò)物理隔離，為網(wǎng)絡(luò)安全提供了保證，在內(nèi)部網(wǎng)絡(luò)中可以省去頻繁的用戶身份認證等安全方面的開銷，從而為通信效率的提升留出空間。
　根節(jié)點（主控節(jié)點）的設(shè)計也將采用內(nèi)外網(wǎng)模式，在其機器上安裝兩塊網(wǎng)卡（網(wǎng)絡(luò)適配器），一塊接集群內(nèi)部網(wǎng)，使用內(nèi)部網(wǎng)絡(luò)設(shè)置，提供內(nèi)部網(wǎng)絡(luò)服務(wù)（域名服務(wù)，NIS，NFS和RSH）；另一塊接外部網(wǎng)，留出對外聯(lián)系的通道，兩網(wǎng)卡之間不提供路由、轉(zhuǎn)發(fā)等功能。
　(2)分支節(jié)點的設(shè)計
　樹形結(jié)構(gòu)中的分支節(jié)點用于連接根節(jié)點（主控節(jié)點）和葉子節(jié)點（計算節(jié)點），在整個集群中發(fā)揮兩個作用：一個是承上啟下的連接作用，另一個則是對根節(jié)點（主控節(jié)點）的分擔(dān)作用，所以分支節(jié)點應(yīng)具有路由和對消息的傳遞、分發(fā)和收集等功能。
    分支節(jié)點的設(shè)計與根節(jié)點有類似之處。也是在其機器上安裝兩塊網(wǎng)卡，一塊連接上層節(jié)點（根節(jié)點或上層的分支節(jié)點），IP地址設(shè)置在上層節(jié)點的同一個網(wǎng)段內(nèi)，默認網(wǎng)關(guān)指向上層節(jié)點（父節(jié)點），使其成為上層網(wǎng)絡(luò)的成員；另一塊連接下層節(jié)點（下層的分支節(jié)點或葉子節(jié)點），設(shè)置IP地址（最好與前一塊網(wǎng)卡的IP地址不同網(wǎng)段），為下層網(wǎng)絡(luò)提供網(wǎng)關(guān)服務(wù)。但若要在上下層兩個網(wǎng)絡(luò)實現(xiàn)路由，需要在分支節(jié)點上修改 /etc/sysctl.conf配置文件中的net.ipv4.ip_forward = 1（以Linux操作系統(tǒng)為平臺參考），使得本節(jié)點機IP轉(zhuǎn)發(fā)功能生效。這樣做的目的是既能實現(xiàn)上下兩層網(wǎng)絡(luò)之間的通信，同時又能阻止基于網(wǎng)絡(luò)第二層的廣播幀的傳播。
　(3)域名的設(shè)計
　在TCP/IP中,計算機之間的通信通過IP訪問來實現(xiàn)，但IP地址不容易編程和管理，所以整個集群系統(tǒng)需要為每個節(jié)點提供一套統(tǒng)一的命名機制。如圖3所示，Boot為根節(jié)點內(nèi)部網(wǎng)卡的網(wǎng)絡(luò)標(biāo)識，bran01-up和bran01-down為同一個分支節(jié)點機上的兩塊網(wǎng)卡上的網(wǎng)絡(luò)標(biāo)識，前一塊為連接上層網(wǎng)絡(luò)的接口，后一塊為連接下層網(wǎng)絡(luò)的接口，leaf01為葉子節(jié)點的網(wǎng)絡(luò)標(biāo)識。MPI編程環(huán)境可以通過此域名來區(qū)分、訪問運行在各個節(jié)點機上的進程（如MPI_Get_processor_name()函數(shù)）。

　對于集群系統(tǒng)來說，集群中所有節(jié)點域名和IP地址的對應(yīng)關(guān)系的建立是在/etc/hosts文件中描述的，不僅是因為它們經(jīng)常用到，而且還因為該文件結(jié)構(gòu)簡單，更易于快速查找。圖3所示的/etc/hosts.equiv文件可以為RSH(遠程shell命令)提供無口令遠程登錄，這也為各節(jié)點載入同一個計算程序二進制代碼和用戶身份的快速驗證提供了可能。
       (4)進程組和通信域的設(shè)計
　    MPI中的通信域（Communicator）提供了一種組織和管理進程間通信的方法。每個通信域包括一組MPI進程，稱為進程組。這一組進程之間可以相互通信，而且這個通信域內(nèi)的通信不會跨越通信域的邊界。這樣就提供了一種安全的消息傳遞機制，因為它隔離了內(nèi)部和外部的通信，避免了不必要的同步。每個進程都至少在某個特定的通信域中，但有可能進程在多個通信域中，這就像某個人可以是多個組織的成員一樣。進程組由一個進程的有序序列進行描述，每個進程根據(jù)在序列中的位置被賦予一個進程號（0， 1， ...，N-1）[4]。
　    本文將根節(jié)點與其相鄰的下一層節(jié)點（孩子節(jié)點）劃定為一個進程組0，將分支節(jié)點1與其相鄰的下一層節(jié)點（孩子節(jié)點）劃定為進程組1，…，依此類推，直到所有分支節(jié)點或根節(jié)點都擁有自己的進程組為止，如圖4所示。由于每個分支節(jié)點或根節(jié)點都有兩塊網(wǎng)卡，所以將兩塊網(wǎng)卡分屬不同的進程組中，彼此互不包含。將全局通信域劃分成若干個子通信域，使得大量的消息傳遞開銷被限制在局部范圍內(nèi),大大降低了全局通信的頻率，從而提高了集群通信的性能。

   (5)組間通信
　進程組劃分之后，形成相應(yīng)的通信域，規(guī)避了大量節(jié)點間同步所消耗的開銷。但進程組之間也要進行通信，根節(jié)點需要將消息逐層傳遞到葉子節(jié)點，同樣葉子節(jié)點所計算出來的結(jié)果也是要逐層收集、規(guī)約到根節(jié)點，所以組間通信也是本系統(tǒng)實現(xiàn)的關(guān)鍵之一。這里,通過使用MPI組間通信函數(shù)(如MPI_Intercomm_create()函數(shù))來實現(xiàn)組間消息的傳遞。
　(6)葉子節(jié)點的設(shè)計
　 葉子節(jié)點作為主要計算節(jié)點，除了NIS、NFS、RSH客戶端軟件和MPI相關(guān)軟件外，盡量不再安裝其他軟件，以減少葉子節(jié)點額外的開銷。設(shè)置與其父節(jié)點同屬一個網(wǎng)段的IP地址，并將網(wǎng)關(guān)指向其父節(jié)點。如有必要可以精簡操作系統(tǒng)內(nèi)核，使其盡量占用CPU時間少、占用內(nèi)存少。
3 實驗結(jié)果與分析
3.1 實驗環(huán)境和方法
    本實驗將先后搭建三組環(huán)境對這兩種結(jié)構(gòu)的MPI集群進行測試,測試環(huán)境如下：
    (1)第一組是具有2個計算節(jié)點的集群，單層型和樹型集群均由1個主控節(jié)點和兩個計算節(jié)點構(gòu)成。
    (2)第二組是擁有4個計算節(jié)點的集群，單層型是指1主控節(jié)點和4個計算節(jié)點構(gòu)成，而樹型結(jié)構(gòu)則是由1個根節(jié)點（主控節(jié)點），2個分支節(jié)點和4個計算節(jié)點構(gòu)成，其中每個分支節(jié)點各連接兩個計算節(jié)點,對稱分布。
    (3)第三組是具有6個計算節(jié)點的集群,如圖5所示。左圖為單層型MPI集群，擁有6個計算節(jié)點和1個主控節(jié)點；右圖為樹型集群，擁有1個根節(jié)點，2個分支節(jié)點和6個計算節(jié)點。

    這其中每個節(jié)點包含一顆PIV處理器和2 GB內(nèi)存，操作系統(tǒng)采用Redhat Linux Enterprise 5，并行集群軟件為OPEN MPI 1.3。由于條件所限，加之實驗規(guī)模較小，所以本實驗采用MPI自帶的函數(shù)MPI_Wtime()來采集MPI計算的開始和結(jié)束時間，取兩者的時間差作為程序的運行時間，并對其進行比較和分析，用MPI_Wtick()函數(shù)來監(jiān)測MPI_Wtime()返回結(jié)果的精度。
    在實驗用例設(shè)計上，考慮到兩種MPI集群的通信機制中的傳輸路徑不同，所以采用計算求解三對角方程組作為測試方案，主要測試通信和計算的平衡。
3.2 測度結(jié)果和分析
    測試結(jié)果如表1、表2所示。

    測試結(jié)果表明,在第一組的測試中，雙方的運行時間沒有明顯差別，這是由于它們都擁有1個主控節(jié)點和2個計算節(jié)點。雖然樹型結(jié)構(gòu)在MPI聚合通信機制上有所改動，但影響有限，測試的結(jié)果基本相同。對于第二組的測試，測試結(jié)果差異較明顯，在傳輸短消息時，可以發(fā)現(xiàn)單層型集群的運算速度并不比樹型慢多少, 在16 B的情況單層型還優(yōu)于樹型。這是因為樹型結(jié)構(gòu)的集群中除了擁有和單層型相同數(shù)目的計算節(jié)點外，還有兩個分支節(jié)點（也叫路由節(jié)點），分支節(jié)點需要在兩個通信域之間傳遞處理消息，需要處理時間，所以樹型結(jié)構(gòu)的消息傳輸時間除了消息廣播和收集時間外，還有域間轉(zhuǎn)發(fā)處理的時間。盡管在時間復(fù)雜度上樹型結(jié)構(gòu)優(yōu)于單層型結(jié)構(gòu)，但在通信域中節(jié)點數(shù)較少、消息較小的情況下，兩者之間差距不是十分明顯，若再加上域間處理的時間，自然會出現(xiàn)這樣的情況。但當(dāng)消息增大時，由于樹型結(jié)構(gòu)中每個通信域的廣播和收集時間遠遠小于單層結(jié)構(gòu)的廣播和收集時間，從而抵消了分支節(jié)點處理消息的時間，所以樹型的整體運算時間明顯小于單層型的運算時間。對于第三組的測試，樹型的整體運算時間明顯優(yōu)于單層型集群，幾乎相當(dāng)于同級別單層型集群的1/2。這是由于隨著計算節(jié)點的增加，樹型MPI集群的優(yōu)勢明顯發(fā)揮出來，尤其是聚合通信方面。
　由上分析表明，基于樹型MPI并行計算集群的設(shè)計方案是可行的。在該方案上構(gòu)建的MPI集群系統(tǒng)可以使消息廣播和消息收集的速度明顯提高，使得全局通信使用頻率明顯下降，從而提升了集群整體計算速度。同時，由于樹型結(jié)構(gòu)的特點，使得集群的擴展更加輕松。盡管從理論上可知隨著節(jié)點數(shù)的增加樹型MPI的集群的優(yōu)勢將更加凸顯，但是由于實驗條件的限制，只能對集群通信系統(tǒng)做初步驗證。所以希望在未來的研發(fā)工作中能夠引入更科學(xué)的評測體系，不斷地論證和完善該系統(tǒng)，為提升中小型MPI集群性能提供幫助。
參考文獻
[1] 劉洋，曹建文，李玉成. 聚合通信模型的測試與分析[J].計算機工程與應(yīng)用，2006(9):30-33.
[2] CHEN C P. The parallel technologies (PaCT-2003)[C]. Nizhni Novgorod, Russia.2003.
[3] ROCH P C, ARNOLD D C, MILLER B P. MRNet: A software-based multicast/reduction network for scalable Tools[A]. Phoenix, Arizona, 2003.
[4] 莫則堯，袁國興.消息傳遞并行編程環(huán)境[M].北京：科學(xué)出版社，2001.