基于遺傳算法的批處理科學工作流任務調度算法的改進

熊聰聰，陳長博，趙 青，林 穎

(天津科技大學人工智能學院，天津 300457)

基于批處理的工作流廣泛應用于多個領域，尤其是在數據分析應用中，例如移動領域、電子商務和科學研究，其原理是通過一系列的連接操作來處理大量數據[1].科學領域的計算任務通常被建模為科學工作流形式，其任務根據數據流與計算相關性形成鏈式結構，由于科學計算領域通常存在數據量巨大和計算復雜度高的問題，需要高性能計算環境支持運行[2].兩者最主要的區別為：科學工作流主要以數據為中心，而傳統工作流更注重業務過程的自動化.云計算作為近年來最火熱的網絡服務方式為科學工作流提供了高效、高性價比、可擴展的運行支撐環境[2-3].當前，基于云平臺的科學工作流的調度研究已成為一個研究熱點，國內外已有很多成果面世.例如，2018 年Anwar 等[4]提出了一種基于工作流程(DSB)的任務包的動態調度策略，用于調度科學的工作流，目的是在用戶定義的期限約束下最小化租賃虛擬機的租用成本.Liu 等[5]提出了一種新的基于任務回填的科學工作流調度策略，使用task backfill 算法在虛擬機實例上聚合多個任務，使用合適的性能，并利用單個任務填充虛擬機的空閑時間槽，在不影響整體性能的情況下提高資源利用率.Zhao 等[6-7]針對異構云環境，提出了一種基于數據依賴聚類和遞歸劃分的數據聚類算法，并將數據大小和固定位置的因素結合起來.然后，提出了一種啟發式的樹對樹數據布局策略，以使頻繁的數據移動發生在高帶寬的信道上.之后，又在此基礎上提出了面向科學工作流模型的任務調度算法[8]，可以在提高執行效率的同時，提高計算資源利用率，減少能源消耗.

然而，隨著大數據時代的到來，一種新型的科學工作流模型——批處理科學工作流逐漸引起人們的注意.為了提高大數據時代數據密集型應用的計算效率，工作流中的很多任務需要通過數據劃分為可并行處理的任務組，從而在原始簡單的有向無環圖(directed acyclic graph，DAG)上形成了一個個包含批處理操作的寬節點結構.

當前，關于批處理科學工作流的云調度研究正處于起步階段，傳統科學工作流調度中的deadline 劃分、虛機映射等方法并不適合于批處理科學工作流模型.因此，本文將重點關注批處理科學工作流的特征，在研究批處理科學工作流任務調度過程中，盡可能滿足用戶所提供的deadline 的情況，尋找調度成本最低的虛擬機資源分配方式.云批處理科學工作流的任務調度包括兩個層次：一是任務包與VM 之間的映射，二是在單個VM 上的順序執行[9].本文重點關注第一個層次，在滿足或相對滿足任務截止期的情況下，工作流調度的成本最優化，尋找最優調度方案.

相關研究中，Mao[10]開發了一個工作流計算系統GreePipe，該系統可以將工作流描述自動轉換成一系列基于Hadoop 的MapReduce 任務，實現生物研究領域復雜的數據分析邏輯.該工作流屬于不可拆分工作流.對于可拆分批處理工作流，大多數工作都直接采用更細的粒度進行建模，并直接采用一些非線性的DAG 圖進行表示，并作為多個單獨的MapReduce 任務處理，這樣的建模方式，丟失了批結構信息.雖然很多針對一般工作流的調度算法可以用于批處理工作流，但是，由于沒有考慮批處理工作流的批結構特點，容易導致較低的資源利用率.

Cai 等[11]提出了一種最少新租賃時間區間優先規則、最便宜執行成本優先規則和剩余時間片長度和執行時間匹配度優先規則的混合式啟發算法.但是，該算法初始虛擬機資源分配方案的原則是選用最多的性能最差的虛擬機類型，并以最大并行度的方式執行批處理任務調度.如果調度時間超出了用戶提出的deadline，就會升級關鍵路徑上任務節點使用的虛擬機類型.因此，最終所得解傾向于租用大量低成本的虛擬機類型，容易陷入局部最優.

與上述已有方法相比，本文改進了遺傳算法中的初始種群生成過程，使初始種群覆蓋面更廣；優化適應度函數，使其更適合評估批處理科學工作流下的個體適應度值；引入非關鍵路徑虛擬機使用數量收縮操作，在不影響關鍵路徑的前提下進一步減少任務調度成本.

1 批處理科學工作流任務調度模型任務模型

為了方便描述，對批處理科學工作流進行如下建模：

(1)圖1 為一個標準的批處理科學工作流DAG，對于一個標準的DAG 圖來說，入口節點是其他所有任務的前驅節點，其優先度是最高的，故在所有任務節點中入口節點應該最先獲得調度，出口節點與之同理.

(2)需要進行任務調度的任務批為 T = (t1, t2,…,tn)，其中 ti代表編號為i 的任務節點.在每一個任務節點上包含若干個子任務，即ti(k )代表ti任務節點上的第k 個任務包.

(3)定義批處理科學工作流為有向無環圖DAG，任務節點ti為有向無環圖DAG 上的一個節點.

(4)假設云平臺提供m 種不同類型的虛擬機，將任務節點ti上的q 個子任務調度到不同虛擬機上的期望運行時間(t)是一個q×m 的矩陣，其計算公式見式(1).矩陣的第i 行表示任務節點i 的所有子任務在每一種虛擬機上的預測執行時間；而第j 列表示每個任務節點的所有任務在單個第j 類虛擬機上運行所需的預估時間.預估時間由兩部分組成，一部分為單個虛擬機執行任務所必需的時間，第二部分為虛擬機啟動和安裝軟件的時間.

圖1 標準批處理科學工作流DAG圖Fig.1 DAG diagram of standard batch processing science workflow

2 批處理科學工作流任務調度

遺傳算法是受達爾文進化論啟發進而產生的一種全局搜索和優化算法.它把每一個總群內的個體看作一種解，通過模仿自然界中優勝劣汰的法則，使優秀的個體留下，并進行交叉變異繼續尋找更優解，同時將劣質的個體淘汰，最終通過不斷的算法迭代得到最優解[12].

本文采用基于改進遺傳算法的智能啟發式算法，以盡可能搜索到在盡量滿足工作流整體deadline 要求前提下的任務調度總成本最優的虛擬機資源分配方案，對可隨意分割的批處理科學工作流任務調度和不可隨意分割的批處理科學工作流任務調度進行論述.可隨意分割的批處理科學工作流是指：在該科學工作流上的每一個節點上的任務包可以根據虛擬機數量隨意分割進行并行處理，使得每個虛擬機上的負載是均衡的.不可隨意分割的批處理科學工作流是指：在該科學工作流上的每一個節點上有一定數量的任務包，任務包不可分割.在本文中假設每個任務包的處理時間是相同的.

2.1 可隨意分割批處理科學工作流調度

2.1.1 編碼方式

本文采用整數編碼的方式，編碼長度取決于任務節點數.每一條染色體都對應一個任務解.假設任務節點數N＝5，可用虛擬機類型數量為M＝6，則染色體(1，3，2，4，3，3，4，1，5，2)代表在任務節點一上使用3 個1 號虛擬機并行執行，在任務節點二上使用4個2 號虛擬機并行執行，在任務節點三上使用3 個3號虛擬機并行執行，在任務節點四上使用1 個4 號虛擬機串行執行，在任務節點五上使用2 個5 號虛擬機并行執行.

2.1.2 優化初始種群生成

傳統遺傳算法的初始種群生成可能存在初始種群生成覆蓋度不夠廣、初始種群生成重復率高的缺點，從而導致算法無法收斂到全局最優解.本文對遺傳算法的初始化種群處理如下：

為了保證初始解距離最優解距離不至于太遠，在生成初始解的過程中引入時間成本比概念，即采用滿足任務執行需求的最低端配置虛擬機類型，在增加虛擬機使用數量的同時與串行執行相比，調度時間減少量與成本增加量之間的比值.

(1)在生成初始解時選取三分之一初始解為每個任務節點選取一個時間減少量與成本增加量之間的比值，并選取比該比值小的所有虛擬機使用類型方案，按照任務節點順序以全組合方式生成初始解.其主要目的是使這一部分生成的初始種群先天就相對較優，提升算法的收斂速度和準確度.

(2)在批處理科學工作流任務調度每一個任務節點內所包含的任務包對應需求的虛擬機類型可能不同，例如有些任務節點所包含的任務為數據密集型任務，有的則為計算密集型，因此在云提供商平臺中會提供各種側重點不同的虛擬機類型.為了進一步保證初始解相對較優，三分之一初始解按照每個任務節點所對應需求類型的虛擬機類型進行隨機生成.

為了保證初始解的隨機性，三分之一初始解按照完全隨機的方式進行初始解生成.

2.1.3 適應度函數

在遺傳算法中，適應度函數是用來衡量一個解的好壞的，本文以調度成本最優以及調度時間盡量滿足截止期為優化目標，由于在該模型下，每個任務節點開始進行任務調度的時間依賴于前序節點的結束時間且任務節點與任務節點之間可以并行執行，因此整個批處理科學工作流的任務調度完成時間取決于該批處理科學工作流關鍵路徑上的任務節點進行任務調度的總時間.而對于同一個批處理科學工作流來說，關鍵路徑的選擇取決于虛擬機的具體配置情況，比如：給定一個批處理科學工作流，在該科學工作流中至少存在一條或多條路徑可以從初始節點通往最終節點，而在某種虛擬機類型和數量的配置下對于該科學工作流，其從初始節點通往最終節點耗時最長的一條路徑為該科學工作流的關鍵路徑，耗時即為該科學工作流的調度總時長.

第y 個任務節點使用j 個i 類虛擬機的執行任務所需時間(ty)的計算公式見式(2).

式中：tyi為單個i 類虛擬機執行第y 個任務節點所需的預估時間；tbi為虛擬機的啟動以及執行軟件的安裝時間.

任務調度總時間為該批處理科學工作流上關鍵路徑節點任務調度所需時間之和.

第y 個任務節點使用j 個i 類虛擬機的執行任務所需的總費用(Cy)的計算公式見式(3).

式中：a 為虛擬機的租用周期；ci為第i 類虛擬機單個租用周期的單價.

總費用Ctotal為每個任務節點的費用的連續累加和，其計算式見式(4).

由上，定義適應度函數fitness 為

式中：w1與w2為兩個實數，兩數相加之和為1；Tdeadline為用戶所提供的調度該批任務所要求的deadline 與任務批開始進行調度的時間差值，單位為min；Ttotaltime為任務調度總時間，單位為min；Max 代表取括號內兩數中較大的.下文在交叉概率函數中用f 簡化表示.

2.1.4 遺傳算法的交叉變異

(1)由于編碼方式為每兩位數字代表一組信息，因此本文的交叉掩碼取值為隨機偶數.交叉概率函數(P)的計算公式見式(6).

式中：k1、k2為常數；fmax為種群最大適應度值；fav為群體平均適應值；f ′為要交叉的兩個個體中較大個體的適應度值.當 f ′大于等于fav，應該讓交叉概率P較小，防止適應度值大的個體統治群體，陷入局部最優解；反之，則應該讓交叉概率較大，以重組出新的個體，擴展搜索空間.

(2)變異操作：本文的變異操作采用的是基本位變異，選取一定百分比的個體隨機變異染色體編碼的偶數位，即代表使用某種虛擬機類型數量的表示位，變異方式是將該位數字隨機加減 1，本文選取3%.這樣做的好處是變異后的染色體適應度值變得更好的概率較高.

2.1.5 非關鍵路徑虛擬機使用數量的收縮

為了進一步優化遺傳算法通過迭代次數所得出的最優解，提出了一種非關鍵路徑虛擬機使用數量收縮的方法.在遺傳算法通過多次迭代得出一個最優解后，在不改變關鍵路徑的情況下，將非關鍵路徑上使用的虛擬機數量按照單價由高到低不斷收縮，直到再次收縮將會改變該解的關鍵路徑便停止收縮并輸出最優解.

2.2 不可隨意分割批處理科學工作流調度

與可隨意分割批處理科學工作流相比，不可隨意分割批處理科學工作流每個任務節點所包含的任務包由于內部的數據關系，任務包不可隨意分割.也就是說在執行調度時，每個任務包只能放在一個虛擬機上進行處理，所以在把任務調度到虛擬機上時，與可隨意分割批處理科學工作流有區別.調度算法具體區別如下：

(1)在本文中，為了更好地使最終解所得到的調度成本最低以及時間盡量滿足用戶所給出的截止期，采用任務平均分配至每個虛擬機上的分配方式.具體分配方式如圖2 所示.由于任務包不可隨意分割，調度到每臺虛擬機上的任務包數量可能不同，所以每個任務節點所需的調度總時間取決于該任務節點上所使用的耗時最長的虛擬機.

(2)由于不可隨意分割批處理科學工作流每個任務節點子任務的不可隨意分割性，所以在改進遺傳算法的變異過程中所采取的基本位變異就有了上限，即虛擬機使用數量不能超過子任務數量，所以當變異位數已經達到上限，則默認虛擬機使用數量變異只能減1.

圖2 虛擬機分配方式Fig.2 Virtual machine allocation mode

3 仿真實驗

使用Matlab 驗證本文所提模型以及算法的有效性.所有進行實驗的批處理科學工作流均為隨機生成，虛擬機類型與單周期租賃費用為亞馬遜云上選取的實例，共選取了五類具有代表性的虛擬機類型.將Tdeadline設置為100 min.亞馬遜云真實實例具體數據見表1.

表1 亞馬遜云資源真實實例數據表Tab.1 Amazon cloud resources real instance data sheet

表中數據全部來源于亞馬遜云官方提供的云資源的真實數據，其中vCPU 代表虛擬機CPU，每個虛擬機都有內存，單位為GiB，帶寬主要影響虛擬機之間的傳輸速度，單位為Mbps.

本文在Matlab 平臺上模擬實現了改進的遺傳算法的可隨意分割批處理科學工作流任務調度與不可隨意分割批處理科學工作流任務調度算法，同時還原了任務可隨意分割按比例劃分截止期經典調度算法與任務不可隨意分割按比例劃分截止期經典調度算法，并與之進行對比.用于實驗的批處理科學工作流是通過Cai 等[11]使用的批處理科學工作流生成器完全隨機生成的.按比例劃分截止期經典調度算法在執行虛擬機資源配置時主要是根據待執行任務量大小，即任務節點內任務執行時間預測值與任務個數的乘積，然后按照所占總任務量的百分比進行分配截止期的長短，最終按照所分得的時間配置虛擬機使其滿足相應分得的截止期.4 種算法的調度成本如圖3所示.

圖3 調度成本對比圖Fig.3 Scheduling cost comparison chart

任務調度成本是在某一特定數目任務節點時生成的批處理科學工作流下，算法運行100 次所取的平均值.由于按比例劃分截止期經典調度算法劃分截止期的方式簡單的按照任務規模按比例分配截止期，且配置虛擬機類型與數量只是簡單按照是否滿足截止期配置，因此耗費的成本就會相對較高.本文所提的改進后的遺傳算法的不可隨意分割批處理科學工作流任務調度算法，由于其搜索空間廣且能并重虛擬機升級與并行度，且在算法得出最優解后進一步對非關鍵路徑上所使用的虛擬機數量進行收縮，進一步縮減成本，所以解的效果要好一些；而基于遺傳算法的可隨意分割任務調度算法，由于模型相對理想化，所以在使用虛擬機類型時算法會比較偏向選擇價格低但并行度高的方式處理任務.亞馬遜云資源的實際標價并不是線性增加的，因此可隨意分割BIGA 算法的調度成本會低于不可隨意分割BIGA.

為了證明算法的有效性，圖4 為改進遺傳算法的成本調優圖，具體實驗數據為在任務節點數為5 的隨機10 個批處理科學工作流生成1 000 次初始解，其中每個批處理科學工作流生成100 次，并計算這些初始解的平均調度成本，然后進行算法迭代，觀察隨著算法迭代次數的不斷增加，解的平均調度成本的變化.從圖4 可以看出改進遺傳算法通過一定次數的迭代，與最初始解相比成本縮減了近90%.

圖4 成本調優圖Fig.4 Cost tuning diagram

為了檢驗本文種群初始化算法的有效性，將經過本文所提的初始化種群優化方法的可隨意分割批處理科學工作流任務調度算法和不可隨意分割批處理科學工作流任務調度算法與其他部分不變初始化種群為隨機生成的兩組算法所得的最終解的調度成本進行對比，圖5 和圖6 為基于改進遺傳算法的可隨意分割批處理科學工作流任務調度與不可隨意分割批處理科學工作流任務調度算法進行1 000 次初始種群優化與不進行初始種群優化的效果對比圖.

由圖5 和圖6 可以看出：兩種算法經過初始種群優化后所得的最終解均要大幅優于未經初始種群優化的算法，其原因主要是經過初始種群優化后所生成的初始種群不僅具有隨機性，同時與隨機生成的初始種群相比，大部分個體都相對更為優秀，這就使得在這樣的種群中進行交叉變異更容易產生優秀解，一定程度上避免了算法陷入局部最優的可能性.

圖5 可隨意分割BIGA 初始種群優化與未優化最終成本對比Fig.5 Final cost comparison of optimized and unoptimized freely split BIGA initial population

圖6 不可隨意分割BIGA 初始種群優化與未優化最終成本對比Fig.6 Final cost comparison of optimized and unoptimized not freely split BIGA initial population

最后，針對本文算法的執行效率問題，通過實驗對比了4 種算法的執行效率，結果如圖7 所示.

圖7 執行效率對比Fig.7 Comparison of performance efficiency

由圖7 可以看出：兩種任務不可隨意分割的任務調度算法的執行效率要明顯高于另外兩種可隨意分割的任務調度算法，且兩種任務可隨意分割的任務調度算法隨著任務節點數的增加其執行效率也會降低，而任務不可隨意分割的兩種任務調度算法則沒有顯著影響.其原因是在進行任務調度虛擬機資源配置計算時，由于任務不可隨意分割的兩種任務調度算法其任務組內的子任務不可隨意分割，導致虛擬機配置數量上限受到子任務數影響，所以其解搜索空間相對較小；而任務可隨意分割的兩種任務調度算法則相反，其解空間隨任務節點數的增加指數增大，所以相應的耗時也就更大.另外，由于隨著任務節點數的增大，其搜索空間是指數增大，所以耗時也會越來越多.

4 結 語

通過以上理論和實驗分析，按比例劃分截止期經典調度算法解的生成方式簡單，且資源分配方案隨機性太大，而所提的兩種任務調度算法優化了初始解的生成，使得初始解不至于離全局最優解太遠，加快了算法的收斂速度.同時，通過并重虛擬機升級與并行度調整兩種操作使最終解更趨近于全局最優，因此在任務調度成本上要比前者少.下一步將重點研究數據密集型批處理工作流任務關聯度聚類與本文方法的結合，以縮減網絡傳輸耗時，從而更全面地解決批處理工作流的云調度問題.

致謝：本研究同時受到國家自然科學基金(11503051，61402325)、國家自然科學基金委員會-中國科學院天文聯合基金(U1531111，U1531115，U1531246，U1731125，U1731243)資助，一并致謝.