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

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

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

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

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

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

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

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