陳彥橦，裴樹(shù)軍，苗 輝

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

1 引言

現(xiàn)代科學(xué)在天文學(xué)、地球科學(xué)、生物信息學(xué)等不同研究領(lǐng)域中運(yùn)行日益繁雜的大規(guī)模科學(xué)應(yīng)用，以模擬和分析現(xiàn)實(shí)世界的活動(dòng)，而科學(xué)工作流已被證實(shí)是建模和管理這些復(fù)雜問(wèn)題的最有效手段[1]?？茖W(xué)工作流通常由一組通過(guò)控制和數(shù)據(jù)依賴(lài)鏈接的粗粒度并行計(jì)算任務(wù)組成。隨著數(shù)據(jù)生產(chǎn)速度的提升和計(jì)算系統(tǒng)的日益復(fù)雜化，科學(xué)工作流越來(lái)越體現(xiàn)為大數(shù)據(jù)形式，如計(jì)算密集型和數(shù)據(jù)密集型[2]。科學(xué)家通常將科學(xué)工作流部署在傳統(tǒng)的分布式執(zhí)行環(huán)境，如集群和網(wǎng)格等平臺(tái)上，然而系統(tǒng)的建立所付出的代價(jià)是非常高昂的，且資源的擴(kuò)展性較差[3]。近年來(lái)隨著云計(jì)算技術(shù)的發(fā)展，其在性能和成本方面為科學(xué)工作流提供了相當(dāng)好的解決方案，云以虛擬機(jī)（virtual machines，VM）的形式為用戶(hù)提供計(jì)算資源，與傳統(tǒng)的分布式執(zhí)行環(huán)境相比，具有無(wú)限的計(jì)算和存儲(chǔ)資源、資源按需提供以及允許用戶(hù)彈性地獲取和釋放資源等優(yōu)點(diǎn)。雖然云環(huán)境有很多優(yōu)勢(shì)，但仍然存在某些需要通過(guò)預(yù)期調(diào)度策略解決的特定問(wèn)題，例如虛擬機(jī)實(shí)例采集延遲、虛擬機(jī)資源的異構(gòu)性及動(dòng)態(tài)按需提供等問(wèn)題。

工作流的調(diào)度主要包含兩個(gè)層次：一是任務(wù)與虛擬機(jī)實(shí)例之間的映射；二是單個(gè)虛擬機(jī)上任務(wù)的順序執(zhí)行。調(diào)度算法的眾多性能指標(biāo)中，用戶(hù)最關(guān)心的兩個(gè)指標(biāo)為工作流的完成時(shí)間和執(zhí)行代價(jià)。分布式資源上的工作流時(shí)間代價(jià)優(yōu)化調(diào)度是一個(gè)NP-hard問(wèn)題，對(duì)于這類(lèi)問(wèn)題，利用基于啟發(fā)式和元啟發(fā)式的調(diào)度算法能夠取得近似最優(yōu)解[4]。

相關(guān)研究中，文獻(xiàn)[5-7]提出基于逆向分層的截止期限約束費(fèi)用優(yōu)化算法TCDBL（temporal consistency based deadline bottom level）和 PBCO（path balance based cost optimization），將截止期限分解到各層，使費(fèi)用優(yōu)化問(wèn)題由全局轉(zhuǎn)化到局部。在此基礎(chǔ)上提出CACO（communication aware cost optimization）算法，采用動(dòng)態(tài)規(guī)劃收集任務(wù)與虛擬機(jī)匹配時(shí)產(chǎn)生的時(shí)間碎片，改善費(fèi)用優(yōu)化效果，但并未為任務(wù)設(shè)定優(yōu)先級(jí)來(lái)找到最佳調(diào)度順序。文獻(xiàn)[8-9]提出了基于部分關(guān)鍵路徑的調(diào)度算法IC-PCP（IaaS cloud partial critical paths）和CPC（critical path cut），將局部關(guān)鍵路徑中的任務(wù)都安排在同一個(gè)費(fèi)用最低的VM實(shí)例上，避免了任務(wù)間的通信成本，但多條部分關(guān)鍵路徑分配到不同VM上時(shí)，由于任務(wù)間的數(shù)據(jù)傳輸將導(dǎo)致較低的任務(wù)調(diào)度成功率。文獻(xiàn)[10-11]提出自適應(yīng)調(diào)度算法 MOEA（multi-objective evolutionary algorithms）和UQMM（uncertainty-based quality of service Min-Min），用于在異構(gòu)多云環(huán)境中實(shí)現(xiàn)用戶(hù)定義約束的任務(wù)調(diào)度，使算法具有更高的適用性。

近年來(lái)，很多學(xué)者側(cè)重于利用智能搜索算法解決調(diào)度問(wèn)題。文獻(xiàn)[12-13]提出基于蟻群的元啟發(fā)式算法，放寬截止期限引導(dǎo)搜索朝著約束方向優(yōu)化。文獻(xiàn)[14]提出基于粒子群的最優(yōu)調(diào)度算法，利用關(guān)鍵路徑進(jìn)行粒子初始化和搜索階段的篩選處理，提高搜索結(jié)果的精度和降低搜索的計(jì)算時(shí)間。文獻(xiàn)[15]提出一種模擬退火遺傳改進(jìn)算法SA（simulated annealing），將模擬退火算法與遺傳算法相結(jié)合，用以解決工作流的多目標(biāo)優(yōu)化問(wèn)題。雖然這些方法都具有良好的表現(xiàn)，但與其他基于啟發(fā)式的方法相比，智能搜索算法在初始化階段耗時(shí)過(guò)多。

針對(duì)異構(gòu)云環(huán)境下科學(xué)工作流截止時(shí)間約束的代價(jià)優(yōu)化調(diào)度問(wèn)題，本文提出了基于約束關(guān)鍵路徑的代價(jià)優(yōu)化算法（cost-optimized scheduling algorithm based on constrained critical path，CSACCP）。算法分為兩個(gè)階段：第一階段設(shè)定任務(wù)的向上權(quán)值，根據(jù)權(quán)值將工作流分解為約束關(guān)鍵路徑（constrained critical path，CCP）集合。第二階段在滿(mǎn)足截止期限約束的條件下，通過(guò)最小費(fèi)用增長(zhǎng)代價(jià)和及時(shí)完成的VM選擇策略，結(jié)合首次適應(yīng)插入算法，實(shí)現(xiàn)每條約束關(guān)鍵路徑與最優(yōu)VM的匹配。

2 系統(tǒng)模型

2.1 科學(xué)工作流模型

科學(xué)工作流通常用有向無(wú)環(huán)圖（directed acyclic graph，DAG）進(jìn)行描述，表示為G=(T,E)，其中T={t1,t2,…,tn}表示一個(gè)含有n個(gè)任務(wù)節(jié)點(diǎn)的有限集，E={eij|ti,tj∈T}表示任務(wù)之間數(shù)據(jù)依賴(lài)關(guān)系的有限邊集。每條數(shù)據(jù)依賴(lài)邊eij=(ti,tj)代表任務(wù)ti和任務(wù)tj之間的數(shù)據(jù)控制依賴(lài)關(guān)系，其中任務(wù)ti稱(chēng)為tj的直接前驅(qū)，任務(wù)tj是ti的直接后繼。用pred(ti)表示任務(wù)ti的直接前驅(qū)集合，succ(ti)表示任務(wù)ti的直接后繼集合。|eij|表示兩個(gè)任務(wù)之間的數(shù)據(jù)傳輸量。

在一個(gè)給定的DAG工作流中，一個(gè)不存在任何前驅(qū)任務(wù)的任務(wù)稱(chēng)為入口任務(wù)tentry，一個(gè)不存在任何后繼任務(wù)的任務(wù)稱(chēng)為出口任務(wù)texit。若一個(gè)DAG中存在多個(gè)入口任務(wù)或多個(gè)出口任務(wù)，則需要增加一個(gè)虛擬任務(wù)（計(jì)算和通信開(kāi)銷(xiāo)都為0）來(lái)保證DAG在進(jìn)行調(diào)度時(shí)有唯一的入口任務(wù)和出口任務(wù)。

一個(gè)擁有11個(gè)任務(wù)的簡(jiǎn)單工作流如圖1所示，每個(gè)節(jié)點(diǎn)代表一個(gè)任務(wù)，邊上的權(quán)值代表兩個(gè)任務(wù)之間的數(shù)據(jù)傳輸量。

Fig.1 Sample workflow圖1 工作流示例

2.2 云資源模型

云資源以m種異構(gòu)的VM形式提供VMSET={VM1,VM2,…,VMm}，每個(gè)VM類(lèi)型，在其CPU性能、內(nèi)存容量和資源定價(jià)等方面都擁有自身配置。資源定價(jià)基于Amazon EC2中按需提供的定價(jià)模型，用戶(hù)根據(jù)VM租賃時(shí)間間隔（timeinterval）的數(shù)量付費(fèi)。同時(shí)當(dāng)VM租用時(shí)，需要一個(gè)引導(dǎo)時(shí)間對(duì)VM進(jìn)行初始化以便用戶(hù)使用，用戶(hù)可根據(jù)需要部署相應(yīng)的軟件資源。

由于云服務(wù)商提供獨(dú)立于VM生存期的存儲(chǔ)服務(wù)，例如EBS（elastic block store），因此當(dāng)輸入數(shù)據(jù)文件傳輸?shù)较鄳?yīng)的存儲(chǔ)資源時(shí)，要執(zhí)行子任務(wù)的VM不需要處于活動(dòng)狀態(tài)。此外由于用于存儲(chǔ)輸入輸出數(shù)據(jù)的存儲(chǔ)資源所需的成本與調(diào)度算法無(wú)關(guān)，因此在此模型中未考慮。假設(shè)所有計(jì)算和存儲(chǔ)服務(wù)都位于同一數(shù)據(jù)中心或區(qū)域，計(jì)算服務(wù)之間的平均帶寬基本相同，用β表示。當(dāng)兩個(gè)具有數(shù)據(jù)依賴(lài)關(guān)系的任務(wù)所選的VM實(shí)例不同時(shí)就會(huì)產(chǎn)生通信開(kāi)銷(xiāo)，則此時(shí)兩任務(wù)之間通信開(kāi)銷(xiāo)如式（1）所示：

表1給出了實(shí)驗(yàn)中使用的Amazon EC2所提供的5種VM資源類(lèi)型的相關(guān)參數(shù)，其中一個(gè)ECU單元相當(dāng)于1 GHz Xeon CPU的性能。

Table 1 Types of VM表1 VM類(lèi)型

將VMSET中每個(gè)VMk定義為一個(gè)二元組(EXT(ti,VMk),Cost(VMk))，其中EXT(ti,VMk)表示任務(wù)ti在資源類(lèi)型為VMk上的預(yù)期執(zhí)行時(shí)間，如式（2）所示，Cost(VMk)表示單位時(shí)間租賃成本。

其中，size(ti)表示任務(wù)ti的大小，以浮點(diǎn)計(jì)算的運(yùn)行次數(shù)度量；FPC(VMk)表示VMk的計(jì)算能力，以每秒進(jìn)行的浮點(diǎn)運(yùn)行次數(shù)度量。

2.3 計(jì)算平臺(tái)模型

本文使用與文獻(xiàn)[16]中相似的計(jì)算平臺(tái)模型，如圖2所示。用戶(hù)提交工作流及相關(guān)的服務(wù)質(zhì)量（quality of service，QoS）要求，例如截止時(shí)間期限和資源需求到工作流管理系統(tǒng)。工作流管理系統(tǒng)由三個(gè)主要模塊組成：資源調(diào)配模塊、工作流調(diào)度模塊和執(zhí)行管理器。資源調(diào)配模塊分析工作流結(jié)構(gòu)以預(yù)估所需資源量，動(dòng)態(tài)地向云服務(wù)商申請(qǐng)資源，并在租賃期結(jié)束時(shí)釋放資源。工作流程調(diào)度模塊與執(zhí)行管理器協(xié)調(diào)，完成工作流任務(wù)與資源之間的映射，并由資源管理器執(zhí)行。

Fig.2 Scheduling system model圖2 調(diào)度系統(tǒng)模型

工作流管理系統(tǒng)維護(hù)一個(gè)資源池Active_VMs信息列表，資源池信息列表中存儲(chǔ)每個(gè)申請(qǐng)到的資源實(shí)例的類(lèi)型、開(kāi)始時(shí)間和結(jié)束時(shí)間，如式（3）所示：

2.4 調(diào)度目標(biāo)

工作流調(diào)度目標(biāo)定義如下：

為工作流G規(guī)劃一個(gè)時(shí)間表S，在總執(zhí)行時(shí)間makespan不超過(guò)工作流截止期限D(zhuǎn)的條件下，最小化運(yùn)行工作流的執(zhí)行代價(jià)CostTotal，如式（4）所示：

3 CSACCP算法設(shè)計(jì)

本章首先介紹與算法有關(guān)的基本定義，然后設(shè)計(jì)CSACCP調(diào)度算法。算法首先調(diào)用Gen_CCPSET將工作流分解成CCP集合，然后通過(guò)CheapestMap算法實(shí)現(xiàn)每條CCP與最優(yōu)VM的匹配，以期在異構(gòu)云環(huán)境中在滿(mǎn)足用戶(hù)截止期限的約束下盡可能減少執(zhí)行代價(jià)。

3.1 基本定義

定義1MXT(ti)表示任務(wù)ti的最小執(zhí)行時(shí)間，定義為其在VMSET中所有資源類(lèi)型上最小執(zhí)行時(shí)間，其計(jì)算公式如下：

定義2EST(ti)表示任務(wù)ti的最早開(kāi)始時(shí)間，定義為其所有直接前驅(qū)被安排在執(zhí)行時(shí)間最小的VM上，并且所有所需的依賴(lài)數(shù)據(jù)都已傳遞到ti。其計(jì)算公式如下：

定義3EFT(ti)表示任務(wù)ti的最早完成時(shí)間，定義如下：

定義4MEXT_G表示工作流最早完成時(shí)間，即出口任務(wù)的最早完成時(shí)間，計(jì)算公式如下：

定義5XFT(ti)表示任務(wù)ti被調(diào)度到VM實(shí)例為vq上的預(yù)期完成時(shí)間，計(jì)算公式如下：

定義6XST(ti)表示任務(wù)ti被調(diào)度到VM實(shí)例為vq上的預(yù)期可開(kāi)始時(shí)間，只有在所有直接前驅(qū)執(zhí)行完畢且依賴(lài)數(shù)據(jù)傳輸?shù)絭q時(shí)才可開(kāi)始，計(jì)算公式如下：

定義7XIDT(vq)表示VM實(shí)例vq的預(yù)期空閑時(shí)間，其中tp為安排調(diào)度到vq上的最后一個(gè)任務(wù)，計(jì)算公式如下：

定義8XET(ti,VMk)表示從任務(wù)ti之后開(kāi)始的關(guān)鍵路徑在VM類(lèi)型為VMk上的執(zhí)行總時(shí)間，計(jì)算公式如下：

3.2 CSACCP算法

3.2.1 Gen_CCPSET算法生成CCP

通常關(guān)鍵路徑是指工作流任務(wù)圖中從入口節(jié)點(diǎn)到出口節(jié)點(diǎn)的最長(zhǎng)路徑。路徑的長(zhǎng)度為節(jié)點(diǎn)的執(zhí)行時(shí)間的平均值和沿該路徑的通信開(kāi)銷(xiāo)的總和。當(dāng)關(guān)鍵路徑上的任務(wù)首先被調(diào)度時(shí)，將產(chǎn)生有效的調(diào)度，但是關(guān)鍵路徑上的所有任務(wù)并非全都準(zhǔn)備就緒。所有直接前驅(qū)已經(jīng)為其調(diào)度處理的任務(wù)被稱(chēng)為準(zhǔn)備就緒任務(wù)。只包含準(zhǔn)備就緒任務(wù)的一組任務(wù)構(gòu)成了一條約束關(guān)鍵路徑CCP。每個(gè)CCP可以根據(jù)其任務(wù)的完成時(shí)間分配一個(gè)VM實(shí)例，將減少依賴(lài)數(shù)據(jù)傳輸時(shí)間。

HEFT（heterogeneous earliest-finish-time）[17]中將任務(wù)ti的向上權(quán)值rank定義為任務(wù)ti至texit的關(guān)鍵路徑長(zhǎng)度，并根據(jù)rank的大小決定任務(wù)執(zhí)行的優(yōu)先級(jí)。從出口任務(wù)開(kāi)始向上迭代計(jì)算每個(gè)任務(wù)的rank值，計(jì)算公式如式（13）所示：

考慮到出度高的任務(wù)若沒(méi)有及時(shí)執(zhí)行會(huì)影響整個(gè)工作流的執(zhí)行時(shí)間，CSACCP算法將向上權(quán)值進(jìn)行改進(jìn)，計(jì)算公式定義如下：

ranku與HEFT中的向上權(quán)值的差異在于聚合了任務(wù)直接后繼的通信時(shí)間，任務(wù)的出度越高優(yōu)先級(jí)越高。

算法Gen_CCPSET用于生成CCP集合。首先從降序排列的權(quán)值集合中選取最大值任務(wù)，查找到其入度為1且權(quán)值最大的子任務(wù)，繼續(xù)向下尋找直到不存在入度為1的子任務(wù)，生成一條CCP。從權(quán)值任務(wù)集合中去除CCP任務(wù)，并在邊集合中去除CCP相關(guān)有向邊，重復(fù)上一步直到集合為空。算法描述如下：

算法1Gen_CCPSET(G=(T,E))

圖1中簡(jiǎn)單工作流每個(gè)任務(wù)在三種VM類(lèi)型上的執(zhí)行時(shí)間及計(jì)算所得向上權(quán)值如表2所示。

Table 2 Upward rank of workflow表2 工作流向上權(quán)值

則經(jīng)過(guò)Gen_CCPSET之后生成的CCPSET為：

CCPSET={{t1,t2},{t3,t6,t9},{t5},{t4,t8},{t7,t10,t11}}

3.2.2 CheapestMap算法

CheapestMap算法接收CCPi及資源集合VMs作為輸入，并返回其最便宜的適用VM實(shí)例cheapestvm。

盡管最便宜的VM實(shí)例可能在其最晚完成時(shí)間之前完成任務(wù)，但它可能不是最佳選擇。這是因?yàn)槿蝿?wù)選擇最便宜的VM實(shí)例，而不考慮其對(duì)后繼任務(wù)的影響，可能會(huì)強(qiáng)制后繼任務(wù)在更快的VM上執(zhí)行，從而增加總體成本。因此，本文采用及時(shí)完成策略，將最便宜的適用VM實(shí)例定義為，在單個(gè)VM實(shí)例vk上，調(diào)度執(zhí)行此CCPi及從其尾任務(wù)ti之后開(kāi)始的關(guān)鍵路徑(最長(zhǎng)路徑)，在滿(mǎn)足截止期限D(zhuǎn)的條件下使得費(fèi)用增長(zhǎng)代價(jià)mincost最小。

由于每個(gè)任務(wù)必須等待其直接前驅(qū)的依賴(lài)數(shù)據(jù)，因此在調(diào)度任務(wù)之間可能會(huì)形成空閑時(shí)隙。如果空閑時(shí)隙過(guò)多，則會(huì)產(chǎn)生資源浪費(fèi)。因此為了提高資源的利用率同時(shí)進(jìn)一步降低執(zhí)行代價(jià)，算法首先考慮對(duì)空閑時(shí)隙的利用，采用首次適應(yīng)（first fit）的回填策略，在滿(mǎn)足截止期限的前提下，將CCPi插入最合適的空閑時(shí)隙，此時(shí)最小費(fèi)用增長(zhǎng)代價(jià)mincost為0。

對(duì)于資源集合VMs中每個(gè)虛擬機(jī)實(shí)例vk，算法由CCPi中每個(gè)任務(wù)在vk上的XFT(tj)和XST(tj)來(lái)計(jì)算CCPi的預(yù)期結(jié)束時(shí)間XFTCCP(CCPi)和預(yù)期開(kāi)始時(shí)間XSTCCP(CCPi)以及預(yù)期執(zhí)行時(shí)間XETCCP(CCPi)，計(jì)算公式如下：

若其滿(mǎn)足工作流截止期限D(zhuǎn)，則計(jì)算vk的費(fèi)用增長(zhǎng)代價(jià)，最終返回最便宜的虛擬機(jī)實(shí)例cheapestvm。算法描述如下：

算法2CheapestMap(CCPi,VMs)

3.2.3 CSACCP算法

為了適應(yīng)VM采集延遲launchdelay，算法將輸入預(yù)期的VM采集時(shí)間并相應(yīng)地作出供應(yīng)決策。由于VM終止延遲不會(huì)對(duì)工作流程的截止時(shí)間限制產(chǎn)生不利影響，因此本算法不考慮終止延遲。

算法首先評(píng)估MEXT_G并將其與用戶(hù)指定的截止期限D(zhuǎn)進(jìn)行比較，如果D大于MEXT_G，算法會(huì)繼續(xù)尋找適當(dāng)?shù)恼{(diào)度時(shí)間表，否則會(huì)提示用戶(hù)修改截止期限D(zhuǎn)。一旦確定了用戶(hù)指定的截止期限的可實(shí)現(xiàn)性，算法調(diào)用Gen_CCPSET生成約束關(guān)鍵路徑集合CCPSET，再對(duì)集合中每條約束關(guān)鍵路徑調(diào)用CheapestMap，選取最便宜的VM實(shí)例進(jìn)行匹配。

由于活動(dòng)資源池Active_VMs并不一定滿(mǎn)足所需，則將VMSET中每種虛擬機(jī)類(lèi)型新實(shí)例集合New_VMs與其合并形成備選資源集合VMs用于選取最便宜的虛擬機(jī)實(shí)例。若最終選取的實(shí)例屬于Active_VMs，將其調(diào)度到該實(shí)例上，并更新活動(dòng)資源池狀態(tài)；若屬于New_VMs，考慮虛擬機(jī)實(shí)例采集延遲，在XSTCP(CCPi)-launchdelay時(shí)刻新建虛擬機(jī)實(shí)例，將其調(diào)度到新建虛擬機(jī)實(shí)例上并更新資源池狀態(tài)信息。算法描述如下：

算法3CSACCP

3.3 時(shí)間復(fù)雜度分析

為計(jì)算時(shí)間復(fù)雜度，假設(shè)工作流G=(T,E)由n個(gè)任務(wù)組成，數(shù)據(jù)依賴(lài)邊的最大數(shù)量為n(n-1)/2，云服務(wù)商提供m種異構(gòu)的VM資源。CSACCP首先計(jì)算MEXT_G，判斷用戶(hù)定義截止期限的合理性，其時(shí)間復(fù)雜度為O(n2)。一旦確定用戶(hù)定義的截止期限是合理的，算法計(jì)算XET矩陣，為后續(xù)VM與CCP的匹配做準(zhǔn)備，其時(shí)間復(fù)雜度為O(n2m)。接下來(lái)算法通過(guò)調(diào)用Gen_CCPSET算法生成約束關(guān)鍵路徑集合，由于需要計(jì)算任務(wù)的向上權(quán)值，其時(shí)間復(fù)雜度為O(n2m)。最后CSACCP算法為CCPSET中每條CCP調(diào)用時(shí)間復(fù)雜度為O(n2m)的CheapestMap算法進(jìn)行虛擬機(jī)的匹配，考慮所有依賴(lài)性的時(shí)間復(fù)雜度為O(n3m)。此外由于云服務(wù)商提供的VM類(lèi)型的數(shù)量是恒定的并且小到足以忽略，因此CSACCP算法的時(shí)間復(fù)雜度為O(n2+n2m+n3m)=O(n3)。

4 實(shí)驗(yàn)結(jié)果及分析

4.1 實(shí)驗(yàn)設(shè)置

工作流采用Juve等人[1]研究的4種不同科學(xué)領(lǐng)域中的工作流結(jié)構(gòu)作為測(cè)試源，包括天文學(xué)領(lǐng)域的Montage、地震科學(xué)領(lǐng)域的Cybershake、重力物理學(xué)領(lǐng)域的LIGO和生物基因?qū)W領(lǐng)域的Epigenomics。每種工作流的大致結(jié)構(gòu)如圖3所示，這些工作流具有不同的組成和結(jié)構(gòu)特性。為了便于評(píng)估工作流算法，Bharathi等人[18]開(kāi)發(fā)了一個(gè)Pegasus工作流生成器來(lái)生成類(lèi)似于真實(shí)科學(xué)工作流的人工合成工作流，將諸如任務(wù)列表、任務(wù)之間的依賴(lài)關(guān)系、計(jì)算時(shí)間等信息存儲(chǔ)在XML格式的文件中。選取3種大小的工作流進(jìn)行了測(cè)試：小型（約100個(gè)任務(wù)）、中型（約300個(gè)任務(wù)）和大型（約1 000個(gè)任務(wù)）。由于實(shí)驗(yàn)結(jié)果相似，則結(jié)果圖表中只顯示大型工作流的實(shí)驗(yàn)結(jié)果。為了對(duì)所提出工作流調(diào)度算法進(jìn)行評(píng)估，本節(jié)利用仿真工具CloudSim[19]對(duì)由Pegasus生成的不同的工作流進(jìn)行仿真測(cè)試。

Fig.3 Four workflow structures used in experiment圖3 實(shí)驗(yàn)中所用4種工作流結(jié)構(gòu)

假設(shè)云服務(wù)提供商提供5種不同類(lèi)型的VM。虛擬機(jī)實(shí)例配置及處理能力基于Amazon EC2，參數(shù)如表1所示，不同虛擬機(jī)之間的平均帶寬設(shè)置為20 Mb/s，VM的采集延遲設(shè)置為97 s[20]。

每個(gè)工作流需要一個(gè)對(duì)應(yīng)的截止期限來(lái)評(píng)估所提出的算法，太短的截止期限會(huì)導(dǎo)致大部分工作流無(wú)法及時(shí)完成，如果截止日期非常寬松，則有足夠的時(shí)間以較低費(fèi)用完成工作流的執(zhí)行。為了設(shè)定截止期限，通過(guò)式（18）將截止時(shí)間分布于嚴(yán)格、適度與寬松之間。

截止期限因子α從1開(kāi)始考慮非常嚴(yán)格的截止期限（通常接近最快執(zhí)行時(shí)間），最高為10的非常寬松的期限，且步長(zhǎng)為1。

4.2 對(duì)比算法

為了驗(yàn)證CSACCP調(diào)度算法的有效性，選擇ICPCP[8]和RCT（robustness cost time）[21]作對(duì)比算法，在考慮所有依賴(lài)性的前提下，3種算法時(shí)間復(fù)雜度均為O(n3)。

IC-PCP算法是針對(duì)本問(wèn)題最常引用的算法之一。算法分為截止期限分布和規(guī)劃調(diào)度兩個(gè)階段，算法將用戶(hù)定義的截止期限分布在所有任務(wù)上，起始于將關(guān)鍵路徑上的關(guān)鍵任務(wù)在滿(mǎn)足截止期限的前提下，安排在最便宜的VM上執(zhí)行以消除通信代價(jià)，然后通過(guò)遞歸計(jì)算關(guān)鍵路徑上未被調(diào)度的后續(xù)任務(wù)的關(guān)鍵路徑，重復(fù)以上步驟直到所有任務(wù)調(diào)度完成。但是IC-PCP算法并未考慮到VM的采集延遲。

文獻(xiàn)[21]中提出了一種健壯性的工作流調(diào)度算法RCT，該算法考慮了云環(huán)境中資源采集延遲，依據(jù)成本和時(shí)間的權(quán)重設(shè)定目標(biāo)函數(shù)?；诓糠株P(guān)鍵路徑PCP（partial critical path），由健壯性類(lèi)型定義的一定量的松弛時(shí)間被添加到PCP執(zhí)行時(shí)間，每個(gè)PCP都有可行解集合FS（feasible solution），從FS中選擇適當(dāng)?shù)腣M實(shí)例。

4.3 實(shí)驗(yàn)結(jié)果分析

4.3.1 性能指標(biāo)

為了評(píng)估被測(cè)算法，選擇使用以下性能指標(biāo)：任務(wù)調(diào)度成功率SR（success rate）和標(biāo)準(zhǔn)化執(zhí)行成本NEC（normalized execute cost）。

每個(gè)算法的任務(wù)調(diào)度成功率SR，計(jì)算為成功達(dá)到預(yù)定期限的模擬運(yùn)行次數(shù)nk與模擬運(yùn)行總次數(shù)ntotal之間的比率，定義為：

因?yàn)榇嬖诙喾N不同性質(zhì)的科學(xué)工作流，所以需要一種標(biāo)準(zhǔn)化方法統(tǒng)一定義執(zhí)行成本。本文首先考慮了在最后期限內(nèi)失敗的成本，因此標(biāo)準(zhǔn)化執(zhí)行成本NEC定義為：

其中，CostTotal是滿(mǎn)足期限工作流的成本，已在式（4）中定義。MinCost為利用貪心策略將所有任務(wù)分配到最便宜的VM實(shí)例中的執(zhí)行成本。

4.3.2 算法執(zhí)行時(shí)間

表3具體介紹3種調(diào)度算法針對(duì)不同類(lèi)型的4種工作流的平均執(zhí)行時(shí)間?？紤]所有任務(wù)依賴(lài)性的前提下，時(shí)間復(fù)雜度均為O(n3)，結(jié)果表明3種算法的執(zhí)行時(shí)間相差不大。值得注意的是，在LIGO工作流中，CSACCP算法的執(zhí)行時(shí)間相對(duì)其他算法有所降低。這是受工作流結(jié)構(gòu)的影響，由于CSACCP算法執(zhí)行時(shí)間主要消耗在為CCP查找最便宜的VM上，CSACCP將LIGO工作流分解為多個(gè)結(jié)構(gòu)相似且執(zhí)行時(shí)間較短的約束關(guān)鍵路徑，使大量的CCP更容易滿(mǎn)足首次適應(yīng)的插入策略，減少了每條CCP在查找最便宜的VM時(shí)的計(jì)算時(shí)間。因此執(zhí)行時(shí)間有所降低，在大型工作流中較為明顯。

Table 3 Average running time of 3 scheduling algorithms表3 3種調(diào)度算法平均執(zhí)行時(shí)間 ms

4.3.3 調(diào)度成功率

評(píng)估每種工作流在不同截止期限因子的情況下任務(wù)調(diào)度成功率，結(jié)果如圖4所示。

Fig.4 Scheduling success rate圖4 調(diào)度成功率

圖4顯示了截止期限因子α從1增加到10，每種算法的調(diào)度成功率SR。較低的成功率表明算法無(wú)法找到符合截止期限的完成時(shí)間?？梢杂^察到IC-PCP在α為1和2時(shí)，在大多數(shù)情況下都無(wú)法找到滿(mǎn)足截止期限的調(diào)度策略。這是因?yàn)樗惴ㄊ紫缺闅v工作流，在忽略任務(wù)間通信開(kāi)銷(xiāo)的前提下，將整條關(guān)鍵路徑分配到一個(gè)最便宜的VM上。在后續(xù)的迭代選取剩余部分關(guān)鍵路徑并為其分配VM時(shí)，由于分配到不同VM上的任務(wù)間需要通信開(kāi)銷(xiāo)，這將導(dǎo)致在嚴(yán)格截止期限下，已分配的關(guān)鍵路徑無(wú)法在預(yù)期的時(shí)間內(nèi)完成，因此整體表現(xiàn)較差。

除Epigenomics之外，RCT和CSACCP在適度和寬松的截止期限內(nèi)沒(méi)有明顯差異，但是CSACCP在嚴(yán)格的截止期限內(nèi)比RCT有更好的表現(xiàn)。這是因?yàn)镽CT將成本及執(zhí)行時(shí)間設(shè)定目標(biāo)函數(shù)，成本的優(yōu)先級(jí)高于執(zhí)行時(shí)間，這將導(dǎo)致在嚴(yán)格的截止期限內(nèi)的表現(xiàn)不如CSACCP。尤其具有高并行度局部關(guān)鍵路徑的工作流Epigenomics，每條局部關(guān)鍵路徑都具有較長(zhǎng)的執(zhí)行時(shí)間。RCT優(yōu)先考慮對(duì)執(zhí)行成本的影響，在滿(mǎn)足最小費(fèi)用增長(zhǎng)的前提下，將多條局部關(guān)鍵路徑分配到一個(gè)VM上，忽視了對(duì)截止期限的影響，因此在嚴(yán)格的截止期限內(nèi)無(wú)法找到合適的調(diào)度策略。而CSACCP設(shè)定了任務(wù)的向上權(quán)值，優(yōu)先調(diào)度對(duì)工作流執(zhí)行影響較大的任務(wù)，并且降低任務(wù)間通信代價(jià)，每次在為CCP分配VM時(shí)，綜合考慮對(duì)費(fèi)用增長(zhǎng)代價(jià)和截止期限的影響，因此有較高的調(diào)度成功率，在嚴(yán)格的截止期限內(nèi)成功率均高于60%。

4.3.4 標(biāo)準(zhǔn)化執(zhí)行成本

圖5中的實(shí)驗(yàn)結(jié)果表明，工作流調(diào)度的成本通常隨著截止期限因子的增加而減少。由于NEC受調(diào)度成功率SR的影響，若無(wú)法找到合適的調(diào)度策略會(huì)引起數(shù)據(jù)值的缺失。在大多數(shù)情況下，CSACCP和RCT算法的性能優(yōu)于IC-PCP算法，在所有工作流的截止期限內(nèi)實(shí)現(xiàn)了最低的總執(zhí)行成本。如所有啟發(fā)式算法一樣，有些方面表現(xiàn)并不是最優(yōu)，但是這些方面都是少數(shù)。例如在Cybershake中，當(dāng)α＜3時(shí)，RCT表現(xiàn)出更少的執(zhí)行成本，但在此階段CSACCP比RCT有更高的調(diào)度成功率，且隨著截止期限因子的增加，CSACCP有著更好的表現(xiàn)。

Fig.5 Normalized schedule cost圖5 標(biāo)準(zhǔn)化執(zhí)行成本

在Epigenomics工作流中，IC-PCP雖然在α＞3的階段內(nèi)實(shí)現(xiàn)了更低的執(zhí)行成本，但是該算法在大多數(shù)的截止期限內(nèi)，無(wú)法滿(mǎn)足期限約束完成工作流的調(diào)度，尤其是在α足夠大的情況下調(diào)度成功率也只達(dá)到32%，而CSACCP則達(dá)到了100%。從圖5中可以看出，Montage和CyberShake在嚴(yán)格截止期限內(nèi)調(diào)度產(chǎn)生的執(zhí)行成本非常高，這是由工作流本身的結(jié)構(gòu)所決定的。在截止期限非常嚴(yán)格時(shí)，工作流前兩層結(jié)構(gòu)中的任務(wù)具有很高的并行度，任務(wù)需要并行執(zhí)行，因此所有算法都需要租用更多的虛擬機(jī)實(shí)例來(lái)完成前期任務(wù)，這將導(dǎo)致更高的執(zhí)行成本。

4.3.5 向上權(quán)值對(duì)算法性能的影響

CSACCP算法對(duì)HEFT中向上權(quán)值rank進(jìn)行了改進(jìn)，為了分析其對(duì)算法性能的影響，設(shè)定性能指標(biāo)執(zhí)行成本降低率CR（cost reduction rate），計(jì)算公式如下：

其中，NECH表示使用HEFT算法中rank的標(biāo)準(zhǔn)化執(zhí)行成本，NECC表示使用CSACCP算法中ranku的標(biāo)準(zhǔn)化執(zhí)行成本。

4種不同類(lèi)型的大型工作流按截止期限因子遞增實(shí)驗(yàn)結(jié)果如表4所示。

Table 4 Average execution cost reduction rate表4 平均執(zhí)行成本降低率 %

表4中結(jié)果表明，對(duì)于大型科學(xué)工作流，優(yōu)先調(diào)度出度高的任務(wù)，在滿(mǎn)足截止期限約束的前提下，可以有效降低工作流的執(zhí)行成本，降低率均在4.6%以上。尤其是對(duì)于Epigenomics和LIGO工作流，降低率可達(dá)到7.2%以上，這與兩種工作流的結(jié)構(gòu)特性有關(guān)。兩種工作流中都有大量的高出度任務(wù)，聚合任務(wù)的通信時(shí)間，提高任務(wù)的優(yōu)先級(jí)，進(jìn)一步縮短了工作流的執(zhí)行時(shí)間，提高調(diào)度成功率。因此，CSACCP算法對(duì)向上權(quán)值進(jìn)行改進(jìn)，并為工作流設(shè)定約束關(guān)鍵路徑可有效降低執(zhí)行成本。

總體來(lái)看，CSACCP在大多數(shù)情況下均可構(gòu)造更優(yōu)的調(diào)度方案，僅只在LIGO工作流的截止期限中RCT具有略高的調(diào)度成功率。在其他場(chǎng)景中，CSACCP均優(yōu)于IC-PCP和RCT。

5 結(jié)束語(yǔ)

為了解決異構(gòu)云環(huán)境下科學(xué)工作流截止期限約束的代價(jià)優(yōu)化調(diào)度問(wèn)題，提出一種基于約束關(guān)鍵路徑的代價(jià)優(yōu)化算法CSACCP。算法綜合考慮云環(huán)境下資源異構(gòu)性、數(shù)據(jù)通信開(kāi)銷(xiāo)和虛擬機(jī)采集延遲等因素。算法對(duì)任務(wù)設(shè)定向上權(quán)值，并根據(jù)權(quán)值將工作流進(jìn)行分解形成約束關(guān)鍵路徑CCP集合，整體分配CCP任務(wù)到最便宜實(shí)例，并且優(yōu)先考慮回填策略，進(jìn)一步提高資源利用率，降低執(zhí)行代價(jià)。實(shí)驗(yàn)結(jié)果表明，CSACCP算法不僅可以降低執(zhí)行代價(jià)，還可以得到更高的任務(wù)調(diào)度成功率。在未來(lái)工作中，將考慮可靠性、能耗等QoS約束。另外，進(jìn)一步結(jié)合云資源的付費(fèi)模式，如Amazon的預(yù)留模式和Spot模式，提高本文工作流調(diào)度模型的適用性。