許愛軍，張 岳

（1.廣州鐵路職業(yè)技術(shù)學(xué)院 信息工程系，廣東 廣州510430；2.中國科學(xué)院 數(shù)學(xué)與系統(tǒng)科學(xué)研究院，北京100120）

0 引 言

計算資源共享環(huán)境 （computing resource sharing environments，CRSE）可以通過中間件軟件的方式把各種異構(gòu)的、多域網(wǎng)絡(luò)環(huán)境下的計算資源充分利用與聚集起來，完成某種分布式的、計算量大的任務(wù)的系統(tǒng)［1－5］。目前關(guān)于構(gòu)建廣域網(wǎng)或局域網(wǎng)上的CRSE，國內(nèi)外已經(jīng)有很多相關(guān)的項目，取得了很有價值的研究結(jié)果［6－11］。研究表明為了提高CRSE的計算性能，除了高效的任務(wù)調(diào)度算法外［12］，低延遲通信與容錯策略也十分重要，同時還必須改進(jìn)應(yīng)用的編程模型，擴(kuò)大CRSE的應(yīng)用領(lǐng)域。

本文提出與描述的LF－CRSE （low latency and fault tolerance CRSE）也是這種類型的計算資源共享環(huán)境。LFCRSE由擔(dān)任各種不同角色的功能節(jié)點自愿的組成，包括客戶端節(jié)點、任務(wù)服務(wù)器節(jié)點、工作機(jī)節(jié)點和工作機(jī)服務(wù)提供器節(jié)點等。LF－CRSE和當(dāng)前的某些項目類似，也是充分運用Java的跨平臺特性、對象序列化技術(shù)和字節(jié)碼技術(shù)，使LF－CRSR具有跨平臺性、通用性和可擴(kuò)展性。LF－CRSE也有自己的特點：支持低通信延遲、容錯特性和分支界限技術(shù) （branch and bound）。分支界限技術(shù)能使LF－CRSE支持最基本的主－從 （master－slave）風(fēng)格的并行計算外，還支持具有數(shù)據(jù)依賴的分布式旅行商 （travelling salesman problem）問題，這樣LF－CRSE的應(yīng)用范圍就大大增加。

通過構(gòu)造LF－CRSE的測試環(huán)境，選擇了典型的并行計算問題進(jìn)行了測試。測試結(jié)果表明了LF－CRSE的加速比穩(wěn)定增加，低延遲通信與容錯策略也具有很好的性能。在同等配置的硬件環(huán)境條件下，優(yōu)于當(dāng)前的一些項目。

1 LF－CRSE的系統(tǒng)結(jié)構(gòu)

1.1 系統(tǒng)概況

根據(jù)LF－CRSE的工作機(jī)制，承擔(dān)了4個不同的功能角色?？蛻舳耍蝿?wù)服務(wù)器，工作機(jī)服務(wù)提供器 （Worker service provider）與工作機(jī)。

客戶端 （Client）首先是用來提交并行計算任務(wù)的，這往往是具體的用戶或者并行應(yīng)用程序開發(fā)員，同時客戶端也負(fù)責(zé)請求計算的臨時結(jié)果和返回結(jié)果，如果某些應(yīng)用有圖形的顯示需求，可以在客戶端上開發(fā)更加多的界面組件模塊?？蛻舳酥缓凸ぷ鳈C(jī)服務(wù)提供器的組件交互，此時工作機(jī)服務(wù)提供器都以服務(wù)組件代理的形式提供。

工作機(jī)服務(wù)提供器 （WSP）管理著網(wǎng)絡(luò)中的任務(wù)服務(wù)器。例如當(dāng)一個任務(wù)服務(wù)器將加入到LF－CRSE平臺的時候，它首先和工作機(jī)服務(wù)提供器通信。WSP將通知新來的任務(wù)服務(wù)器節(jié)點如何加入到合適的任務(wù)服務(wù)器網(wǎng)絡(luò)之中。

任務(wù)服務(wù)器 （Task server）用來存儲任務(wù)對象。每個任務(wù)對象都是已經(jīng)被劃分好的任務(wù)但是還沒有開始計算，它可以是一種Java字節(jié)碼的形式，同時包含著一些相關(guān)的數(shù)據(jù)文件與參數(shù)。任務(wù)服務(wù)器可以在內(nèi)部平衡化即將到達(dá)的任務(wù)。每個任務(wù)服務(wù)器的下屬有一些工作機(jī)依附于它。當(dāng)一個工作機(jī)請求任務(wù)執(zhí)行的時候，任務(wù)服務(wù)器返回一個任務(wù)給工作機(jī)，如果工作是空閑的時候，將讓其執(zhí)行。如果工作機(jī)出現(xiàn)了異常，任務(wù)服務(wù)器將重新分配該任務(wù)給另外的工作機(jī)。

工作機(jī) （Worker）是LF－CRSE中的任務(wù)的具體執(zhí)行者，同時返回任務(wù)的臨時結(jié)果給工作機(jī)服務(wù)提供器，它的角色類型是愿意提供空閑計算資源的自愿者，一般來說，工作機(jī)數(shù)目越大，LF－CRSE的計算能力就越強(qiáng)大。

1.2 工作機(jī)制

當(dāng)一個客戶端登錄到LF－CRSE中時，工作機(jī)服務(wù)提供器將廣播該登錄到所有的任務(wù)服務(wù)器，同時任務(wù)服務(wù)器也將傳遞這些廣播消息到其下屬的所有工作機(jī)。當(dāng)一個客戶端離開的時候，工作機(jī)服務(wù)提供器也廣播該離開消息到所有的任務(wù)服務(wù)器，同時任務(wù)服務(wù)器匯總資源的消費信息到所有的下屬的工作機(jī)。這些信息隨后會陸續(xù)的被收集到工作機(jī)服務(wù)器中，然后被傳遞到客戶端。目前LF－CRSE平臺中任務(wù)服務(wù)器的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示。所有的劃分／聚集操作、登錄和離開操作都是通過一個任務(wù)服務(wù)器的網(wǎng)絡(luò)拓?fù)渚S護(hù)來完成。

圖1 LF－CRSE的工作機(jī)制

從圖1中看出，該LF－CRSE系統(tǒng)具有3個任務(wù)服務(wù)器，任務(wù)服務(wù)器是一種二維的拓?fù)?，每個任務(wù)服務(wù)器下面依附了5個工作機(jī)，該客戶端只是和工作機(jī)服務(wù)提供器交互。任務(wù)對象封裝了計算過程，任務(wù)對象是一種序列化了的Java對象或者可跨平臺運行的Java字節(jié)碼，它們的輸入和輸出都是通過LF－CRSE平臺來管理，任務(wù)的執(zhí)行的個數(shù)是隨著工作機(jī)的增加而提升的，任務(wù)對象同時支持對工作機(jī)的透明性和任務(wù)容錯處理。

1.3 應(yīng)用編程模式

并行分布式計算的任務(wù)往往被開發(fā)員劃分成許多可以并行執(zhí)行的子任務(wù)，任務(wù)與子任務(wù)之間可以形成一個任務(wù)圖。應(yīng)用的任務(wù)圖中的節(jié)點和邊分別表示了任務(wù)劃分的方式 （主從模式或分治模式）、任務(wù)之間的數(shù)據(jù)依賴關(guān)系，任務(wù)都是通過共享對象來訪問的。共享的語義表示了并行計算的上下文，對象的共享是異步與阻塞模式的。這種限制導(dǎo)致了共享在某些情形下不可用。但是通過分支界限模式（branch and bound），LF－CRSE可以處理很多情況下的交互優(yōu)化問題，LF－CRSE中運用了該技術(shù)。

子任務(wù)是應(yīng)用編程接口的核心，它們通過執(zhí)行Execute方法來封裝了計算的細(xì)節(jié)。Execute方法具有一些環(huán)境參數(shù)，這個是重點需要考慮的。假設(shè)A是一個任務(wù)，它有一組輸入對象，它返回一個輸出對象，該輸出對象是下一個任務(wù)的輸入 （假設(shè)為A’），也許A’又被分解成一組子任務(wù)，同時返回一個臨時結(jié)果。最后臨時結(jié)果的返回值是關(guān)于任務(wù)A的環(huán)境參數(shù)。這種任務(wù)的分解由一個大的任務(wù)劃分后完成，任務(wù)分解后又有新的子任務(wù)產(chǎn)生。獨立的子任務(wù)可以通過隱式的消息傳遞完成。它可以改善工作機(jī)的利用率，也很方便容錯。從這個分析可以看出，任務(wù)的關(guān)系圖對于LF－CRSE是透明的，任務(wù)的調(diào)度是在執(zhí)行的時候完成的。

在LF－CRSE中，子任務(wù)的訪問通過一個通用環(huán)境對象完成，通用環(huán)境對象是在整個計算過程中的一個只讀的輸入對象，并且對于共享對象是可變化的。例如當(dāng)運行TSP分布式旅行商問題的時候，用戶可能希望調(diào)整距離矩陣到輸入對象之中，子任務(wù)通過環(huán)境中的GetShared（）方法來訪問共享對象，同時通過SetShared（）方法來更改。一個共享對象是實現(xiàn)了Shared的接口，它包括isNewerThan（）方法。

雖然共享之間的語義比較虛弱，但是它是適合分布式計算的。當(dāng)共享對象改變的時候，它的值也被通知出去。當(dāng)環(huán)境中接收到共享對象的新的值的時候，它將通過is－NewerThan（）方法來判斷它是否比當(dāng)前的值更新，例如在TSP問題中的旅行的距離就可以作為共享對象。那么當(dāng)一個新的旅行被發(fā)現(xiàn)了后，它的整體距離將被共享。如果提出的整體距離少于當(dāng)前的最優(yōu)的旅行距離，在這個情況下isNewerThan（）方法將返回True的值。但是在分布式計算中主－從編程模式并不是經(jīng)常發(fā)生這種情形。

2 低延遲通信與容錯

2.1 低延遲的處理

LF－CRSE的低延遲通信處理依賴于任務(wù)緩存、任務(wù)預(yù)獲取和任務(wù)服務(wù)器計算等策略。

任務(wù)緩存：當(dāng)任務(wù)在劃分成為子任務(wù)的時候，首先被構(gòu)造的子任務(wù)被下載并緩存在工作機(jī)上，計算完成后，根據(jù)工作機(jī)的需求來請求任務(wù)服務(wù)器獲得下一個任務(wù)。任務(wù)的緩存的情況是根據(jù)應(yīng)用開發(fā)員劃分需要來控制的。

任務(wù)預(yù)獲?。翰⑿袘?yīng)用也可以根據(jù)任務(wù)的預(yù)獲取來減少通信的延遲。分為顯式模式和隱式模式。在顯式模式下，如果一個任務(wù)再不能劃分成子任務(wù)則稱為原子。子任務(wù)類中有一個類型為Boolean的方法isAtomic（）來控制。默認(rèn)的情況下該方法是返回真。當(dāng)調(diào)用子任務(wù)的Execute（）方法的時候，工作機(jī)就需要調(diào)用isAtomic（）方法，如果返回真，那么工作機(jī)在調(diào)用任務(wù)的Execute（）方法的時候，通過另外的線程將預(yù)獲取另外一個任務(wù)。隱式模式：當(dāng)一個子任務(wù)對象的isAtomic（）方法的返回值是假，那么程序?qū)⑻D(zhuǎn)到一個新的執(zhí)行點上，該點處可以保證不需要構(gòu)造任何的子任務(wù)，它又可以調(diào)用環(huán)境對象中的預(yù)獲取方法。這樣也可以使工作機(jī)請求到任務(wù)服務(wù)器中的另外的線程。

任務(wù)的預(yù)獲取技術(shù)覆蓋了工作機(jī)從當(dāng)前任務(wù)的執(zhí)行到下一個子任務(wù)的請求。這樣可以刺激應(yīng)用開發(fā)員：鑒定原子任務(wù)類、讓工作機(jī)的空閑時間盡可能滿足每個原子子任務(wù)類。

任務(wù)服務(wù)器計算：如果任務(wù)的封裝的計算是稍微復(fù)雜點的，那么在任務(wù)服務(wù)器上計算所消耗的時間比在工作機(jī)上計算往往要少。這個是因為從任務(wù)服務(wù)器到工作機(jī)，把代碼和數(shù)據(jù)的序列化時間和反序列化的時間代價很大。如果把這些任務(wù)直接在任務(wù)服務(wù)器上計算還可以減少網(wǎng)絡(luò)的延遲。比較常見的操作，例如求最大值Max，求和Sum都可以在任務(wù)服務(wù)器上直接執(zhí)行，而不需要分配到工作機(jī)。在實現(xiàn)這個策略的時候，通過一個名稱為ExecuteOnServer（）的Boolean型方法來完成。

當(dāng)一個任務(wù)準(zhǔn)備執(zhí)行的時候，任務(wù)服務(wù)器將調(diào)用ExecuteOnServer（）方法，如果返回為真，任務(wù)服務(wù)器將在本地執(zhí)行。該操作由應(yīng)用程序員在編程的時候自己控制。整體來說通過這些策略保證了LF－CRSE功能節(jié)點之間的低延遲通信，減少了任務(wù)執(zhí)行的代價。

2.2 容錯的處理

當(dāng)一個任務(wù)服務(wù)器探測到某些工作機(jī)的異常的時候，工作機(jī)上的代理對象可以負(fù)責(zé)容錯，周期性的發(fā)送心跳消息給任務(wù)服務(wù)器，如果任務(wù)服務(wù)器的通信出現(xiàn)了異常，通過設(shè)置一個超時時間間隙和延遲域值，它將試圖重新通信一直到成功完成，如果超過了時間間隙，工作機(jī)上的代理對象將返回工作機(jī)的任務(wù)相關(guān)的代碼和數(shù)據(jù)，以便用來重新分配任務(wù)，隨后它將從任務(wù)服務(wù)器的網(wǎng)絡(luò)中刪除。這就使LF－CRSE在某種程度上具有一定的可靠性。

因為是面向子任務(wù)的容錯策略，所以LF－CRSE的任務(wù)的重新分配代價是比較小的，由于系統(tǒng)支持的主要編程模型是主－從 （Master－Slave）和分治 （divide－and－conquer）模式，節(jié)點之間的通信量很小，只要節(jié)點有非正常退出，LFCRSE可以給新取代的節(jié)點再次分配子任務(wù)相關(guān)的參數(shù)與代碼。例如在分布式旅行商的TSP問題中，任務(wù)的劃分是比較復(fù)雜的，只有當(dāng)前正在執(zhí)行的任務(wù)才需要被重新計算。測試中顯示TSP的每個子任務(wù)的平均執(zhí)行時間是2s，重新從失敗中恢復(fù)的大約時間是1s，這些是代價和整體的運行時間比較是很小的。

3 實驗與討論

3.1 實驗環(huán)境

LF－CRSE的實驗環(huán)境的配置是通過某個科研機(jī)構(gòu)的局域網(wǎng)組成，不同的機(jī)器擔(dān)任客戶機(jī)、工作機(jī)服務(wù)提供器、工作機(jī)和任務(wù)服務(wù)器的角色。不同的角色的節(jié)點上都安裝好了LF－CRSE的中間件軟件，它們都是Jar包的形式。機(jī)器的配置如表1所示。

并行計算的案例程序選擇了需要分支界限法的分布式旅行商TSP問題，使用了TSPLIB中的kroB200的數(shù)據(jù)。為了保證該算法有很好的提高速度，系統(tǒng)設(shè)置了最初的上限，運用分支界限技術(shù)優(yōu)化旅游長度，使其達(dá)到最小的旅游長度。最后每一輪都搜索同一個搜索樹，子任務(wù)的平均執(zhí)行時間大約為2.05s。

3.2 實驗過程

在每個實驗中，啟動了工作機(jī)服務(wù)提供器，隨后啟動一個任務(wù)服務(wù)器，隨著后面的任務(wù)服務(wù)器的加入，它們分別開始聚集大量數(shù)目的工作機(jī)。整體來說64個工作機(jī)，依附于8個任務(wù)服務(wù)器上，這些機(jī)器共同協(xié)同與合作來完成一個大的并行計算任務(wù)，由客戶機(jī)上啟動TSP的應(yīng)用，提交到工作機(jī)服務(wù)器上，如圖2所示。

圖2 LF－CRSE的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

應(yīng)用由可變化的負(fù)載組成，它有一些不平衡的任務(wù)關(guān)系圖。整體計算的時間是應(yīng)用從提交任務(wù)到最后接收到匯總子任務(wù)結(jié)果的輸出的時間。LF－CRSE可以通過自動的分支界限技術(shù)保證了該應(yīng)用的遞歸迭代過程，完成低延遲的通信優(yōu)化。由于處理器都是雙核的，所以如果取的工作機(jī)的數(shù)目是60，那么就有120個處理器，系統(tǒng)能夠獲得了一定的速度提高。測試的時間取了3次的平均值。

在容錯性能的測試中，LF－CRSE在任務(wù)服務(wù)器上啟動了32個處理器。系統(tǒng)運行1500s后，大約經(jīng)過了3／4的計算過程后，通過采用手動的方式關(guān)閉某些任務(wù)服務(wù)器。把整體的計算過程的時間記錄下來，把它和理想的執(zhí)行時間進(jìn)行了比較。

為了測試整個系統(tǒng)中的任務(wù)服務(wù)器與工作機(jī)之間的低延遲通信開銷，體現(xiàn)系統(tǒng)的低延遲通信性能，在任務(wù)服務(wù)器上運行了22個處理器，把它和一個任務(wù)服務(wù)器和一個處理器的情形進(jìn)行了比較，該實驗也運行了3次，記錄了平均值。

3.3 結(jié)果討論

圖3中顯示了TSP并行案例程序的運行速度測試結(jié)果，在功能上，LF－CRSE除了能夠很好的完成計算外，還以較快的速度完成了并行計算。在不同的工作機(jī)數(shù)下，完成相同的子任務(wù)的時間明顯減少，特別是在工作機(jī)的數(shù)目達(dá)到16個以上后，加速比提高更快。這是由于在LF－CRSE中使用了分支界限技術(shù)，可以讓新的子任務(wù)不停產(chǎn)生，同時利用低延遲的通信使整體完成的時間代價減少。在同等硬件配置條件下，由于任務(wù)劃分粒度好，每個子任務(wù)的完成時間不超過2s，LF－CRSE的性能優(yōu)于當(dāng)前的一些Javalin和JAVM 等項目［13－15］。

圖3 分布式旅行商TSP的測試結(jié)果

在TSP問題中，Pmin是最低的邊界處理器數(shù)目，它可以更加好的優(yōu)化并行粒度性能。在這里設(shè)置的Pmin的值為1857，那么1857就是處理器的最低邊界，這樣就可以把完成時間降低到Tmin，大約為37s。LF－CRSE的容錯測試結(jié)果如表2所示。它可以把一個異常的任務(wù)由失敗到重新分配到新的工作機(jī)，但是它需要一些開銷。從表中可以看出，這些時間開銷不超過整體時間的10%。

最后測試了任務(wù)服務(wù)器和工作機(jī)之間的通信延遲開銷。測試結(jié)果表明，如果把簡單的操作直接在任務(wù)服務(wù)器上執(zhí)行，而不是分配到工作機(jī)上，可以使整體的通信開銷減少，這個是因為對于TSP算法來說，任務(wù)服務(wù)器上的任務(wù)劃分比較簡單，整體的完成時間減少。

表2 LF－CRSE的容錯測試結(jié)果

4 結(jié)束語

本文提出與描述了一個支持低延遲通信與容錯的計算資源共享環(huán)境LF－CRSE，它通過中間件的方式可以完成廣域網(wǎng)／局域網(wǎng)上的計算資源共享。在具體案例測試與容錯測試等方面，LF－CRSE的功能測試與性能測試體現(xiàn)出良好的性能。本文的后續(xù)工作是調(diào)整后臺節(jié)點的應(yīng)用相關(guān)的調(diào)度策略，分析新的應(yīng)用編程模式，改進(jìn)節(jié)點上的負(fù)載，充分提高計算資源的利用率。

［1］Franck Cappello，Samir Djilali，Gilles Fedak，et al.Computing on largescale distributed systems：XtremWeb architecture programming models security tests and convergence with grid［J］.Future Generation Computer System，2005，21 （3）：417－437.

［2］Anderson D P.BOINC：A system for public－resource computing and storage ［C］.Proceedings of the Fifth International Workshop of Grid Computing.Washington，DC：IEEE Computer Society Press，2004：4－10.

［3］Andrade N，Cirne W，Brasileiro F，et al.Ourgrid：An approach to easily assemble grids with equitable resource sharing［G］.LNCS 2862：9th Workshop on Job Scheduling Strategies for Parallel Processing.Seattle， Washington：Springer－Verlag，2003：61－86.

［4］Anglano C，Canonico M，Guazzone，et al.G peer－to－peer desktop grids in the real world：The share grid project［C］.Lyon，F(xiàn)rance：Proceedings of 8th IEEE International Symposium on Cluster Computing and the Grid，2008：621－626.

［5］Akshay Luther，Rajkumar Buyya，Rajiv Ranjan，et al.Alchemi：A .NET－based enterprise grid computing system ［C］.Las Vegas，USA：Proceedings of the 6th International Conference on Internet Computing，2005：27－30.

［6］Great internet mersenne prime search project ［EB／OL］.http：／／www.mersenne.org／，2011.

［7］Shudo K，Tanaka Y，Sekiguchi S.P3：P2P－based middleware enabling transfer and aggregation of computational resources［C］.Proc of the IEEE International Symposium on Cluster Computing and the Grid，2005：259－266.

［8］Michele Amoretti，F(xiàn)rancesco Zanichelli，Gianni Conte.SP2A：A service－oriented framework for P2P－based grids ［C］.Proceedings of 3rd International Workshop on Middleware for Grid Computing.New York：ACM Press，2005：1－6.

［9］Patoli Z，Gkion M，Al－Barakati，et al.How to build an open source render farm based on desktop grid computing［C］.Hussain DMA，Rajput AQK，Chowdhry BS.Proceedings of IMTIC，2008：268－278.

［10］Kondo D，Taufer M，Brook C，et al.Characterizing and evaluating desktop grids：An empirical study ［C］.18th International Parallel and Distributed Processing Symposium.Santa Fe，New Mexico，USA：IEEE Computer Society，2004：26－35.

［11］LUIS F G Sarmenta.Volunteer computing ［D］.Department of Electrical Engineering and Computer Science，MIT，2001.

［12］Neary M O，Cappello P.Advanced eager scheduling for Javabased adaptively parallel computing［J］.Concurrency and Computation：Practice and Experience，2005，17 （7－8）：797－819.

［13］Neary M O，Phipps A，Richman S，et al.Javelin 2.0：Javabased parallel computing on the internet［G］.LNCS 1900：6th Int’l Euro－Par Conference.Springer Verlag， 2000：1231－1238.

［14］Cappello P，Mourloukos D.CX：A scalable robust network for parallel computing［J］.Scientific Programming，2001，10（2）：159－171.

［15］LAU L F，Ananda A L，TAN G，et al.JAVM：Internetbased parallel computing using Java［M］.Annual Review of Scalable Computing，Singapore University Press／World Scientific，2000：59－74.