基于Scilab的分布式并行計算方法的研究

1、第22卷第10期計算機(jī)應(yīng)用與軟件 Vol.22,No.10 2005年10月Computer Applications and Software Oct. 2005基于Scilab的分布式并行計算方法的研究張志立1,2張冬1齊德昱11(華南理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院 廣東 廣州 5106402(許昌學(xué)院網(wǎng)絡(luò)中心 河南 許昌 461000摘 要文章利用Scilab構(gòu)建分布并行計算的支撐環(huán)境,為實(shí)現(xiàn)分布并行計算提供了新方法。設(shè)計了Netbutterfly Grid ComputingSystem(NGCS,討論了NGCS的體系結(jié)構(gòu),任務(wù)分布、系統(tǒng)通信和容錯機(jī)制等關(guān)鍵問題。最后給出網(wǎng)格計算環(huán)境下基

2、于Scilab的一個分布并行計算實(shí)例,實(shí)驗(yàn)的結(jié)果是令人滿意的。關(guān)鍵詞分布并行計算網(wǎng)格計算 Scilab Globus toolkitTHE RESEARCH OF DISTRIBUTED PARALLEL COMPUTING METHOD ON SCILABZhang Zhili1,2 Zhang Dong1 Qi Deyu11(College of Computer Science and Engineering, South China Univ. of Tech., Guangzhou Guangdong 510640, China2(Center of Network, Xuchang

3、 University, Xuchang Henan 461000, ChinaAbstract The paper focuses on the implements of distributed parallel computing on Scilab, a wide-used grid environment. Netbutterfly Grid ComputingSystem(NGCS is designed, Some of key issues, such as the architecture of NGCS, job distributing, system communica

4、tions and fault tolerance are analyzed anddiscussed. And a new science computing method is advanced. Finally, an example on grid computing environments is presented. The experiment shows that its theresults are satisfying.Keywords Distributed parallel computing Grid computing Scilab Globus toolkit1引

5、 言隨著計算機(jī)和互聯(lián)網(wǎng)技術(shù)的出現(xiàn)和迅速發(fā)展,科學(xué)與工程計算獲得了廣泛的應(yīng)用,它是計算機(jī)在科學(xué)與高技術(shù)領(lǐng)域應(yīng)用的必不可少的工具,并且已經(jīng)成為科學(xué)研究的一個重要的方向,是20世紀(jì)最重要的科技進(jìn)步之一。利用Internet上現(xiàn)有的計算資源開發(fā)分布式并行計算系統(tǒng)有著巨大的潛在價值, 現(xiàn)有并行計算的實(shí)現(xiàn)主要有兩種方式:(1并行計算機(jī)方式:并行計算機(jī)可分為緊耦合和松耦合方式兩類。實(shí)現(xiàn)這種傳統(tǒng)并行計算的問題是代價太高,難以實(shí)現(xiàn),不適合一般的應(yīng)用。(2網(wǎng)絡(luò)并行計算系統(tǒng)方式:由一組互聯(lián)的同構(gòu)或異構(gòu)計算單元和相關(guān)資源組成,可被用戶視為單一的計算環(huán)境來完成并行計算1。其最典型的代表是PVM。這類系統(tǒng)最嚴(yán)重的問題是只

6、考慮處理機(jī)能力的異構(gòu),很難解決操作系統(tǒng)、協(xié)議等方面的異構(gòu)性。網(wǎng)格是剛剛興起的計算環(huán)境,它支持高性能計算和高度的資源共享2。用網(wǎng)格實(shí)現(xiàn)大規(guī)模分布并行計算是必然的趨勢,將為大規(guī)?？茖W(xué)與工程計算開辟一個新的領(lǐng)域。然而,目前的一些網(wǎng)格環(huán)境,如OGSA/Globus,距離直接支持分布并行計算還很遙遠(yuǎn),對于一般用戶來說,廉價易用的分布式并行計算環(huán)境是進(jìn)行大規(guī)?？茖W(xué)計算最有效的實(shí)現(xiàn)平臺。因此,討論在現(xiàn)有網(wǎng)格環(huán)境下如何實(shí)現(xiàn)分布并行計算仍然是十分必要的?；赟cilab3運(yùn)算引擎,以O(shè)GSA/Globus為背景,我們設(shè)計開發(fā)了網(wǎng)格環(huán)境下分布式并行計算工具Netbutterfly Grid Computing S

7、ystem(簡稱NGCS,分析了分布并行計算存在的關(guān)鍵問題,并提出了相應(yīng)的解決方法。2基于Scilab的分布并行計算2.1NGCS的分布并行計算結(jié)構(gòu)如圖1所示,由多個提供網(wǎng)格服務(wù)的網(wǎng)格計算節(jié)點(diǎn)組成一個虛擬的并行機(jī),它可以完成由網(wǎng)格客戶提交的并行計算任務(wù)。每個網(wǎng)格計算節(jié)點(diǎn)即并行計算的一個節(jié)點(diǎn),提供一個或一些可以并行執(zhí)行子任務(wù)的并行網(wǎng)格服務(wù)。作為對運(yùn)算資源的完整封裝,網(wǎng)格計算節(jié)點(diǎn)用來完成具體的計算任務(wù),它使用Scilab作為算法描述語言,可以降低使用者描述科學(xué)計算問題的難度。計算服務(wù)層(虛擬并行機(jī)抽象了計算能力,當(dāng)計算任務(wù)被接受時,它就會自動尋找適合的計算資源來完成。應(yīng)用層主要是用圖1 NGCS層

8、次結(jié)構(gòu)圖 24 計算機(jī)應(yīng)用與軟件 2005年來對計算服務(wù)進(jìn)行有效使用和管理,處理多應(yīng)用協(xié)調(diào)等問題、通過網(wǎng)格中間件Globus Toolkit并行地調(diào)用網(wǎng)格服務(wù)實(shí)例等。與傳統(tǒng)意義上的并行機(jī)和網(wǎng)絡(luò)并行實(shí)現(xiàn)方式相比,其最大的優(yōu)點(diǎn)是,充分利用互聯(lián)網(wǎng)上的資源實(shí)現(xiàn)大型問題的分布并行計算,可以解決處理機(jī)能力、操作系統(tǒng)等方面的異構(gòu)性,可以利用網(wǎng)格基礎(chǔ)設(shè)施作為分布并行計算的編程環(huán)境,及其實(shí)現(xiàn)的簡單性。2.2NGCS設(shè)計架構(gòu)(1NGCS應(yīng)用結(jié)構(gòu)模型如圖2所示,數(shù)據(jù)容器主要存放并行程序和應(yīng)用數(shù)據(jù);運(yùn)算容器包括N個資源節(jié)點(diǎn),為系統(tǒng)提供計算能力;資源目錄服務(wù)包括運(yùn)算資源服務(wù)和數(shù)據(jù)資源服務(wù);NGCS運(yùn)行時節(jié)點(diǎn)把編輯好的任

9、務(wù)提交到數(shù)據(jù)容器,數(shù)據(jù)容器與運(yùn)算容器進(jìn)行交互完成任務(wù),在此過程中數(shù)據(jù)容器和運(yùn)算容器通過目錄服務(wù)來發(fā)現(xiàn)所需資源,直到運(yùn)算完成。 圖2 NGCS應(yīng)用結(jié)構(gòu)模型(2服務(wù)器系統(tǒng)設(shè)計NGCS在物理實(shí)現(xiàn)上采用了核心服務(wù)器組結(jié)構(gòu),客戶端即是資源提供者又是資源調(diào)用者,系統(tǒng)內(nèi)的計算資源來自于對客戶端資源的有效聚集。NGCS的服務(wù)器采用可擴(kuò)展的集群設(shè)計,各個模塊可以分別運(yùn)行。服務(wù)器組結(jié)構(gòu)如圖3所示。它的優(yōu)點(diǎn)是可擴(kuò)展性好,負(fù)載量大,可以適當(dāng)冗余,可靠性高。服務(wù)器主要完成的工作是任務(wù)和資源的組織和調(diào)度。(3客戶節(jié)點(diǎn)設(shè)計NGCS的客戶節(jié)點(diǎn)包括任務(wù)接入界面和Scilab網(wǎng)格計算虛擬機(jī)。任務(wù)接入界面是用戶申請進(jìn)入NGCS的接

10、口,用戶通過任務(wù)接入界面把任務(wù)提交到 NGCS系統(tǒng);Scilab網(wǎng)格計算虛擬機(jī)是NGCS的運(yùn)算節(jié)點(diǎn),它為系統(tǒng)提供運(yùn)算能力?？蛻艄?jié)點(diǎn)分任務(wù)模式和計算模式。前者為節(jié)點(diǎn)向系統(tǒng)提交計算任務(wù)并等待系統(tǒng)完成的過程,后者為節(jié)點(diǎn)向系統(tǒng)提供計算服務(wù)。由于每個客戶節(jié)點(diǎn)是用Globus Toolkit構(gòu)建的網(wǎng)格節(jié)點(diǎn),所以,它支持從微機(jī)到巨型機(jī)的任何機(jī)種, 從Windows到Unix和Linux以及將來可能出現(xiàn)的任何操作系統(tǒng),極大的便利了異種機(jī)間的網(wǎng)絡(luò)并行,從而可以充分地利用現(xiàn)有的網(wǎng)絡(luò)資源進(jìn)行分布并行計算。2.3系統(tǒng)編碼設(shè)計本系統(tǒng)采用了Scilab語言作為科學(xué)計算腳本描述語言。Scilab是由法國國立自動化研究院(I

11、NRIA和ENPC開發(fā)的“開放源碼”軟件,使用Scilab作為應(yīng)用腳本語言有利于計算任務(wù)的快捷描述和使用者的快速掌握,從而提高了使用者對科學(xué)計算問題的描述效率。由于NGCS的應(yīng)用程序采用了解釋執(zhí)行的方式,使得NGCS的應(yīng)用腳本可以在不同平臺的NGCS節(jié)點(diǎn)直接運(yùn)行,在不同操作系統(tǒng)節(jié)點(diǎn)中共同運(yùn)行一個并行程序,具有良好的異構(gòu)擴(kuò)展特性。為了使Scilab適用于網(wǎng)絡(luò)化的并行計算,系統(tǒng)增加了遠(yuǎn)程數(shù)據(jù)讀寫指令NGCS_RD和NGCS_WR,去掉了磁盤操作等可能危害客戶機(jī)的危險指令。整個運(yùn)算程序的入口是main.ngcs 文件,其它程序作為過程被調(diào)用。Main.ngcs是一個描述任務(wù)流的文件,語法上只有2個關(guān)

12、鍵字NGCS_CX和NGCS_END。NGCS_CX: 程序的條件執(zhí)行,當(dāng)表達(dá)式X為真時,系統(tǒng)并行執(zhí)行NGCS_CX語句內(nèi)的所有函數(shù);NGCS_END:運(yùn)算結(jié)束,此條指令一般用來結(jié)束系統(tǒng)任務(wù),系統(tǒng)執(zhí)行到此語句時對所分配資源進(jìn)行釋放,應(yīng)用完成。當(dāng)表達(dá)式X為真時,整個運(yùn)算任務(wù)結(jié)束,向任務(wù)提交者發(fā)出結(jié)束標(biāo)志,注銷資源節(jié)點(diǎn)緩沖區(qū)。2.4關(guān)鍵技術(shù)問題的討論(1任務(wù)并行傳統(tǒng)的并行計算模型一般都是基于數(shù)據(jù)并行的,數(shù)據(jù)并行的并行度較高但難于處理不規(guī)則問題,而基于功能并行的計算模型,對非規(guī)則問題的處理能力較好。NGCS并行調(diào)度語言,對任務(wù)關(guān)系進(jìn)行描述,將人們對問題的分解自然的對應(yīng)為程序中的各級任務(wù),并行編程自然

13、、清晰;同時,任務(wù)并行綜合了數(shù)據(jù)并行和功能并行的優(yōu)勢,在支持較高并行度的前提下,能夠有效地處理不規(guī)則問題,可以較方便地將串行程序改寫為并行程序。系統(tǒng)把數(shù)據(jù)和操作封裝成不同的任務(wù)以實(shí)現(xiàn)并行化:當(dāng)多個任務(wù)具有相同操作、不同數(shù)據(jù)時實(shí)現(xiàn)數(shù)據(jù)并行;當(dāng)多個任務(wù)具有不同操作時實(shí)現(xiàn)功能并行4。每個任務(wù)被分布到一個網(wǎng)格節(jié)點(diǎn)?；赟cilab的分布并行計算可以擴(kuò)展并行計算環(huán)境到以GLOBUS網(wǎng)格節(jié)點(diǎn)為并行計算節(jié)點(diǎn)的廣域網(wǎng)絡(luò)中,這樣,可并行計算的任務(wù)能被分布到網(wǎng)格上多個計算資源上,系統(tǒng)的性能將大大提高。(2系統(tǒng)通信系統(tǒng)通信涉及兩個方面:一個是并行計算節(jié)點(diǎn)之間的通信,主要是完成并行計算的各網(wǎng)格計算節(jié)點(diǎn)上的網(wǎng)格服務(wù)之間

14、的數(shù)據(jù)通信和同步信息交流;另一個是網(wǎng)格服務(wù)與客戶之間通信。可以用來實(shí)現(xiàn)網(wǎng)格服務(wù)之間通信和網(wǎng)格服務(wù)與客戶的通信。通信機(jī)制有兩種實(shí)現(xiàn)方法:Pull方法和Push方法5。其中Push方法允許數(shù)據(jù)和通知一起傳輸,這種通信方式效率高,對于并行計算這種性能優(yōu)先的需求來說,可以采用這種方式。此外,由于現(xiàn)有的網(wǎng)格服務(wù)是基于TCP/IP協(xié)議這種底層通信方式,因此,通信效率較高。為了實(shí)現(xiàn)NGCS在Internet下的通信,NGCS采用了SOAP1.2標(biāo)準(zhǔn)并對其進(jìn)行封裝。SOAP v1.2為在一個松散的、分布的環(huán)境中使用XML對等地交換結(jié)構(gòu)化和類型化的信息提供了一個簡單且輕量級的機(jī)制6。SOAP本身并不定義任何應(yīng)用

15、語義,它只是定義了一種簡單的機(jī)制,通過一個模塊化的包裝模型和特定格式編碼數(shù)據(jù)的重編碼機(jī)制來表示應(yīng)用語義。SOAP 的這項能力使得它可被很多類型的系統(tǒng)用于從消息系統(tǒng)到 圖3 NGCS服務(wù)器組第10期張志立等:基于Scilab的分布式并行計算方法的研究 25RPC(Remote Procedure Call的延伸。NGCS擴(kuò)展了Scilab,對Soap進(jìn)行了封裝,在Scilab中加入了SOAP_EG的數(shù)據(jù)操作指令NGCS_ SOAPEG,使得用戶可以訪問系統(tǒng)各數(shù)據(jù)緩存中的數(shù)據(jù)信息,實(shí)現(xiàn)了分布式內(nèi)存對用戶的透明性。NGCS_SOAP指令NGCS_ SOAPEG(Type,Name有兩個參數(shù):Type

16、決定了系統(tǒng)執(zhí)行的操作類型:數(shù)據(jù)讀取或者數(shù)據(jù)寫入;Name為需要處理的變量的名稱,由以字母打頭的字符串表示,當(dāng)前面加“*”時表示為數(shù)據(jù)指針操作,前面無“*”時表示值操作。(3容錯機(jī)制理想狀態(tài)下網(wǎng)絡(luò)具有以下特征:較短的通信延時、較高的通信帶寬、極小的錯誤率、較好的可擴(kuò)展性。而現(xiàn)實(shí)情況是難以容忍的延時、有限的帶寬、隨機(jī)可能的出錯,因此建立基于互聯(lián)網(wǎng)的分布并行運(yùn)算系統(tǒng)必須有一套與之相對應(yīng)的容錯機(jī)制來適應(yīng)。該計算環(huán)境是由分布的若干臺計算機(jī)用Internet連接而成,每臺計算機(jī)是自治的,所以系統(tǒng)比較可靠。一個單元或資源的故障不影響其他資源的正常功能。理論上,可以通過全局的檢查點(diǎn)實(shí)現(xiàn)網(wǎng)格的容錯7,但實(shí)現(xiàn)難度

17、大,可行的方法是通過應(yīng)用程序本身來實(shí)現(xiàn)容錯功能。由于所提出的分布并行計算環(huán)境是基于Globus toolkit的,而Globus可以使用監(jiān)聽心跳的措施來跟蹤并行計算機(jī)失效的情況,從而達(dá)到容錯的目的。(4安全問題由于采用SOAP進(jìn)行底層通信,NGCS應(yīng)用可以部署的范圍大為擴(kuò)大,但在運(yùn)行過程中暴露節(jié)點(diǎn)地址在所難免,節(jié)點(diǎn)安全問題和數(shù)據(jù)安全問題成為制約系統(tǒng)部署的主要問題。目前采用的策略是有限的不可傳遞的信任原則,節(jié)點(diǎn)對主控系統(tǒng)的信任以任務(wù)為單位分配,并且任務(wù)腳本不能訪問節(jié)點(diǎn)的文件系統(tǒng),只能對系統(tǒng)規(guī)定的內(nèi)存進(jìn)行讀寫。3實(shí)例測試3.1問題分析與編碼實(shí)現(xiàn)為了驗(yàn)證NGCS系統(tǒng)的有效性,下面設(shè)計了一個數(shù)據(jù)耦合計

18、算任務(wù):N 皇后問題,一個N 皇后問題可被分解為N 個N-1粒度的問題,即N個可并行計算的任務(wù)。計算任務(wù)使用NGCS 描述,部署在一個局域網(wǎng)內(nèi),成為一個可執(zhí)行并行計算的科學(xué)計算環(huán)境。然后對不同數(shù)目有效節(jié)點(diǎn)情況下任務(wù)執(zhí)行的加速比進(jìn)行了比較。下面是用Scilab編寫的簡化后的部分網(wǎng)格服務(wù)實(shí)現(xiàn)算法和網(wǎng)格客戶應(yīng)用算法程序。N的并行宏語言描述NGCS.MAIN(略。3.2測試環(huán)境與結(jié)果要使用NGCS進(jìn)行分布并行計算必須具備如下條件:(1具備NGCS服務(wù)器系統(tǒng),并且系統(tǒng)內(nèi)至少具有兩個可用客戶節(jié)點(diǎn);(2 合理的NGCS應(yīng)用任務(wù)編碼;下面設(shè)計了一個有五臺計算機(jī)組成的異構(gòu)網(wǎng)絡(luò)環(huán)境的應(yīng)用系統(tǒng)來驗(yàn)證其有效性,主機(jī)1

19、上配置了NGCS的資源目錄服務(wù)和協(xié)同服務(wù),主機(jī)2為用戶應(yīng)用接入節(jié)點(diǎn),主機(jī)3、4、5為運(yùn)算資源節(jié)點(diǎn)。給出了求解問題的實(shí)際(理論運(yùn)行時間結(jié)果(略,圖4是該問題實(shí)際(理論加速比的測試結(jié)果。實(shí)驗(yàn)結(jié)果表明:隨著問題的規(guī)模增大, 在網(wǎng)格分布計算環(huán)境下的并行求解速度比單機(jī)求解的速度得到了很大的提高。隨著有效運(yùn)算節(jié)點(diǎn)數(shù)目的增加系統(tǒng)任務(wù)求解的速度也在不斷得到提高,但由于網(wǎng)絡(luò)帶寬和傳輸延遲等因素,運(yùn)算節(jié)點(diǎn)增加和任務(wù)求解速度加速并不能嚴(yán)格按照理論值進(jìn)行,在有效節(jié)點(diǎn)增加的同時,任務(wù)加速度要略小于新增的節(jié)點(diǎn)單獨(dú)計算能力之和。 圖4 實(shí)際和理論求解性能加速比4結(jié)論本文提出一種基于網(wǎng)格計算環(huán)境的分布并行計算實(shí)現(xiàn)新方法,實(shí)現(xiàn)了Scilab科學(xué)計算任務(wù)在Internet環(huán)境下的分布并行計算;它充分利用網(wǎng)絡(luò)上分散的、閑置的、異構(gòu)的資源獲得計算能力,屏蔽用戶服務(wù)細(xì)節(jié),簡化使用難度,使任務(wù)在處理節(jié)點(diǎn)上自動分配與調(diào)度,無需考慮任務(wù)和處理節(jié)點(diǎn)的對應(yīng)關(guān)系,進(jìn)一步減少了用戶編程細(xì)節(jié);同時,NGCS實(shí)現(xiàn)了系統(tǒng)動態(tài)負(fù)載平衡,提高了程序的執(zhí)行效率,并簡化了并行計算的實(shí)現(xiàn),為在異構(gòu)廣域網(wǎng)絡(luò)上實(shí)現(xiàn)超大問題的大規(guī)模分