文獻(xiàn)標(biāo)識(shí)碼: A
文章編號(hào): 0258-7998(2011)12-0126-04
近年來(lái)隨著各種應(yīng)用計(jì)算需求的不斷增長(zhǎng),集群計(jì)算的規(guī)模也在不斷擴(kuò)大。然而集群規(guī)模的增大并不意味著絕對(duì)計(jì)算速度和并行效率的提升,其中影響并行應(yīng)用程序計(jì)算性能發(fā)揮的主要瓶頸之一是消息傳遞通信設(shè)計(jì)不理想或使用不合理,導(dǎo)致全局通信使用頻率過(guò)高,造成通信堵塞、各種操作的響應(yīng)時(shí)間持續(xù)延長(zhǎng)和計(jì)算性能的下降。有數(shù)據(jù)表明,在大多數(shù)集群通信中,聚合通信開(kāi)銷往往占據(jù)全部消息傳遞通信開(kāi)銷的80%以上。因此,合理調(diào)整消息傳遞中聚合通信機(jī)制、降低全局通信流量應(yīng)是改善現(xiàn)有集群計(jì)算環(huán)境的有效手段之一[1]。
本文基于MPI集群框架結(jié)構(gòu),通過(guò)分析單層型集群和樹(shù)型結(jié)構(gòu)集群的聚合通信原理,提出了一種采用樹(shù)型結(jié)構(gòu)的MPI集群系統(tǒng)設(shè)計(jì)方案,用以降低聚合通信的開(kāi)銷,改善集群計(jì)算環(huán)境,同時(shí)也為集群的擴(kuò)展提供更加靈活的手段。聚合通信包括很多全局操作(如廣播、同步、歸約、分發(fā)、收集)等,但很多聚合通信是由其他聚合通信的組合來(lái)實(shí)現(xiàn)的,本文選擇了有代表性的廣播和收集作為主要研究對(duì)象。
1 單層型結(jié)構(gòu)與樹(shù)型結(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ā)來(lái)的消息,以及系統(tǒng)認(rèn)證、網(wǎng)絡(luò)管理和遠(yuǎn)程控制等。
從屬節(jié)點(diǎn)的功能主要用于計(jì)算、接收主控節(jié)點(diǎn)發(fā)來(lái)的各種控制命令、數(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í),無(wú)論是一對(duì)多模式,多對(duì)多模式還是多對(duì)一模式,都要圍繞著主控節(jié)點(diǎn)進(jìn)行,使得集群中全局通信流量所占比重較大。當(dāng)集群節(jié)點(diǎn)數(shù)增加或計(jì)算量很大時(shí),網(wǎng)絡(luò)負(fù)載極易到達(dá)額定上限,使得主控節(jié)點(diǎn)無(wú)法正常運(yùn)行,計(jì)算性能下降。
單層型結(jié)構(gòu)的消息廣播和消息收集的時(shí)間復(fù)雜度均為:O(n)
1.2 樹(shù)型結(jié)構(gòu)介紹
樹(shù)型結(jié)構(gòu)是針對(duì)單層型結(jié)構(gòu)在消息廣播和消息收集方面速度慢、可擴(kuò)展性差的弱點(diǎn)而提出的新的消息傳輸結(jié)構(gòu)。圖2所示為典型的樹(shù)型結(jié)構(gòu),和單層型結(jié)構(gòu)一樣,樹(shù)型結(jié)構(gòu)也有主控節(jié)點(diǎn)(根節(jié)點(diǎn))和從屬節(jié)點(diǎn)(葉子節(jié)點(diǎn)),且功能與單層型結(jié)構(gòu)類似。不同的是,樹(shù)型結(jié)構(gòu)中還包含分支節(jié)點(diǎn),這些分支節(jié)點(diǎn)是樹(shù)的內(nèi)部節(jié)點(diǎn),沒(méi)有計(jì)算功能,也沒(méi)有系統(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)相互之間沒(méi)有建立直接的通信連接。
樹(shù)型結(jié)構(gòu)集群可以將全局通信域劃分為多個(gè)子通信域,并且可以將主控節(jié)點(diǎn)的負(fù)載量分擔(dān)到各個(gè)分支節(jié)點(diǎn)上,降低全局通信量進(jìn)而改善集群計(jì)算環(huán)境。同時(shí)隨著樹(shù)的深度增加,使得集群更易于擴(kuò)展。但該集群實(shí)現(xiàn)起來(lái)比較復(fù)雜,且沒(méi)有專用的協(xié)議、應(yīng)用軟件或集群工具的支持[3]。
樹(shù)型結(jié)構(gòu)的消息廣播和消息收集的時(shí)間復(fù)雜度均為:O(logn)
2 樹(shù)型MPI的設(shè)計(jì)與實(shí)現(xiàn)
雖然使用樹(shù)型結(jié)構(gòu)的集群系統(tǒng)可以改善聚合通信的效率,但其實(shí)現(xiàn)起來(lái)則相對(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)樹(shù)型結(jié)構(gòu)的MPI集群系統(tǒng)設(shè)計(jì)方案。這里需要注意以下問(wèn)題:
(1)根節(jié)點(diǎn)的設(shè)計(jì)
在構(gòu)建集群網(wǎng)絡(luò)時(shí),網(wǎng)絡(luò)安全和通信效率既相互依賴又相互制衡。若省去頻繁的核實(shí)用戶身份等安全方面的檢查,則可以省去一部分系統(tǒng)開(kāi)銷,進(jìn)而提高網(wǎng)絡(luò)通信效率,但集群網(wǎng)絡(luò)的安全性就無(wú)法保障;同樣,若犧牲通信效率而實(shí)現(xiàn)網(wǎng)絡(luò)安全,則集群計(jì)算的優(yōu)勢(shì)將無(wú)法體現(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)證等安全方面的開(kāi)銷,從而為通信效率的提升留出空間。
根節(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ì)
樹(shù)形結(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ī)之間的通信通過(guò)IP訪問(wèn)來(lái)實(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)境可以通過(guò)此域名來(lái)區(qū)分、訪問(wèn)運(yùn)行在各個(gè)節(jié)點(diǎn)機(jī)上的進(jìn)程(如MPI_Get_processor_name()函數(shù))。
對(duì)于集群系統(tǒng)來(lái)說(shuō),集群中所有節(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命令)提供無(wú)口令遠(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è)子通信域,使得大量的消息傳遞開(kāi)銷被限制在局部范圍內(nèi),大大降低了全局通信的頻率,從而提高了集群通信的性能。
(5)組間通信
進(jìn)程組劃分之后,形成相應(yīng)的通信域,規(guī)避了大量節(jié)點(diǎn)間同步所消耗的開(kāi)銷。但進(jìn)程組之間也要進(jìn)行通信,根節(jié)點(diǎn)需要將消息逐層傳遞到葉子節(jié)點(diǎn),同樣葉子節(jié)點(diǎn)所計(jì)算出來(lái)的結(jié)果也是要逐層收集、規(guī)約到根節(jié)點(diǎn),所以組間通信也是本系統(tǒng)實(shí)現(xiàn)的關(guān)鍵之一。這里,通過(guò)使用MPI組間通信函數(shù)(如MPI_Intercomm_create()函數(shù))來(lái)實(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)額外的開(kāi)銷。設(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)的集群,單層型和樹(shù)型集群均由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)成,而樹(shù)型結(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);右圖為樹(shù)型集群,擁有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()來(lái)采集MPI計(jì)算的開(kāi)始和結(jié)束時(shí)間,取兩者的時(shí)間差作為程序的運(yùn)行時(shí)間,并對(duì)其進(jìn)行比較和分析,用MPI_Wtick()函數(shù)來(lái)監(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í)間沒(méi)有明顯差別,這是由于它們都擁有1個(gè)主控節(jié)點(diǎn)和2個(gè)計(jì)算節(jié)點(diǎn)。雖然樹(shù)型結(jié)構(gòu)在MPI聚合通信機(jī)制上有所改動(dòng),但影響有限,測(cè)試的結(jié)果基本相同。對(duì)于第二組的測(cè)試,測(cè)試結(jié)果差異較明顯,在傳輸短消息時(shí),可以發(fā)現(xiàn)單層型集群的運(yùn)算速度并不比樹(shù)型慢多少, 在16 B的情況單層型還優(yōu)于樹(shù)型。這是因?yàn)闃?shù)型結(jié)構(gòu)的集群中除了擁有和單層型相同數(shù)目的計(jì)算節(jié)點(diǎn)外,還有兩個(gè)分支節(jié)點(diǎn)(也叫路由節(jié)點(diǎn)),分支節(jié)點(diǎn)需要在兩個(gè)通信域之間傳遞處理消息,需要處理時(shí)間,所以樹(shù)型結(jié)構(gòu)的消息傳輸時(shí)間除了消息廣播和收集時(shí)間外,還有域間轉(zhuǎn)發(fā)處理的時(shí)間。盡管在時(shí)間復(fù)雜度上樹(shù)型結(jié)構(gòu)優(yōu)于單層型結(jié)構(gòu),但在通信域中節(jié)點(diǎn)數(shù)較少、消息較小的情況下,兩者之間差距不是十分明顯,若再加上域間處理的時(shí)間,自然會(huì)出現(xiàn)這樣的情況。但當(dāng)消息增大時(shí),由于樹(shù)型結(jié)構(gòu)中每個(gè)通信域的廣播和收集時(shí)間遠(yuǎn)遠(yuǎn)小于單層結(jié)構(gòu)的廣播和收集時(shí)間,從而抵消了分支節(jié)點(diǎn)處理消息的時(shí)間,所以樹(shù)型的整體運(yùn)算時(shí)間明顯小于單層型的運(yùn)算時(shí)間。對(duì)于第三組的測(cè)試,樹(shù)型的整體運(yùn)算時(shí)間明顯優(yōu)于單層型集群,幾乎相當(dāng)于同級(jí)別單層型集群的1/2。這是由于隨著計(jì)算節(jié)點(diǎn)的增加,樹(shù)型MPI集群的優(yōu)勢(shì)明顯發(fā)揮出來(lái),尤其是聚合通信方面。
由上分析表明,基于樹(shù)型MPI并行計(jì)算集群的設(shè)計(jì)方案是可行的。在該方案上構(gòu)建的MPI集群系統(tǒng)可以使消息廣播和消息收集的速度明顯提高,使得全局通信使用頻率明顯下降,從而提升了集群整體計(jì)算速度。同時(shí),由于樹(shù)型結(jié)構(gòu)的特點(diǎn),使得集群的擴(kuò)展更加輕松。盡管從理論上可知隨著節(jié)點(diǎn)數(shù)的增加樹(shù)型MPI的集群的優(yōu)勢(shì)將更加凸顯,但是由于實(shí)驗(yàn)條件的限制,只能對(duì)集群通信系統(tǒng)做初步驗(yàn)證。所以希望在未來(lái)的研發(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.