摘  要： 針對異構(gòu)集群并行效率不高的特點，通過分析由于計算系統(tǒng)設(shè)計不合理而產(chǎn)生的種種問題，提出了一種基于異構(gòu)環(huán)境下的樹型計算系統(tǒng)，用以兼容各類計算平臺，降低全局通信流量和均衡主控節(jié)點負(fù)載，從而改善集群通信效率，使集群的擴(kuò)展更加靈活，并且通過實驗驗證了該系統(tǒng)的可行性。
關(guān)鍵詞： MPI；組通信；廣播；收集；Linux

    近年來，為了滿足不斷增長的計算能力的需求，將已有的若干個不同的計算平臺(計算主機(jī)或計算網(wǎng)絡(luò))互連并改造成高性能集群系統(tǒng)是一種性價比較高的實現(xiàn)方式。然而集群規(guī)模的增大并沒有帶來絕對計算速度和并行效率的提升，伴隨而來的卻是全局通信（尤其是組通信）流量猛增，網(wǎng)絡(luò)堵塞嚴(yán)重，操作響應(yīng)遲滯，以至計算性能下降。
1 分析問題
    經(jīng)過對此類異構(gòu)集群的研究和分析，計算系統(tǒng)設(shè)計的不合理應(yīng)是造成該集群計算性能下降的主要原因之一。其理由是：在現(xiàn)有的計算系統(tǒng)中，大多是在不考慮集群網(wǎng)絡(luò)或處理機(jī)的性能差異的情況下對網(wǎng)絡(luò)進(jìn)行模型化，然后在此模型及其參數(shù)值基礎(chǔ)上構(gòu)造出最優(yōu)算法來實現(xiàn)通信。這樣的方法固然能夠定量地分析算法的描述精度，更能精確地給出通信時間的統(tǒng)計公式，這對計算系統(tǒng)的分析和設(shè)計是有指導(dǎo)意義的，但同時也存在著一些問題，就是它們假定計算中的所有進(jìn)程對(發(fā)送進(jìn)程和接收進(jìn)程稱為進(jìn)程對)之間的通信時間都是相等的。而實際情況卻并非如此，不同的處理器速度、不同的內(nèi)部結(jié)構(gòu)（單核或多核）以及集群內(nèi)部存在著不同類型的網(wǎng)絡(luò)和不同的連接方式，這些都會造成通信延遲的差異，所以此種模型構(gòu)造出的集群系統(tǒng)與實際應(yīng)用是有差距的。具體表現(xiàn)在應(yīng)用的透明性不足[1]、集群框架結(jié)構(gòu)[2]和編程模型的選用不合理。
2 解決問題
    解決問題思路就是在粒度、通信開銷和計算資源三者之間尋找最佳平衡點，并以此平衡點來組織集群，以達(dá)到性能提升的目的。本文將具體的網(wǎng)絡(luò)拓?fù)湫畔⒆鳛橹饕Ｒ罁?jù)，提出了一種基于異構(gòu)集群環(huán)境下采用樹型結(jié)構(gòu)的計算系統(tǒng)，用以確定適合并行任務(wù)的粒度、降低通信開銷和提高計算資源利用率，進(jìn)而改善集群計算環(huán)境。
2.1 樹型組通信系統(tǒng)的提出
2.1.1 樹型結(jié)構(gòu)介紹
    樹型結(jié)構(gòu)是針對單層型結(jié)構(gòu)在消息廣播和消息收集方面速度慢、可擴(kuò)展性差的弱點而提出的新的集群框架結(jié)構(gòu)。圖1所示的是典型的樹型結(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)認(rèn)證、網(wǎng)絡(luò)管理和遠(yuǎn)程控制等功能，只有對消息的轉(zhuǎn)發(fā)、分發(fā)和收集功能，所以也叫路由節(jié)點。如圖1所示，根節(jié)點與其下一層的分支節(jié)點有直接的通信連接。同樣，每個分支節(jié)點都與其下一層的節(jié)點有直接通信連接，上層節(jié)點與下層節(jié)點可以實現(xiàn)組通信，而擁有同一個父親的同層節(jié)點之間可以進(jìn)行點到點通信。除此以外，其他非同父節(jié)點相互之間沒有建立直接的通信連接。

    樹型結(jié)構(gòu)集群可以將全局通信域劃分為多個子通信域，并且可以將主控節(jié)點的負(fù)載量分擔(dān)到各個分支節(jié)點上，降低全局通信量進(jìn)而改善集群計算環(huán)境。隨著樹的深度的增加，使得集群更易于擴(kuò)展。但該集群實現(xiàn)起來比較復(fù)雜，且沒有專用的協(xié)議、應(yīng)用軟件或集群工具的支持[3]。樹型結(jié)構(gòu)的消息廣播和消息收集的時間復(fù)雜度均為O(logn)。
2.1.2 異構(gòu)環(huán)境下樹型計算系統(tǒng)
    在異構(gòu)環(huán)境下集群成員間彼此通信差異很大，有的使用廣域網(wǎng)技術(shù)通信，有的在局域網(wǎng)內(nèi)通信，還有的通信在機(jī)器內(nèi)部進(jìn)行，所有這些相互通信的進(jìn)程對之間的通信時間是不可能相等的。所以延用已有的計算系統(tǒng)不可能最優(yōu)。
    系統(tǒng)采用如圖2所示的樹型結(jié)構(gòu)，根節(jié)點為主控節(jié)點，葉子節(jié)點為計算節(jié)點（圖中圓形節(jié)點），此外還有路由節(jié)點（圖中方形節(jié)點）用于連接上下層節(jié)點或網(wǎng)絡(luò)，整個系統(tǒng)按通信速度分層，各層的通信速度從第0層到最后一層依次升高，第0層的通信最慢，最底層的通信最快。通常根據(jù)一般情況下節(jié)點機(jī)的計算速度或子網(wǎng)中延遲的大小來評定各節(jié)點機(jī)或子網(wǎng)通信速度的快慢。例如，對于集群子網(wǎng)中存在10 M以太網(wǎng)計算平臺、100 M以太網(wǎng)計算平臺和SMP節(jié)點機(jī)，顯然SMP是機(jī)內(nèi)通信，通信速度是三者之中最高的，應(yīng)放在最底層（圖中第3層）；10 M以太網(wǎng)的通信帶寬明顯低于100 M以太網(wǎng)，所以應(yīng)放在最上層（圖中第1層），100 M以太網(wǎng)的放在中間層（圖中第2層）。

2.2 OpenMP+MPI混合編程模型機(jī)制
    在前面提到，由于異構(gòu)環(huán)境下各節(jié)點機(jī)或計算平臺的粒度并行化程度不一，采用統(tǒng)一的編程方式勢必會顧此失彼，所以依據(jù)各節(jié)點機(jī)或計算平臺的實際情況，各取所長，采用混合編程MPI+OpenMP方式應(yīng)是較好的選擇[4]。
2.2.1 MPI編程方式
    MPI(Message Passing Interface)是消息傳遞接口的工業(yè)標(biāo)準(zhǔn)，為用戶提供一個實際可用、可移植、高效、靈活的消息傳遞接口庫。相對其他并行編程模型，由于其既可以在分布式系統(tǒng)又可以在共享內(nèi)存系統(tǒng)中運行，同時可以移植到包括NT和Unix在內(nèi)的幾乎所有系統(tǒng)，所以非常適合異構(gòu)環(huán)境下的集群通信。目前有關(guān)MPI的產(chǎn)品很多，主要有LAM/MPI、LA-MPI、FT-MPI和PACX-MPI，其中Open MPI結(jié)合了上述幾種工具的優(yōu)點，有望成為下一代MPI系統(tǒng)的主導(dǎo)者，它在異構(gòu)環(huán)境下的作業(yè)管理、異構(gòu)處理器、異構(gòu)網(wǎng)絡(luò)協(xié)議等方面提供了較為全面的技術(shù)支持，是目前對異構(gòu)計算環(huán)境支持較好的MPI實現(xiàn)系統(tǒng)。在本模型中，采用Open MPI集群工具，用于負(fù)責(zé)集群內(nèi)節(jié)點間通信。
2.2.2 OpenMP編程方式
    異構(gòu)環(huán)境中，對于擁有多核處理器的節(jié)點機(jī)或計算平臺，由于其采用共享存儲系統(tǒng)的方式來進(jìn)行計算和通信，采用MPI編程模式并不合適，其主要理由是：在該系統(tǒng)上MPI的消息傳送是通過存儲器中的共享消息緩沖區(qū)來實現(xiàn)的，所以對于較小的數(shù)據(jù)傳送量（粒度），其通信效率較低；而在進(jìn)行大塊的數(shù)據(jù)傳送時，通信效率則較好。但由于共享消息緩沖區(qū)的容量有限，所以當(dāng)通信量超過共享消息緩沖區(qū)的容量時，通信速率將下降。此外，一些MPI應(yīng)用需要特定數(shù)量的進(jìn)程運行，當(dāng)MPI所需進(jìn)程數(shù)與節(jié)點機(jī)處理器數(shù)不相等時，該系統(tǒng)將無法運行，進(jìn)而降低了節(jié)點機(jī)的利用率。所以在此系統(tǒng)下應(yīng)選擇基于共享存儲的編程方式，通過共享變量實現(xiàn)線程間通信和線程級并行。OpenMP是共享內(nèi)存編程的工業(yè)標(biāo)準(zhǔn)，它規(guī)范了一系列編譯制導(dǎo)、子程序庫和環(huán)境變量，采用 Fork-Join 的并行執(zhí)行模式實現(xiàn)線程級并行。制導(dǎo)語句提供對并行區(qū)域、工作共享的支持，且支持?jǐn)?shù)據(jù)私有化。在本模型中，采用OpenMP集群工具負(fù)責(zé)節(jié)點內(nèi)通信。
2.2.3 如何實現(xiàn)MPI與OpenMP的混合編程

    (1)原則上以MPI編程為主，OpenMP編程為輔，這樣才能更符合異構(gòu)環(huán)境的特點；
    (2)每個節(jié)點上都應(yīng)有MPI進(jìn)程，使得整個集群為一個MPI集群；
    (3)對于多核環(huán)境或SMP體系結(jié)構(gòu)的，MPI進(jìn)程中的計算部分(尤其是循環(huán)部分)應(yīng)交由OpenMP多線程并行求解(以嵌入編程方式實現(xiàn))；
    (4)OpenMP多線程求解部分可以與MPI進(jìn)程的局部計算、通信或同步操作穿插進(jìn)行；
    (5)OpenMP求解部分結(jié)束后，應(yīng)返回并繼續(xù)MPI進(jìn)程，直至MPI進(jìn)程結(jié)束。
2.3 路由節(jié)點的構(gòu)造
    樹形結(jié)構(gòu)中的分支節(jié)點用于連接根節(jié)點(主控節(jié)點)和葉子節(jié)點（計算節(jié)點），在整個集群中發(fā)揮兩個作用：一個是承上啟下的連接作用，另一個則是對根節(jié)點（主控節(jié)點）的分擔(dān)作用，所以分支節(jié)點應(yīng)具有路由和對消息的傳遞、分發(fā)和收集等功能。
    這里，以集群中采用統(tǒng)一的TCP/IP協(xié)議為例來構(gòu)造一個分支節(jié)點。首先在分支節(jié)點機(jī)上安裝兩塊網(wǎng)卡，一塊連接上層節(jié)點(根節(jié)點或上層的分支節(jié)點)，IP地址設(shè)置在上層節(jié)點的同一個網(wǎng)段內(nèi)，默認(rèn)網(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é)點機(jī)IP轉(zhuǎn)發(fā)功能生效。這樣做的目的是既能實現(xiàn)上下兩層網(wǎng)絡(luò)之間的通信，同時又能阻止基于網(wǎng)絡(luò)第二層的廣播幀的傳播。若集群中存在不同網(wǎng)絡(luò)協(xié)議，則在構(gòu)造分支節(jié)點機(jī)時，除了安裝兩塊網(wǎng)卡和相應(yīng)的網(wǎng)絡(luò)協(xié)議之外，還要依托MPI通信機(jī)制實現(xiàn)協(xié)議之間的通信。
2.4 進(jìn)程組和通信域的設(shè)計
    MPI中的通信域（Communicator）提供了一種組織和管理進(jìn)程間通信的方法。每個通信域包括一組MPI進(jìn)程，稱為進(jìn)程組。這一組進(jìn)程之間可以相互通信，而且這個通信域內(nèi)的通信不會跨越通信域的邊界。這樣就提供了一種安全的消息傳遞的機(jī)制，因為它隔離了內(nèi)部和外部的通信，避免了不必要的同步。每個進(jìn)程都至少在某個特定的通信域中，但有可能進(jìn)程在多個通信域中的情形，這就像某個人可以是多個組織的成員一樣。進(jìn)程組由一個進(jìn)程的有序序列進(jìn)行描述，每個進(jìn)程根據(jù)在序列中的位置被賦予一個進(jìn)程號（0，1，…，N-1）[5]。
    這里，將根節(jié)點與其相鄰的下一層節(jié)點（孩子節(jié)點）劃定為一個進(jìn)程組0，對分支節(jié)點1與其相鄰的下一層節(jié)點（孩子節(jié)點）劃定為進(jìn)程組1，…。如此類推，直到所有分支節(jié)點或根節(jié)點都擁有自己的進(jìn)程組為止，如圖3所示。由于每個分支節(jié)點或根節(jié)點都有兩塊網(wǎng)卡，所以將兩塊網(wǎng)卡分屬不同的進(jìn)程組中，彼此互不包含。

    這樣的設(shè)計將全局通信域劃分成若干個子通信域，使得大量的消息傳遞開銷限制在局部，大大降低了全局通信的頻率，從而提高了集群通信的性能。
2.5 組間通信
    進(jìn)程組劃分之后，形成相應(yīng)的通信域，規(guī)避了大量節(jié)點間同步所消耗的開銷，但進(jìn)程組之間也需要通信，根節(jié)點需要將消息逐層傳遞到葉子節(jié)點，同樣葉子節(jié)點所計算出來的結(jié)果也要逐層收集、規(guī)約到根節(jié)點，所以組間通信也是本系統(tǒng)實現(xiàn)的關(guān)鍵之一。
    這里，通過使用MPI組間通信函數(shù)(如MPI_Intercomm_
create()函數(shù))來實現(xiàn)組間消息的傳遞。
3 實驗測試與分析
3.1 實驗環(huán)境和方法
    本實驗將先后搭建兩種結(jié)構(gòu)的集群進(jìn)行測試。其測試環(huán)境如下：
    (1)第一種結(jié)構(gòu)為傳統(tǒng)的單層型MPI集群，其中有4個計算節(jié)點和1個主控節(jié)點，這4個計算節(jié)點分別由2個單核結(jié)構(gòu)節(jié)點和2個雙核結(jié)構(gòu)節(jié)點構(gòu)成，如圖4(a)所示。
    (2)第二種結(jié)構(gòu)為本文提出的樹型MPI+OpenMP集群，其中有4個計算節(jié)點、1個路由節(jié)點和1個主控節(jié)點（根節(jié)點），如圖4(b)所示。

    其中，每個單核節(jié)點包含一顆P Ⅳ處理器和2 GB內(nèi)存，每個雙核節(jié)點包含一顆奔騰雙核E2140處理器和2 GB內(nèi)存，操作系統(tǒng)采用Redhat Linux Enterprise 5，并行集群軟件為OPEN MPI 1.3+OpenMP。由于條件所限，加之實驗規(guī)模較小，所以本實驗采用MPI自帶的函數(shù)MPI_Wtime()來采集MPI計算的開始和結(jié)束時間，取二者的時間差作為程序的運行時間并對其進(jìn)行比較和分析，用MPI_Wtick()函數(shù)來監(jiān)測MPI_Wtime()返回結(jié)果的精度。
    在實驗用例設(shè)計上，考慮到兩種MPI集群的通信機(jī)制中的傳輸路徑不同，采用計算求解三對角方程組作為測試方案，主要測試通信和計算的平衡。
3.2 結(jié)果和分析
    兩種集群測試結(jié)果如表1所示?？梢姕y試結(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)中每個通信域的廣播和收集時間遠(yuǎn)遠(yuǎn)小于單層結(jié)構(gòu)的廣播和收集時間，從而抵消了分支節(jié)點處理消息的時間，所以樹型的整體運算時間明顯小于單層型的運算時間。當(dāng)消息大小為512 KB以后時，單層型的運算時間明顯高于樹型，這是因為雙核節(jié)點是基于共享存儲器來實現(xiàn)進(jìn)程間通信的。由于事先將共享存儲器的容量設(shè)定為512 KB，所以當(dāng)消息大小超過共享存儲器的容量之后，基于MPI的單層型集群的通信效率迅速下降，而樹型中的雙核節(jié)點是基于多線程共享機(jī)制的，當(dāng)消息增大時反而其優(yōu)勢更加明顯。

    由上分析，基于異構(gòu)環(huán)境下樹型計算系統(tǒng)是可行的。在該方案上構(gòu)建的MPI+OpenMP集群系統(tǒng)可以兼容各類計算平臺，各取所長，并使消息廣播和消息收集的通信速度明顯提高，全局通信流量明顯下降，從而提升了集群整體計算速度。同時，由于樹型結(jié)構(gòu)的特點，使得集群的擴(kuò)展更加輕松。盡管從理論上可知隨著節(jié)點數(shù)的增加，該類集群的優(yōu)勢將更加凸顯，但是由于實驗條件的限制，只能對集群通信系統(tǒng)做初步驗證，所以希望在未來的研發(fā)工作中能夠引入更科學(xué)的評測體系，不斷地論證和完善該系統(tǒng)，為傳統(tǒng)集群性能的升級改造提供一些幫助。
參考文獻(xiàn)
[1] 蔣艷凰，趙強利，盧宇彤.異構(gòu)環(huán)境下MPI通信技術(shù)研究[J].小型微型計算機(jī)系統(tǒng)，2009，30(9)：1724-1729.
[2] 劉洋，曹建文，李玉成.聚合通信模型的測試與分析[J]. 計算機(jī)工程與應(yīng)用，2006，42(9)：30-33.
[3] CHEN C P.The parallel computing technologies(PaCT-2003)[C].Seventh International Conference，2003：15-19.
[4] 趙永華，遲學(xué)斌.基于SMP集群的MPI+OpenMP混合編程模型及有效實現(xiàn)[J].微電子學(xué)與計算機(jī)，2005，22(10)：7-11.
[5] 莫則堯，袁國興.消息傳遞并行編程環(huán)境[M].北京：科學(xué)出版社，2001.