支持低延遲通信與容錯的計算資源共享環境構建

許愛軍，張 岳

（1.廣州鐵路職業技術學院 信息工程系，廣東 廣州510430；2.中國科學院 數學與系統科學研究院，北京100120）

0 引 言

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

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

通過構造LF－CRSE的測試環境，選擇了典型的并行計算問題進行了測試。測試結果表明了LF－CRSE的加速比穩定增加，低延遲通信與容錯策略也具有很好的性能。在同等配置的硬件環境條件下，優于當前的一些項目。

1 LF－CRSE的系統結構

1.1 系統概況

根據LF－CRSE的工作機制，承擔了4個不同的功能角色。客戶端，任務服務器，工作機服務提供器 （Worker service provider）與工作機。

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

工作機服務提供器 （WSP）管理著網絡中的任務服務器。例如當一個任務服務器將加入到LF－CRSE平臺的時候，它首先和工作機服務提供器通信。WSP將通知新來的任務服務器節點如何加入到合適的任務服務器網絡之中。

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

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

1.2 工作機制

當一個客戶端登錄到LF－CRSE中時，工作機服務提供器將廣播該登錄到所有的任務服務器，同時任務服務器也將傳遞這些廣播消息到其下屬的所有工作機。當一個客戶端離開的時候，工作機服務提供器也廣播該離開消息到所有的任務服務器，同時任務服務器匯總資源的消費信息到所有的下屬的工作機。這些信息隨后會陸續的被收集到工作機服務器中，然后被傳遞到客戶端。目前LF－CRSE平臺中任務服務器的網絡拓撲結構如圖1所示。所有的劃分／聚集操作、登錄和離開操作都是通過一個任務服務器的網絡拓撲維護來完成。

圖1 LF－CRSE的工作機制

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

1.3 應用編程模式

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

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

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

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

2 低延遲通信與容錯

2.1 低延遲的處理

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

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

任務預獲?。翰⑿袘靡部梢愿鶕蝿盏念A獲取來減少通信的延遲。分為顯式模式和隱式模式。在顯式模式下，如果一個任務再不能劃分成子任務則稱為原子。子任務類中有一個類型為Boolean的方法isAtomic（）來控制。默認的情況下該方法是返回真。當調用子任務的Execute（）方法的時候，工作機就需要調用isAtomic（）方法，如果返回真，那么工作機在調用任務的Execute（）方法的時候，通過另外的線程將預獲取另外一個任務。隱式模式：當一個子任務對象的isAtomic（）方法的返回值是假，那么程序將跳轉到一個新的執行點上，該點處可以保證不需要構造任何的子任務，它又可以調用環境對象中的預獲取方法。這樣也可以使工作機請求到任務服務器中的另外的線程。

任務的預獲取技術覆蓋了工作機從當前任務的執行到下一個子任務的請求。這樣可以刺激應用開發員：鑒定原子任務類、讓工作機的空閑時間盡可能滿足每個原子子任務類。

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

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

2.2 容錯的處理

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

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

3 實驗與討論

3.1 實驗環境

LF－CRSE的實驗環境的配置是通過某個科研機構的局域網組成，不同的機器擔任客戶機、工作機服務提供器、工作機和任務服務器的角色。不同的角色的節點上都安裝好了LF－CRSE的中間件軟件，它們都是Jar包的形式。機器的配置如表1所示。

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

3.2 實驗過程

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

圖2 LF－CRSE的網絡拓撲結構

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

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

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

3.3 結果討論

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

圖3 分布式旅行商TSP的測試結果

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

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

表2 LF－CRSE的容錯測試結果

4 結束語

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

［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，France：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，Francesco 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.