可任意劃分負載的調度模型、算法與應用

摘要:隨著數據并行應用需求的日益增長，可任意劃分負載的調度問題已經成為并行調度領域新的研究熱點#65377;回顧了可任意劃分負載調度的基本模型及近年來對這個基本模型的擴展性研究，并給出了它的應用研究和今后的發展方向#65377;

關鍵詞:可任意劃分負載;數據并行;調度

中圖分類號:TP316文獻標志碼:A

文章編號:1001-3695(2007)04-0204-05

0引言

調度問題是并行和分布式系統研究領域中最重要的問題之一#65377;最常用的對并行和分布式應用建模的工具是有向無環圖(DAG)和獨立任務集#65377;在一般情況下，基于這兩類模型的調度問題^[1，2]都是NP完全的，因此研究人員不得不借助啟發式算法來獲得一個“好”的調度方案#65377;

本文關注的是另一類重要的數據并行應用的調度#65377;這種應用所處理的負載是可以任意劃分的(Arbitrarily Divisible)，每個負載片都可以被單獨地處理，且負載中的所有元素所要求的處理類型相同#65377;所謂可以任意劃分，是指負載可以劃分成任意多個不相交的負載片，每個負載片可以有任意大小#65377;這類應用被稱為可任意劃分負載，簡稱可分負載(Divisible Load)#65377;

最早的可分負載調度(Divisible Load Scheduling，DLS)研究出現在1988年^[3]#65377;由于日益增長的數據并行應用的需求，近幾年來它已經成為并行調度領域新的研究熱點^[4~16]#65377;在大型實驗數據的處理#65380;圖像與信號處理#65380;數據挖掘#65380;計算生物學#65380;科學計算等領域中很多重要的應用都屬于可分負載#65377;可分負載的調度理論可以應用在從并行機到計算網格的各種計算平臺#65377;

一般而言，并行程序的調度問題是NP完全的#65377;但是由于DLS采用線性模型對應用和網絡建模，并且充分利用了負載可任意劃分的特性，可以使用連續數學的方法進行分析#65377;很多重要類型的DLS問題都可以獲得最優解的解析解，這是DLS獲得成功的主要原因之一#65377;另外，使用DAG和獨立任務集對程序建模，由于程序中存在分支等原因，參數的估算是一個復雜的問題#65377;雖然參數估計作為一個獨立的課題已經研究了多年，但是仍然不能準確判斷一個任務所需要的計算時間#65377;而且，DAG調度目前主要解決處理器的調度而很少考慮網絡上通信的競爭，這些原因使得現有算法得出的理論值與實際的運行情況有很大差異^[17]#65377;而在可分負載的調度中，程序運行和負載傳輸的時間僅與負載的大小有關，因此能夠比較準確地進行參數估算，可操作性強，從而能夠對應用準確建模#65377;實驗表明，DLS理論值與實際運行值之間的差異非常小，對于一些精心完成的實驗，這個差異小于10%^[18]#65377;隨著負載量的增加，這個差異逐漸降低#65377;當增加資源的數目時，由于可分負載的特性，DLS能表現出很強的可擴展性#65377;

1基本模型與結論

調度問題是與網絡的拓撲結構緊密相關的，可分負載的調度理論可以應用在從并行機到計算網格的各種計算平臺上#65377;星型(或稱為單層樹)網絡是其中一個重要的網絡類型，不僅因為大多數DLS研究都是基于星型網絡的^[7，19~23]，而且因為它涵蓋了很多重要的網絡類型，如總線網和廣域網上的分布式計算模型都是星型拓撲的例子#65377;下面以星型拓撲為例說明可分負載的分配模型與分配過程，其他網絡上的DLS問題在后文說明#65377;

星型網包含一個Master和一組Worker#65377;Master與每個Worker有一條鏈路連接#65377;Master記為p0，對于一個負載，Master首先選擇N個Worker用于處理負載，分別用pN，pN-1，…，p1表示，相應的通信鏈路分別記為lN，lN-1，…，l1，如圖1所示#65377;wi是第i個處理器相對于標準處理器的計算速度，zi是第i條鏈路相對于標準鏈路的傳輸速度#65377;Master可以通過不同的通信鏈路連接到Worker，但Master只有一個端口，即在同一時刻，Master只能與一個Worker進行通信#65377;所謂的標準處理器和鏈路是作為參照的任何一個處理器和鏈路，可以是網絡中的任何一個處理器或網絡，甚至為了方便可以是假想的處理器或鏈路#65377;

Master節點可以有前端(也稱為通信協處理器)也可以沒有前端#65377;在有前端的情況下，計算和通信在Master上是同時發生的#65377;Master首先將負載劃分成N+1個部分，在開始處理其負責的負載的同時按照某個順序向其他處理器發送負載片;在沒有前端的情況下，Master首先為其他處理器分配負載片，然后處理自己所負責的負載片#65377;不論Master是否有前端，其他處理器都是在接收到發送給它的負載后開始計算#65377;圖2給出了在Master有前端的情況下負載的分配和處理過程#65377;其中時間軸上部表示通信，下部表示計算#65377;將第i個處理器pi完成計算的時間記做Ti#65377;調度的目標是使整個負載的處理時間Tf最小，Tf是所有處理器完成計算的最大時間，即:Tf=max{T0，T1，…，TN}#65377;

定義Tcp是整個應用在標準處理器上完成的時間，Tcm是在標準鏈路上傳輸這個應用的全部輸入數據的時間，分配給處理器pi的負載的百分比記做αi#65377;因此αiwiTcp是第i個Worker處理相應負載的時間，αiziTcm是通過第i條鏈路向第i個Worker發送相應負載的時間#65377;多遍負載分配策略的時間圖如圖3所示#65377;

從上述的負載分配過程不難看出，可分負載的分配主要有以下三個問題需要解決:

(1)資源選擇

在同構網絡下(每條鏈路的傳輸速度都相同且每個處理器的計算速度也都相同)，應該使用全部處理器#65377;但是在異構網絡上，資源的選擇仍是一個未完全解決的問題#65377;最優的處理時間不一定需要利用所有的資源，可以僅在快的資源(鏈路和處理器)上達到#65377;Bharadwaj等人^[21]的研究部分解決了異構星型網絡下資源的選擇問題，給出了區分“快”“慢”資源的表達式#65377;

(2)網絡配置與負載的分配順序

按照不同的順序向Worker發送負載可能會產生不同的調度，另外網絡的不同配置(鏈路與處理器的不同組合)也會對調度結果產生影響#65377;文獻[21]研究了分配順序和網絡配置的問題，證明了在總線網上處理時間與分配順序無關#65377;而在鏈路傳輸速度不同的異構網絡上分成兩種情況:①不能改變網絡物理結構的情況，即配置是固定的，一個處理器所對應的鏈路不能改變#65377;在這種情況下，應按照鏈路速度的遞減順序發送負載#65377;②在可以改變網絡的物理結構的情況下，應按照wk+1≥wk和zk+1≥zk的順序來重新組織網絡，并按資源速度遞減的順序分配負載#65377;另外，如果Master也可以參加重排，那么應該選擇最快的處理器作為Master#65377;對于沒有前端的情況，文獻[21]也得到了類似的結果#65377;

(3)負載片大小的確定

確定了資源和分配順序之后的問題是如何確定每個負載片的大小#65377;Cheng等人^[24]通過假設所有的計算都在同一時間完成(即T0=T1=…=TN)，提出了一個在樹型網絡(星型是樹型的一個特例)下進行負載劃分的遞歸算法，其后文獻[20]給出了同構星型(總線)網絡下的解析解#65377;Sohn和Robertazzi^[19]通過引入等價處理器的概念嚴格地證明了根據這個假設可以獲得最優調度#65377;這個重要結論稱為最優性原理(Optimality Principle)#65377;利用這個結論和全部負載片之和等于1的約定，可以得到下面的方程組:

共有N+1個方程和N+1個未知數，所以可以得到αk=

(1+∑Ni=1∏Nj=1fj)k=0，1，…，N-1，αN=1/1+∑Ni=1∏Nj=1fj#65377;其中fj=(wj+zj×Tcm/Tcp)/wj-1#65377;最小完成時間為Tf=w0Tcp∏Nj=k+1fj1+∑Ni=1∏Nj=1fj#65377;

在前面的討論中，假設一個處理器只有在接收到全部分配給它的負載之后才能開始計算#65377;因此在負載量很大的情況下，后面的處理器需要等待很長時間才能開始計算#65377;利用負載可任意劃分的性質，可以將分配給一個處理器的負載繼續劃分，并分成多次向處理器發送負載片，每次只向它發送一小片負載#65377;這種分配策略通過盡可能地將計算與通信重疊從而最大程度地降低處理器的等待時間，最后降低總的負載完成時間，這種策略稱做多遍分配策略#65377;圖3給出了這個分配過程，其中將第j次分配給處理器pi的負載的百分比記做αi，j#65377;文獻[25]提出的MI算法首先利用了這一思想，但它的一個不足是向處理器發送負載的次數是人為指定的#65377;UMR算法^[4]假設在每次分配中負載片的尺寸都是相同的，并將負載的處理時間看做是處理器數目和分配次數的函數，利用Lagrange極值法獲得了近優的負載分配次數#65377;

2對基本模型的擴展

2.1仿射成本模型

在現實的網絡環境下，啟動時間是通信延遲的一個重要成分，此外進程在開始處理數據之前也可能需要先完成一些初始化工作#65377;因此將通信和計算模型分別定義為αiwiTcp+θcp和θiziTcm+θcm，θcp和θcm分別表示通信的啟動時間和計算的啟動時間#65377;為了與前面的線性模型有所區分，稱之為仿射成本(Affine Cost)模型#65377;

在星型和樹型網絡中采用仿射模型，處理器必須同時完成的條件仍然成立，但負載的分配順序仍是沒有完全解決的問題^[7]#65377;對于總線網，Blazewicz等人^[26]和Bharadwaj等人^[27]提出了用于確定可以分配給負載最大處理器的集合的遞歸公式和條件#65377;根據這個條件使用二分搜索獲得最大處理器集合的復雜度是O(log m)#65377;文獻[26]只考慮了通信啟動的時間，而文獻[27]既考慮了負載的通信又考慮了計算的啟動時間#65377;在仿射成本約束下，兩者都得到了在由N個處理器構成的系統中存在最優解的充要條件#65377;在總線網上，仿射成本模型與線性模型不同的是處理時間受負載分配順序影響#65377;文獻[27]對此進行了分析并獲得了最優解#65377;文獻[27]還給出了在不存在最優次序的情況下，一個可產生次優解的貪心算法#65377;Bharadwaj等人^[28]在Master有前端和沒有前端的兩種情況下分析了仿射模型對線性網絡的影響，得到了利用系統中全部處理器的充要條件#65377;

前文提到的UMR算法^[4]的另一個改進是在仿射模型下考慮多次分配策略#65377;

2.2考慮結果返回的調度

大多數DLS的研究都只考慮了輸入數據的傳輸階段和計算階段的調度，但對于絕大多數實際應用，Worker往往還需要向Master返回計算結果，即有一個輸出數據的傳輸階段#65377;不考慮輸出階段的調度，實際上是假設返回結果的時間與完成整個計算的時間相比可以忽略#65377;但對于很多應用，程序產生的結果和輸入數據的大小相同(如低層圖像處理#65380;矩陣計算)甚至更大(如3D場景渲染)#65377;

考慮結果的傳輸，除了要解決負載分配順序的問題外還要確定每個處理器按什么順序返回結果#65377;第一個研究這個問題的是文獻[29]，它解決了兩類特殊應用的最優調度問題:一類是通信時間是與消息大小無關的常量，典型的應用是數據庫的查詢處理，這種情況下按LIFO方式(最后接收負載的處理器最先返回結果)安排發送和接收階段是最優方法;另一類在總線網上且數據的傳輸沒有啟動開銷的情況，在這種情況下按FIFO(最先接收負載的處理器最先返回結果)方式是最優的#65377;對于這兩種情況，文獻[29]分別給出了最優的負載發送順序和解析解#65377;對于不滿足上述條件的應用，考慮結果傳輸階段的DLS仍是尚未解決的問題#65377;文獻[6]將單端口模型擴展到雙端口模型(Master有兩個端口，在使用一個端口向Worker發送消息的同時可以從另一個端口接收Worker的計算結果)，在此模型下分別得出了基于LIFO和FIFO策略的最優算法#65377;

2.3整數劃分

可分負載的一個特殊問題是分配給處理器的粒度(Granularity)#65377;粒度是可以分配給一個處理器的最小負載單位，也稱為可分因子(Divisible Factor)#65377;所有的可分負載分配文獻在求解最優調度時都假設這個粒度是無窮小，但是對于實際的應用這個假設顯然是不成立的#65377;例如，對于基于行的求解矩陣向量乘積算法，最少需要向處理器分配一個矩陣行#65377;因此，這帶來了一個怎樣將DLS獲得的實數劃分轉換成整數劃分的問題#65377;

Bharadwaj等人^[27]通過一個整數逼近技術來解決這個問題#65377;在這種情況下只能獲得次優解(處理器不在同一時刻停止)，對于總線網絡下的同構系統，使用整數逼近技術的誤差在±(wTcp+zTcm)內#65377;文獻[30]提出的算法PIA和IIA，分別將誤差降低至±[(mzTcm)/2+wcp]和±[zTcm+(kwTcp)/2]#65377;

2.4多任務與混合負載的調度

文獻[31]研究了總線網上的多個可分應用的批處理問題，它根據當前狀態決定采用單遍或多遍策略來分配下一個任務#65377;如果在第i個任務完成之前，有足夠的時間發送第i+1個任務的負載就采用單遍分配，否則采用多遍分配策略#65377;由于不同的任務調度順序會產生不同的完成時間，文獻[31]提出的啟發式算法能給出近優的調度順序#65377;文獻[8]提出了一個更復雜和更實際的網絡模型，并在此之上來解決多個可分負載的調度問題#65377;

到達一個計算機系統的任務不一定是同一種類型的#65377;例如，作業可能是不能劃分的(串行的)#65380;可以劃分為模塊的或是可以任意劃分的#65377;同一個作業的不同部分也可能有不同的類型#65377;Bataineh等人^[32]提出了一個同時調度串行負載和可分負載的算法，這個算法的中心思想是使所有的處理器首先處理可分負載，然后是串行負載#65377;不過在某些情況下，這個策略不一定能產生最優解#65377;在這些情況下，一部分處理器分配給串行負載，其他分配給可分負載#65377;這個分配依賴于串行負載的數量#65380;它們的完成時間和可分負載的總完成時間#65377;文獻[33]給出了一個在多處理器系統中同時調度可分任務和串行任務的算法，并證明這個算法的結果好于已有算法且其非常接近最優值#65377;

2.5其他的網絡拓撲

除了星型網，研究人員還將DLS問題擴展到了其他類型的網絡上，如線性陣列^[3]#65380;樹型網^[24]#65380;網格(Mesh)^[34]和超立方體^[35]，得到了負載分配#65380;處理時間#65380;加速比和處理器利用率等重要結果#65377;

至于分布式系統，Ghose^[9]研究了在系統參數(w和z)未知的環境下可分負載的調度問題#65377;其基本思想是使用探測技術，先將負載的一小部分發送給其他處理器，根據各節點的反饋來估計網絡參數，然后再按照最優的分配算法分配負載#65377;文獻[15]研究了網格計算環境下的可分負載分配問題#65377;文獻[5]開發了一個在網格上開發和部署可分負載應用的軟件APSTDV#65377;

3應用

3.1大型的矩陣向量乘積

求解大型矩陣-向量積在并行應用中尤其是科學計算中是非常重要的#65377;由于矩陣的大尺寸和計算處理的同構性，使得這個問題可以被看做是可任意劃分的#65377;考慮一個矩陣向量積b=Ax的計算，b是m×1的向量，A是m×n的矩陣，x是n×1的向量#65377;計算b的乘法和加法總數分別是mn和m(n-1)#65377;使用行劃分策略來分解這個問題:令A=(A1，A2，…，Am)T，x=(x1，x2，…，xn)T和b=(b1，b2，…，bm)T#65377;其中Ai是矩陣A的第i行，xi是向量x的第i個元素，bi是向量b的第i個元素#65377;bi可以按如下公式計算:bi=Aix， i=1，…，m，Aix是向量Ai和x的內積#65377;處理器Pi所處理的負載由矩陣A的行數mi給出，即Pi計算向量b的mi個單元，m0+m1+…+mp=m#65377;因此，對于上面所定義的矩陣—向量問題，負載分配方案由一個p+1元組(m0，m1，…，mp)給出了#65377;

文獻[36]在總線網上的四種情況下研究了矩陣向量乘積的調度問題:①矩陣和向量存在于所有的處理器上;②矩陣已經存在于每個處理器上，只需要向通過廣播向它們發送向量;③矩陣和向量都需要通過廣播發送到所有的處理器;④向量通過廣播，而矩陣通過一對一的通信方式#65377;文獻[36]分別給出了每種情況下的解析解，并進行了分析#65377;文獻[37]通過實驗證明了這些算法的時間性能，這個實驗在由Pentium 3計算機構成的網絡上使用200×100 000的矩陣驗證了文獻[36]的結果#65377;

3.2其他應用

文獻[38]研究了在總線網上有啟動開銷的情況下，劃分大圖像數據的問題#65377;使用行方式的劃分機制，得到了分配給處理器的最優像素數和最優處理時間的解析解#65377;文獻[12]的工作是在一個實際的異構環境下以邊緣檢測算法為例對這些理論進行了驗證，并與經典的平均劃分算法進行了比較，結果表明采用基于DLS得到的結果遠遠好于平均劃分#65377;

文獻[18]使用DLS處理模式匹配#65380;文件壓縮#65380;關系數據庫中的連接操作#65380;圖的著色和遺傳搜索等應用的調度#65377;這些實驗的負載處理時間的理論計算值與實驗值之間的差異在±30%以內，并且隨著負載的增加，這個差異逐漸降低，從而有力地證明了DLS對一些重要應用的適用性#65377;

4結束語

隨著數據密集型應用的重要性日益突顯，DLS的研究為這些應用的調度提供了一個有效的解決方案#65377;與大多數并行調度問題的啟發式解決方案不同，很多重要類型的DLS問題不僅可以得到最優解，而且能得到解析解，從而保證了調度結果的一致性#65377;

但是DLS仍然是一個充滿機遇和挑戰的研究領域#65377;除了在前文提到的一些尚未解決的問題之外，對DLS最優調度的證明仍局限在少數幾類網絡上#65377;雖然有理由認為這個結論可以推廣到其他一些更復雜的拓撲結構上，但仍需要嚴格的理論證明來支持#65377;隨著集群技術和網格技術的逐步發展，DLS對這種復雜網絡的建模與擴展也需要進一步研究及驗證#65377;此外，目前對DLS的驗證仍停留在仿真實驗階段，缺乏大型的#65380;實際的應用來證明它的真正潛力，因此DLS在各種實際計算平臺上的應用將是下一步研究的重要方向#65377;

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