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

    近年來，為了滿足不斷增長(zhǎng)的計(jì)算能力的需求，將已有的若干個(gè)不同的計(jì)算平臺(tái)(計(jì)算主機(jī)或計(jì)算網(wǎng)絡(luò))互連并改造成高性能集群系統(tǒng)是一種性價(jià)比較高的實(shí)現(xiàn)方式。然而集群規(guī)模的增大并沒有帶來絕對(duì)計(jì)算速度和并行效率的提升，伴隨而來的卻是全局通信（尤其是組通信）流量猛增，網(wǎng)絡(luò)堵塞嚴(yán)重，操作響應(yīng)遲滯，以至計(jì)算性能下降。
1 分析問題
    經(jīng)過對(duì)此類異構(gòu)集群的研究和分析，計(jì)算系統(tǒng)設(shè)計(jì)的不合理應(yīng)是造成該集群計(jì)算性能下降的主要原因之一。其理由是：在現(xiàn)有的計(jì)算系統(tǒng)中，大多是在不考慮集群網(wǎng)絡(luò)或處理機(jī)的性能差異的情況下對(duì)網(wǎng)絡(luò)進(jìn)行模型化，然后在此模型及其參數(shù)值基礎(chǔ)上構(gòu)造出最優(yōu)算法來實(shí)現(xiàn)通信。這樣的方法固然能夠定量地分析算法的描述精度，更能精確地給出通信時(shí)間的統(tǒng)計(jì)公式，這對(duì)計(jì)算系統(tǒng)的分析和設(shè)計(jì)是有指導(dǎo)意義的，但同時(shí)也存在著一些問題，就是它們假定計(jì)算中的所有進(jìn)程對(duì)(發(fā)送進(jìn)程和接收進(jìn)程稱為進(jìn)程對(duì))之間的通信時(shí)間都是相等的。而實(shí)際情況卻并非如此，不同的處理器速度、不同的內(nèi)部結(jié)構(gòu)（單核或多核）以及集群內(nèi)部存在著不同類型的網(wǎng)絡(luò)和不同的連接方式，這些都會(huì)造成通信延遲的差異，所以此種模型構(gòu)造出的集群系統(tǒng)與實(shí)際應(yīng)用是有差距的。具體表現(xiàn)在應(yīng)用的透明性不足[1]、集群框架結(jié)構(gòu)[2]和編程模型的選用不合理。
2 解決問題
    解決問題思路就是在粒度、通信開銷和計(jì)算資源三者之間尋找最佳平衡點(diǎn)，并以此平衡點(diǎn)來組織集群，以達(dá)到性能提升的目的。本文將具體的網(wǎng)絡(luò)拓?fù)湫畔⒆鳛橹饕Ｒ罁?jù)，提出了一種基于異構(gòu)集群環(huán)境下采用樹型結(jié)構(gòu)的計(jì)算系統(tǒng)，用以確定適合并行任務(wù)的粒度、降低通信開銷和提高計(jì)算資源利用率，進(jìn)而改善集群計(jì)算環(huán)境。
2.1 樹型組通信系統(tǒng)的提出
2.1.1 樹型結(jié)構(gòu)介紹
    樹型結(jié)構(gòu)是針對(duì)單層型結(jié)構(gòu)在消息廣播和消息收集方面速度慢、可擴(kuò)展性差的弱點(diǎn)而提出的新的集群框架結(jié)構(gòu)。圖1所示的是典型的樹型結(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)。如圖1所示，根節(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)境。隨著樹的深度的增加，使得集群更易于擴(kuò)展。但該集群實(shí)現(xiàn)起來比較復(fù)雜，且沒有專用的協(xié)議、應(yīng)用軟件或集群工具的支持[3]。樹型結(jié)構(gòu)的消息廣播和消息收集的時(shí)間復(fù)雜度均為O(logn)。
2.1.2 異構(gòu)環(huán)境下樹型計(jì)算系統(tǒng)
    在異構(gòu)環(huán)境下集群成員間彼此通信差異很大，有的使用廣域網(wǎng)技術(shù)通信，有的在局域網(wǎng)內(nèi)通信，還有的通信在機(jī)器內(nèi)部進(jìn)行，所有這些相互通信的進(jìn)程對(duì)之間的通信時(shí)間是不可能相等的。所以延用已有的計(jì)算系統(tǒng)不可能最優(yōu)。
    系統(tǒng)采用如圖2所示的樹型結(jié)構(gòu)，根節(jié)點(diǎn)為主控節(jié)點(diǎn)，葉子節(jié)點(diǎn)為計(jì)算節(jié)點(diǎn)（圖中圓形節(jié)點(diǎn)），此外還有路由節(jié)點(diǎn)（圖中方形節(jié)點(diǎn)）用于連接上下層節(jié)點(diǎn)或網(wǎng)絡(luò)，整個(gè)系統(tǒng)按通信速度分層，各層的通信速度從第0層到最后一層依次升高，第0層的通信最慢，最底層的通信最快。通常根據(jù)一般情況下節(jié)點(diǎn)機(jī)的計(jì)算速度或子網(wǎng)中延遲的大小來評(píng)定各節(jié)點(diǎn)機(jī)或子網(wǎng)通信速度的快慢。例如，對(duì)于集群子網(wǎng)中存在10 M以太網(wǎng)計(jì)算平臺(tái)、100 M以太網(wǎng)計(jì)算平臺(tái)和SMP節(jié)點(diǎn)機(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é)點(diǎn)機(jī)或計(jì)算平臺(tái)的粒度并行化程度不一，采用統(tǒng)一的編程方式勢(shì)必會(huì)顧此失彼，所以依據(jù)各節(jié)點(diǎn)機(jī)或計(jì)算平臺(tái)的實(shí)際情況，各取所長(zhǎng)，采用混合編程MPI+OpenMP方式應(yīng)是較好的選擇[4]。
2.2.1 MPI編程方式
    MPI(Message Passing Interface)是消息傳遞接口的工業(yè)標(biāo)準(zhǔn)，為用戶提供一個(gè)實(shí)際可用、可移植、高效、靈活的消息傳遞接口庫。相對(duì)其他并行編程模型，由于其既可以在分布式系統(tǒng)又可以在共享內(nèi)存系統(tǒng)中運(yùn)行，同時(shí)可以移植到包括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)點(diǎn)，有望成為下一代MPI系統(tǒng)的主導(dǎo)者，它在異構(gòu)環(huán)境下的作業(yè)管理、異構(gòu)處理器、異構(gòu)網(wǎng)絡(luò)協(xié)議等方面提供了較為全面的技術(shù)支持，是目前對(duì)異構(gòu)計(jì)算環(huán)境支持較好的MPI實(shí)現(xiàn)系統(tǒng)。在本模型中，采用Open MPI集群工具，用于負(fù)責(zé)集群內(nèi)節(jié)點(diǎn)間通信。
2.2.2 OpenMP編程方式
    異構(gòu)環(huán)境中，對(duì)于擁有多核處理器的節(jié)點(diǎn)機(jī)或計(jì)算平臺(tái)，由于其采用共享存儲(chǔ)系統(tǒng)的方式來進(jìn)行計(jì)算和通信，采用MPI編程模式并不合適，其主要理由是：在該系統(tǒng)上MPI的消息傳送是通過存儲(chǔ)器中的共享消息緩沖區(qū)來實(shí)現(xiàn)的，所以對(duì)于較小的數(shù)據(jù)傳送量（粒度），其通信效率較低；而在進(jìn)行大塊的數(shù)據(jù)傳送時(shí)，通信效率則較好。但由于共享消息緩沖區(qū)的容量有限，所以當(dāng)通信量超過共享消息緩沖區(qū)的容量時(shí)，通信速率將下降。此外，一些MPI應(yīng)用需要特定數(shù)量的進(jìn)程運(yùn)行，當(dāng)MPI所需進(jìn)程數(shù)與節(jié)點(diǎn)機(jī)處理器數(shù)不相等時(shí)，該系統(tǒng)將無法運(yùn)行，進(jìn)而降低了節(jié)點(diǎn)機(jī)的利用率。所以在此系統(tǒng)下應(yīng)選擇基于共享存儲(chǔ)的編程方式，通過共享變量實(shí)現(xiàn)線程間通信和線程級(jí)并行。OpenMP是共享內(nèi)存編程的工業(yè)標(biāo)準(zhǔn)，它規(guī)范了一系列編譯制導(dǎo)、子程序庫和環(huán)境變量，采用 Fork-Join 的并行執(zhí)行模式實(shí)現(xiàn)線程級(jí)并行。制導(dǎo)語句提供對(duì)并行區(qū)域、工作共享的支持，且支持?jǐn)?shù)據(jù)私有化。在本模型中，采用OpenMP集群工具負(fù)責(zé)節(jié)點(diǎn)內(nèi)通信。
2.2.3 如何實(shí)現(xiàn)MPI與OpenMP的混合編程

    (1)原則上以MPI編程為主，OpenMP編程為輔，這樣才能更符合異構(gòu)環(huán)境的特點(diǎn)；
    (2)每個(gè)節(jié)點(diǎn)上都應(yīng)有MPI進(jìn)程，使得整個(gè)集群為一個(gè)MPI集群；
    (3)對(duì)于多核環(huán)境或SMP體系結(jié)構(gòu)的，MPI進(jìn)程中的計(jì)算部分(尤其是循環(huán)部分)應(yīng)交由OpenMP多線程并行求解(以嵌入編程方式實(shí)現(xiàn))；
    (4)OpenMP多線程求解部分可以與MPI進(jìn)程的局部計(jì)算、通信或同步操作穿插進(jìn)行；
    (5)OpenMP求解部分結(jié)束后，應(yīng)返回并繼續(xù)MPI進(jìn)程，直至MPI進(jìn)程結(jié)束。
2.3 路由節(jié)點(diǎn)的構(gòu)造
    樹形結(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ā)和收集等功能。
    這里，以集群中采用統(tǒng)一的TCP/IP協(xié)議為例來構(gòu)造一個(gè)分支節(jié)點(diǎn)。首先在分支節(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ò)第二層的廣播幀的傳播。若集群中存在不同網(wǎng)絡(luò)協(xié)議，則在構(gòu)造分支節(jié)點(diǎn)機(jī)時(shí)，除了安裝兩塊網(wǎng)卡和相應(yīng)的網(wǎng)絡(luò)協(xié)議之外，還要依托MPI通信機(jī)制實(shí)現(xiàn)協(xié)議之間的通信。
2.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）[5]。
    這里，將根節(jié)點(diǎn)與其相鄰的下一層節(jié)點(diǎn)（孩子節(jié)點(diǎn)）劃定為一個(gè)進(jìn)程組0，對(duì)分支節(jié)點(diǎn)1與其相鄰的下一層節(jié)點(diǎn)（孩子節(jié)點(diǎn)）劃定為進(jìn)程組1，…。如此類推，直到所有分支節(jié)點(diǎn)或根節(jié)點(diǎn)都擁有自己的進(jìn)程組為止，如圖3所示。由于每個(gè)分支節(jié)點(diǎn)或根節(jié)點(diǎn)都有兩塊網(wǎng)卡，所以將兩塊網(wǎng)卡分屬不同的進(jìn)程組中，彼此互不包含。

    這樣的設(shè)計(jì)將全局通信域劃分成若干個(gè)子通信域，使得大量的消息傳遞開銷限制在局部，大大降低了全局通信的頻率，從而提高了集群通信的性能。
2.5 組間通信
    進(jìn)程組劃分之后，形成相應(yīng)的通信域，規(guī)避了大量節(jié)點(diǎ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)組間消息的傳遞。
3 實(shí)驗(yàn)測(cè)試與分析
3.1 實(shí)驗(yàn)環(huán)境和方法
    本實(shí)驗(yàn)將先后搭建兩種結(jié)構(gòu)的集群進(jìn)行測(cè)試。其測(cè)試環(huán)境如下：
    (1)第一種結(jié)構(gòu)為傳統(tǒng)的單層型MPI集群，其中有4個(gè)計(jì)算節(jié)點(diǎn)和1個(gè)主控節(jié)點(diǎn)，這4個(gè)計(jì)算節(jié)點(diǎn)分別由2個(gè)單核結(jié)構(gòu)節(jié)點(diǎn)和2個(gè)雙核結(jié)構(gòu)節(jié)點(diǎn)構(gòu)成，如圖4(a)所示。
    (2)第二種結(jié)構(gòu)為本文提出的樹型MPI+OpenMP集群，其中有4個(gè)計(jì)算節(jié)點(diǎn)、1個(gè)路由節(jié)點(diǎn)和1個(gè)主控節(jié)點(diǎn)（根節(jié)點(diǎn)），如圖4(b)所示。

    其中，每個(gè)單核節(jié)點(diǎn)包含一顆P Ⅳ處理器和2 GB內(nèi)存，每個(gè)雙核節(jié)點(diǎn)包含一顆奔騰雙核E2140處理器和2 GB內(nèi)存，操作系統(tǒng)采用Redhat Linux Enterprise 5，并行集群軟件為OPEN MPI 1.3+OpenMP。由于條件所限，加之實(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 結(jié)果和分析
    兩種集群測(cè)試結(jié)果如表1所示?？梢姕y(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)需要時(shí)間在兩個(gè)通信域之間傳遞處理消息，所以樹型結(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í)間。當(dāng)消息大小為512 KB以后時(shí)，單層型的運(yùn)算時(shí)間明顯高于樹型，這是因?yàn)殡p核節(jié)點(diǎn)是基于共享存儲(chǔ)器來實(shí)現(xiàn)進(jìn)程間通信的。由于事先將共享存儲(chǔ)器的容量設(shè)定為512 KB，所以當(dāng)消息大小超過共享存儲(chǔ)器的容量之后，基于MPI的單層型集群的通信效率迅速下降，而樹型中的雙核節(jié)點(diǎn)是基于多線程共享機(jī)制的，當(dāng)消息增大時(shí)反而其優(yōu)勢(shì)更加明顯。

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