非集中調度模型下的網格資源調度研究

摘要：針對當前網格資源調度系統擴展性差的問題，提出了基于非集中調度模型的以保守Backfilling算法為核心的網格資源調度算法。探討了網格任務在站點處理器數目異構情況下，網格作業多站點協同調度問題。實驗仿真證明，在跨網格站的資源調度中，運用資源預留策略和多站點作業分塊可以改善作業的平均響應時間，并起到負載平衡的效果。

關鍵詞：網格計算； 資源調度； 非集中調度

中圖分類號：TP302文獻標志碼：A

文章編號：1001－3695(2007)08－0030－04

網格計算[1]的目標是提供最廣泛的資源共享，實現以大規模計算和數據處理為特征的科學活動。網格任務的有效調度決定了資源的合理使用，是網格計算最重要的問題之一。網格資源調度本質上是跨多個站點（域）的，當前跨站點的網格資源調度算法大多是基于集中機制控制下的網格調度模型。這些模型通常假設具有一個全局調度器控制整個網格環境下的資源調度。顯然，整個網格系統的擴展性能因此受到影響，并且存在單點失效問題。隨著網格規模的擴大，網格調度系統的擴展性問題日益突出，基于全分布的非集中控制調度模型的網格資源調度算法的研究越來越受到重視。

1相關研究工作

Hamscher等人[2]對網格任務調度模型和調度策略作了深入描述和分析，將網格調度模型分為集中調度模型、層次調度模型和非集中調度模型三大類。集中調度模型和層次調度模型采用了集中控制的信息模型，能提供最高性能的調度方案；但是由于全局調度器的存在，整個網格系統的擴展性能受到影響，并且存在單點失效問題。非集中調度模型消除了集中調度模型的通信瓶頸，更具有可擴展性；此外單個調度器失效不會導致全局調度失敗，使該模型容錯能力也得到提高。但是由于調度器缺乏全局的資源和任務信息，實現起來比較困難，并且調度結果通常都不是全局最優的。

文獻[3]提出了針對小范圍內多個cluster之間任務調度的元調度器。為了綜合考慮網絡和計算資源，他們通過建立以網絡帶寬為中心的并行任務通信模型用以描述cluster之間的共享網絡負載隨時間的變化關系，在此基礎上研究和設計了綜合網格計算資源及網絡資源的協同調度元調度器。該研究基于層次調度模型。文獻[2]基于同構的網格資源模型，在比較幾種網格調度模型的過程中，對非集中調度模型進行初步研究。試驗表明，Backfilling算法對于提高系統的資源利用率大有幫助，并且在大多數情況下性能優于FCFS；但是其限定任務只能在同一個節點運行。Ramin Yahyapour[4]和Streit[5]設計了一種跨網格域的任務調度算法，針對Backfilling算法進行了集中調度模型下的多站點資源調度研究；但是他們將研究限定于站點同構，并且假設作業分塊數量對作業的執行時間沒有影響。然而在大多數情況下，上述關于作業執行時間的假設是不現實的。相比而言，非集中調度模型由于缺乏集中控制機制和全局網格資源信息，很少有人研究。本文嘗試在Yahyapour和Streit的研究基礎上，進一步研究非集中調度模型下的網格任務調度問題。著重考慮幾個問題：

采用非集中調度模型；站點處理器數量的異構；作業分塊對作業運行時間的影響。

在文獻[6]提出了一個分布式網格資源發現模型。該模型提供了在全分布網格環境中發現網格范圍內滿足任務需求的資源集合能力。在該模型基礎上，本文通過提出一種基于Backfilling機制的跨站點資源調度算法，探討在非集中控制模型下網格資源調度的問題。

2基于Backfilling跨站點調度模型及假設

2．1系統假設

非集中控制模型網格任務的調度非常復雜，在此僅討論針對計算資源共享的計算網格任務調度問題。對模型作出如下假設：

a）站點模型。計算網格由多個獨立站點組成，每個站點包含若干計算資源。站點支持將本地網格資源與其他站點的網格資源組合而形成更大的網格資源集，從而提高網格資源的利用率并支持更大規模的網格任務運行。

b）計算資源模型。假設計算資源為cluster，每個站點包含多個cluster；每個計算節點都有自己的CPU、內存以及磁盤；cluster內部和cluster之間由高速網絡互連，忽略站點內部的網絡開銷；同時，cluster支持空間共享模式。一個計算節點在同一時間只能運行一個任務，任務不能被搶占并且在任務提交到計算節點運行之后，任務對計算節點的需求不再變化。

c）網格任務模型。網格任務為批任務類型；同時假設網格任務具備在多個站點中并行執行的能力。任務在單個cluster上的任務長度為T，則該任務在分塊執行時，任務長度為[1]

其中： f表示任務分塊的數量；p是刻畫任務分塊開銷的影響因子。

2．2基于Backfilling的網格任務調度模型

依據上述資源信息，本文提出的調度系統如圖1所示。調度系統的主要構件是分布在各個站點中的資源管理器、調度器以及任務隊列。資源管理器主要提供：a)資源管理，即監控和管理全站點的計算資源；b)資源發現，即接收本地用戶提交的網格計算任務并在全網格范圍內為其發現滿足資源需求的網格資源集合（包括跨站點的資源集合）；c)按照用戶的提交時間收集本地站點的網格任務供調度器調度。網格調度器的主要作用是將任務隊列中的任務在全局網格范圍內調度運行，并且安排跨站點運行的網格任務在本地資源上調度執行。

圖1跨站點任務調度模型

3網格任務調度算法

本文設計了一個基于Backfilling策略的多站點協同任務調度算法。任務調度按照網格任務的執行時間和執行地點，可以分為單一站點立即執行、多站點立即執行、單一站點排隊執行、多站點資源預留執行四類。網格調度器根據當前的資源狀況決定網格任務的執行方式。

3．1總體調度算法

由于分布式調度環境下可能同時存在多個全局網格任務調度實例，網格資源發現結果RSready_single_site、RSready_multi_site中的空閑資源存在被其他站點搶先調度的可能。對此，在處理資源就緒信息時用了重新確認的辦法，一旦調度器向某一個外部調度器發出資源就緒的確認，就意味著該資源會立即被調度運行；當再次接收到其他調度器針對該資源就緒的確認，該調度只能返回資源非就緒的回復。由此，避免了分布式環境下多個全局網格任務同時向一個空閑資源分配任務的情形。

3．2Backfilling與資源預留算法

網格資源預留必須確定作業隊列中任務的預期完成時間。激進的Backfilling算法只針對作業隊列的第一個任務進行資源預留，作業隊列中其他任務的執行時間無法確定。相比而言，保守Backfilling算法保證了每個任務的預期執行時間。因此KRMM系統選擇保守的Backfilling算法配合資源預留操作的實施。

調度系統支持資源的預留操作。根據KRMM網格任務模型，跨站點執行的網格任務必須同步執行。因此，本地資源調度器必須與其他資源調度器協商出一個同步啟動任務的時間點。

3．2．1資源預留算法

算法輸入：

資源預留算法最主要的工作就是確定各個并行執行的子任務在各站點中的最遲開始執行時間，并將這個時間作為所有子任務的開始時間。

3．2．2支持資源預留的Backfilling算法

調度系統中的保守Backfilling依賴于兩個數據結構，即作業等待隊列和任務時空表。任務時空表以鏈表的形式保存，對于每一個新作業，只掃描時空分布圖一次，因為算法復雜性與任務個數為線性關系。

算法輸入：作業等待隊列；任務時空表。

當作業等待隊列中有新任務抵達，執行步驟a）。

a）新任務是資源預留任務，轉到e)；否則執行b）。

b）尋找作業插入點：

(a)對當前作業時空分布表進行掃描，找到第一個滿足該作業對節點個數要求的時間點。這個時間點稱為作業插入點。

(b)從作業插入點開始，繼續掃描作業時空分布圖，以確保節點在作業結束前資源都是可用的。

(c)如果(b)不滿足要求，返回(a)繼續掃描，直到找到一個合適的作業插入點。

c)將新作業插入作業時空分布圖，轉e)。

d)直接將任務插入等待作業隊列，并更新任務時空表。

e)如果時間到了作業插入點，則作業立即開始執行。

4實驗

本文對資源調度算法進行了模擬實驗，以驗證算法的正確性并對其性能進行評價。

實驗中，模擬了由四個站點組成的網格計算環境下的網格資源調度情況。每個站點的資源情況如表1所示。

到目前為止，還沒有用于測試網格調度系統性能的標準網格作業量文檔。因此采用由希伯倫大學的Dror Feitelson收集整理并與本文調度系統具有相似工作環境的康奈爾理論中心（Cornell theory center，CTC）的工作載荷[7]，作為仿真的輸入任務。本文仿真過程截取了CTC作業記錄中兩個完整的四個月記錄，分別記為CTC1、CTC2。表2為這兩個作業記錄的統計信息（其中日平均負載=日均作業量×作業平均處理器數量×作業平均運行時間／處理器數量）。Backfilling算法是在線調度算法。為保證算法的高效性，Backfilling算法通常要求等待隊列中有足夠的作業，以從中尋找到合適的作業進行回填。為保證仿真過程中有足夠的作業，同時向四個站點輸入相同的作業集合，即每個站點的調度器都有相同的CTC工作流輸入。

在上述實驗的前提下，本文分別仿真了如下三種情況的任務調度：

a)單站點調度。網格任務在單一站點內部調度執行。這是整個仿真的比較基準。

b)多站點調度單站點執行。在全網格范圍內尋找單個站點內部滿足網格任務資源需求且完成時間最小的資源集合，并在該資源集合上調度執行。

c)多站點協同調度。在多站點調度單站點執行基礎上，啟動了多站點任務分塊執行和資源預留的網格調度。

仿真結果如圖3~5所示。

圖3顯示了單站點調度情況下，兩個作業記錄分別在各個站點上執行的系統加權平均響應時間(AWRT)。系統的仿真測試結果與文獻[4，5]的結果是一致的。仿真結果顯示，AWRT隨著站點內部的cluster數量以及p值的增大而增加。因為對于每個站點而言，在總處理器數目相同的情況下，cluster數目越多，任務被分塊執行的可能性越大；同時，隨著p的增大，根據式（1）可以得出任務的完成時間將延長，AWRT隨之增加。

圖4和圖5是兩個作業集的網格資源調度情況。圖中，每個系列（site1~site4）的前三個分類（p=0．1，p=0．2，p=0．4）代表多站點調度單站點執行的資源調度結果；后三個分類則代表多站點協同調度的結果。對比圖3可以看出，網格環境中，在各個站點輸入不變的情況下，每個站點的加權平均響應時間都得到了極大改善；甚至在p=0．4，作業長度增加70%以上的情況下，仍有大部分站點的AWRT小于單站點任務調度p=0．1的AWRT。通過在全局網格范圍內尋找滿足作業需求的資源，任務的分塊數量也大大下降。這說明分布式Backfilling很好地適應了網格特點，極大提高了網格任務的響應時間。同時還可以看出，各個站點的AWRT之間的懸殊顯著減小，說明網格任務調度起到了很好的負載均衡作用。

從圖4、5還可以看出，網格任務的多站點分塊執行和多站點資源預留進一步改善了網格任務的加權平均響應時間。在多站點分塊執行的情況下，所有站點的AWRT均小于相應條件下網格任務單站點執行和多站點調度單站點執行的AWRT。

5結束語

網格資源調度問題在大多數情況下都是NP完全問題。在分布式的網格環境中，處理網格資源調度問題更加困難。本文提出了基于非集中調度模型的以保守Backfilling算法為核心的網格資源調度算法；通過引入確認機制以消除資源并發請求帶來的不確定性；探討了網格任務在站點處理器數目異構情況下，網格作業多站點協同調度問題。實驗仿真證明，在跨網格站點的資源調度中，運用資源預留策略和多站點作業分塊可以改善作業的平均響應時間，并起到了負載平衡的效果。

參考文獻：

［1］FORSTER I， KESSELMAN C.The grid2:blueprint for a new computing infrastructure[M].金海，等譯.北京:電子工業出版社， 2004.

[2］HAMSCHER V， SCHWIEGELSHOHN U， STREIT A，et al. Evaluation of jobscheduling strategies for grid computing[EB/OL].2000(2005－12－08).[2006－03－17]. http://springerlink.lib.tsinghua.edu.cn/.[3］JONES W M， PANG L W， STANZIONE D， et al. Job communication characterization and its impact on metascheduling coallocated jobs in a minigrid [C]//Proc of the 18th IEEE International Parallel and Distributed Processing Symposium. Washington D C: IEEE Computer Society，2004:253－261.[4］YAHYAPOUR R. Design and evaluation of job scheduling strategies for grid computing[D].Dortmund:University of Dortmund， 2002.

[5］STREIT A. Selftuning job scheduling strategies for the resource mana￣gement of HPC systems and computational grids [D]. Paderborn:Paderborn University，2003.

[6］盧國明，顧小豐，孫世新，等. 基于本體的網格資源匹配算法研究[J]. 計算機科學，2006，33(4):75－79.

[7］Standard workloads archive[EB/OL]. http://www.cs.huji.ac.il/labs/parallel/workload/.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”