異構集群系統的可分負載多輪調度算法

摘要：針對更實際的異構集群計算環境，充分考慮處理機具有不同的計算速度、通信能力和存儲容量的特性，通過允許計算和通信操作重疊執行，采取多次并行分配計算任務的方法，設計一種可分負載多輪調度算法。實驗結果表明，該算法不但能獲得與均勻多輪調度(UMR)算法相當的漸近最優調度時間長度，并且能夠處理更大規模的應用負載，實用性更強。

關鍵詞：異構集群系統； 任務調度； 并行算法； 可分負載

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

文章編號：1001－3695(2008)04－1028－05

0引言

如何把復雜應用的所有任務合理地調度分配到異構計算系統的各個處理機上，并追求整個應用的最小完成時間的任務調度問題，是異構集群計算系統提高性能的一個非常關鍵的問題。任務數目和大小可以任意選擇，即任務粒度可以任意小的一類獨立任務調度問題稱為可分負載調度[1~3]。科學和工程領域有許多應用是由大量細粒度的獨立任務構成的，即這些應用可以劃分成任意數目和任意大小的任務塊。因此這些應用易于直接并行化，特別是在主從模式下，這一類應用也稱為可分負載[1~3]。由于可分負載理論廣泛的應用背景及其結果的簡單性和易于分析，使得可分負載任務調度問題的研究近年來引起了人們的高度重視，并在大規模信號處理、視頻和圖像處理、數據挖掘、網絡存儲、VoD 系統、科學計算、密碼求解、大規模仿真、組合優化、負載平衡的擴散操作和模式匹配等領域得到了廣泛的應用。

可分負載調度算法主要分為單輪調度算法和多輪調度算法兩大類。單輪調度算法較為簡單，但其計算和通信的重疊性較差，額外開銷相對較大；多輪調度算法則具有較好的計算和通信重疊性，較好地降低了調度的額外開銷。但由于難以分析等原因，使得對多輪調度算法的研究成果相對較少，已有的多輪調度算法大多數是同構集群計算環境下的調度算法。在一定的假設條件下，一些簡單的可分負載調度問題存在緊致形式的最優解。但在處理機具有不同計算速度、通信能力和存儲容量的異構集群計算環境下的可分負載調度問題是NP－完全問題[4~6]。

文獻[7~9]在考慮處理機實際計算能力和通信延遲不同的情況下，提出了異構集群系統的均勻多輪調度算法UMR，并獲得漸近最優的調度輪數。文獻[7]給出了UMR的詳細推導過程和實驗結果分析。文獻[9]的模擬實驗表明，任務塊的大小在調度過程中保持逐漸增大并不能有效地抑制額外開銷。文獻[10]對文獻[9]的UMR算法作了擴展，提出了一種健壯的均勻多輪調度算法RUMR。該算法考慮性能預測誤差，對任務塊按其從小到大遞增然后再遞減的次序進行調度分配，使得算法更加健壯。文獻[11]設計了一個由處理機運算速度不同和異構網絡互聯的異構集群系統的已知資源的最優負載分布RAOLD（resource－aware optimal load distribution）算法。文獻[12，13]考慮了處理機的通信延遲，在異構集群環境上設計了一個漸近最優的多輪調度算法，該算法易于實現，并在理論上第一次給出了多輪調度算法性能的定量分析。文獻[5，14]研究了處理機通信延遲不同和存儲受限的異構集群環境下可分負載的單輪調度算法。文獻[4，5]的研究分析結果表明，處理機通信延遲不同和存儲受限的星型異構集群環境的可分負載調度問題是NP完全問題。文獻[6]證明了在仿射代價模型下，處理機計算速度和通信能力不同的星型異構計算平臺的可分負載調度問題是NP完全的。文獻[15]研究了異構集群環境下可分負載調度的雙向信息通信問題。文獻[16]研究了處理機存儲受限的單級樹型網絡的異構集群環境的可分負載調度問題，提出了增量平衡策略算法（incremental balancing strategy，IBS）。文獻[17]在文獻[16]的基礎上，研究分析了處理機通信延遲不同和存儲受限的多級樹型網絡異構集群環境的可分負載調度問題，設計了調度算法PPOLD（pull－push optimal load distribution）。文獻[16，17]提出的IBS和PPOLD調度算法在每一次迭代時都將填滿一個處理機節點的內存，然后該處理機節點將不再參與后面的迭代（即剩余的任務調度）。這兩種算法都不能處理任務負載總量大于集群系統總內存容量的情況。

在更實際的異構集群計算環境中，處理機的計算速度、通信能力和內存容量等均可能不同。本文將在均勻多輪調度算法UMR的基礎上，通過允許計算和通信操作重疊執行，采取多次并行分配計算任務的方法，研究設計一種同時考慮處理機具有不同的計算速度、通信能力和內存能力等因素的異構集群系統可分負載多輪調度算法UMRLM。該算法在追求調度長度最小化的同時，使得算法能夠處理更大規模的應用負載問題。

1應用模型和計算模型描述

本文對應用模型和計算模型的假設與UMR算法相似。對應用模型的假設為：a)應用包含一個大小為Wtotal的負載，負載可以被任意劃分成大小不同的塊（chunk）；b)只考慮輸入數據的傳送，不考慮返回結果的數據傳送。對計算平臺的假設如下：a)具有N個從處理機節點（worker）和一個主處理機節點（master）的星型異構機群系統；b)主處理機節點以串行傳輸方式與各從處理機節點進行通信；c)允許從處理機節點從網絡上接收數據的同時進行任務處理；d)主處理機節點只負責發送負載塊chunk到各從處理機節點，不參與負載處理。異構機群系統計算模型如圖1所示。

本文使用的主要符號定義如下：a)Wtotal表示總負載大小（假設一個任務代表一個單位負載）；b)chunkji表示第j輪調度分配給第i個worker的任務數；c)Si表示第i個worker的處理能力即單位時間內處理的任務數；d)cLati表示第i個worker的計算延遲即初始化計算所需的時間；e)Bi表示master到第i個worker的鏈路通信速率，即單位時間內傳送的任務數；f)nLati表示master到第i個worker的鏈路通信延遲；g)bufi表示第i個worker的內存大小；h)constj為第j輪調度的處理時間；i)roundj表示第j輪調度分配的總負載量。

2均勻多輪調度算法

UMR算法[7~9]是僅考慮處理機計算和通信能力不同的異構計算環境下的一個均勻多輪調度算法，它采用的計算平臺模型如圖1所示。該算法假設同一輪調度中各處理機節點的負載計算時間相同，并采用串行傳輸模式即在每一時刻只允許master向一個worker節點發送負載。圖2描述了UMR算法對負載傳送和各處理機節點處理相應負載的過程。

在串行傳輸模式下，UMR算法獲得了漸近最優的調度輪數及第一輪調度分配給各從處理機節點的負載塊大小[8]。雖然UMR算法考慮了處理機計算速度和通信延遲不同這兩個因素，但沒有考慮各個處理機的實際存儲能力。

3處理機計算速度和通信能力及內存容量不同的異構集群系統調度算法

對于處理機具有不同的計算速度、通信能力和內存容量的更實際的異構集群系統，通過允許計算與通信操作重疊執行，采取多次并行分配計算任務的方法。本文設計一種可分負載多輪調度算法UMRLM，其主要思想是：a)參考UMR算法的方法，計算每一個負載塊的初始值；b)若第j輪調度中存在某個負載塊chunkji大于欲分配給第i個處理機節點的可用內存容量bufi，則令第j~M′-2輪調度分配給各從處理機節點的負載大小都等于第j-1輪調度分配給各相應處理機節點的負載大小，M′為總調度輪數；c)為了縮短總調度長度，對最后一輪調度的剩余負載按各處理機節點的處理時間遞減原則進行分配，并盡可能使得所有worker同時完成工作。

3．1負載塊大小和調度輪數的確定

在負載調度過程中，根據UMR算法計算每一輪調度分配給各個處理機節點的負載初始值chunk′ji。如果存在chunk′ji大于處理機節點i的可用內存容量，那么第j~M′-2輪調度的各個負載塊的取值均等于第j-1輪調度時相應的負載塊大小。

4實驗

本文通過在異構PC機群系統上實現、運行兩個矩陣A和B（A和B中的元素為實數數據）的乘積算法，考察處理機不同計算速度、通信能力和存儲容量等因素對調度算法總調度長度的影響，評測本文提出的調度算法UMRLM的性能并與UMR算法進行比較。為了綜合考察這三種因素對調度性能的影響，本文根據c1×Si+c2×Bi+c3×bufi （i=1~N）值的降序來確定處理機的調度順序。其中：c1、c2和c3為權值常數。當c1最大時表示優先考慮處理機的計算速度較快的處理機節點；c2最大時表示優先考慮鏈路通信速率較大的節點；c3最大時表示優先考慮可用存儲容量較大的處理機節點。

為了能更好地評測調度算法的性能，實驗不考慮矩陣相乘結果的返回，并假設矩陣B預先存儲在各從處理機節點中。對矩陣A以行為單位進行劃分，即一行代表一個任務，調度過程中把矩陣A的各行發送到各處理機節點與B作乘法運算。所有的實驗在由4臺HP DX系列PC機（CPU:P4 3．0 GHz，內存:512 MB）、2臺IBM Netvista A系列的PC機（CPU：P4 2．0 GHz，內存:256 MB）和10臺IBM Netvista M系列PC機（CPU均為P4 2．4 GHz。其中有兩臺內存大小均為1 GB、其余各臺內存大小都是512 MB）通過100 Mbps以太網互連組成的異構集群計算系統實現，各個處理機節點運行的操作系統為Red Hat Linux 9，編程環境為C語言+MPI。

在實驗中，對于從處理機，設其中2臺HP DX序列的PC機和2臺內存大小為1 GB的IBM Netvista M系列PC機的可用最大內存容量分別能夠存儲1 100行的矩陣元素（每行有1 500個元素）、10臺IBM Netvista M系列和1臺HP DX系列PC機的最大可用內存容量分別能夠存儲825行矩陣元素、2臺IBM Netvista A系列PC機最大可用內存容量分別能夠存儲550行的矩陣元素，實驗結果如圖3~9所示。圖3~6給出的是當從處理機個數分別為6、9、12和15時，本文提出的UMRLM和UMR算法的調度時間圖。從圖中可以看出UMRLM算法在同時考慮處理機內存受限的情況下仍能取得與UMR算法相當的調度時間。圖3~6的實驗結果表明，當負載量較大，使得某一輪調度分配給某個處理機的負載超出了該處理機實際可用內存容量時，UMR算法無法繼續執行。例如，在6個從處理機的情況下，UMR算法最多只能處理到6 000行的矩陣規模，而UMRLM算法將不受此限制，能夠處理更大規模的負載。

從圖7可知，當負載量固定時，UMRLM和UMR算法的調度時間都隨處理機個數增加而逐漸減少。圖8的實驗結果給出了當處理機個數為15時，按照不同權重確定處理機分配順序時的調度時間圖。從圖8可以看出，在綜合考慮了處理機計算速度、通信能力和存儲容量的情況下，當分別按照處理機計算能力優先、通信能力優先和存儲能力優先來確定處理機分配順序時，應用的調度時間差別不是很明顯，但以計算能力優先（c1=0．8，c2=c3=0．1）確定的處理機順序分配任務時的調度時間要略優于以通信能力優先和存儲能力優先確定的處理機順序進行任務分配時的調度時間。圖9給出了處理機個數為15、矩陣規模為10 000行、逐漸增大處理機的最小實際可用內存容量時調度時間的變化情況。從圖9可以看出，處理機實際可用最小內存的增大對調度時間幾乎沒有什么影響。

綜上所述，本文提出的UMRLM算法不但能取得與UMR算法相當的漸近最優調度時間長度；同時由于UMRLM算法的設計綜合考慮了處理機實際的計算速度、通信能力和可用存儲容量等因素，它能夠處理更大規模的應用負載。

5結束語

針對處理機具有不同的計算速度、通信能力和存儲容量的更實際的異構集群系統，在均勻多輪調度算法UMR的基礎上，通過允許計算和通信操作重疊執行，采取多次并行分配計算任務的方法，本文提出一種可分負載多輪調度算法UMRLM。在異構PC機群系統上的實驗結果表明，一方面，UMRLM算法在調度時間上取得了與UMR算法相當的漸近最優的調度時間長度；另一方面，由于UMRLM算法的設計同時還考慮了處理機實際可用內存容量的因素，能夠處理更大規模的應用負載，實用性更強。

參考文獻：

[1]ROBERTAZZI T G. Ten reasons to use divisible load theory[J]. Computer， 2003，36(5):63－68.

[2]BHARADWAJ V， GHOSE D， ROBERTAZZI T G. Divisible load theory: a new paradigm for load scheduling in distributed systems[J]. Cluster Computing， 2003，6(1):7－17.

[3]BHARADWAJ V， GHOSE D， MANI V， et al. Scheduling divisible loads in parallel and distributed systems[M]. Los Alamitos: IEEE Computer Society Press， 1996.

[4]BEAUMONT O， LEGRAND A， MARCHAL L， et al. Independent divisible tasks scheduling on heterogeneous star－shaped platforms with limited memory[C]//Proc of the 13th Euromicro Conference on Pa－rallel， Distributed and Network－based Processing. Los Alamitos: IEEE Computer Society Press， 2005:179－186.

[5]DROZDOWSKI M， WOLNNIEWICZ P. Divisible load scheduling in systems with limited memory[J]. Cluster Computing， 2003，6(1):19－29.

[6]LEGRAND A， YANG Y， CASANOVA H. NP－completeness of the divisible load scheduling problem on heterogeneous star platforms with affine costs， CS2005－0818[R]. Berkeley: University ofCalifornia， 2005.

[7]YANG Yang， CASANOVA H. A multi－round algorithm for scheduling divisible workload applications: analysis and experimental evaluation， CS2002－0721[R]. Berkeley: University of California， 2002.

[8]YANG Yang， van der RAADT K， CASANOVA H. Multiround algorithms for scheduling divisible loads[J]. IEEE Trans on Parallel and Distributed Systems， 2005，16(11):1092－1102.

[9]YANG Yang， CASANOVA H. UMR: a multi－round algorithm for scheduling divisible workloads[C]//Proc of the International Parallel and Distributed Processing Symposium. Los Alamitos: IEEE Compu－ter Society Press， 2003:24－32.

[10]YANG Yang， CASANOVA H. RUMR: robust scheduling for divisible workloads[C]//Proc of the 12th IEEE International Symposium on High Performance Distributed Computing. Los Alamitos: IEEE Computer Society Press， 2003:114－123.

[11]YAO Jin－nan， VEERAVALLI B. Design and performance analysis of divisible load scheduling strategies on arbitrary graphs[J]. Cluster Computing， 2004，7(2):191－207.

[12]BEAUMONT O， LEGRAND A， ROBERT Y. Optimal algorithms for scheduling divisible workloads on heterogeneous systems[C]//Proc of International Parallel and Distributed Processing Sysmposium. Los Alamitos: IEEE Computer Society Press， 2003:98－111.

[13]BEAUMONT O， LEGRAND A， ROBERT Y. Sche－duling divisible workloads on heterogeneous platforms[J].Parallel Computing， 2003，29(9):1121－1152.

[14]DROZDOWSKI M， WOLNIEWICZ P.Optimum divisible load schedu－ling on heterogeneous stars with limited memory[J]. European Journal of Operational Research， 2006，172(2):545－559.

[15]BEAUMONT O， MARCHAL L， ROBERT Y. Scheduling divisible loads with return messages on heterogeneous master－worker platforms， N 2005－21[R].[S.l.]: Laboratoire de l′informatique du paralléli－sme， 2005.

[16]LI X， BHARADWAJ V， KO C C. Divisible load scheduling on single－level tree networks with buffers constraints[J]. IEEE Trans on Aerospace and Electronic Systems， 2000，36(4):1298－1307.

[17]VEERAVALLI B， YAO Jin－nan. Divisible load scheduling strategies on distributed multi－level tree networks with communication delays and buffer constraints[J]. Computer Communications， 2004，27(1):93－110.

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