陳彥橦，裴樹軍，苗 輝

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

1 引言

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

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

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

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

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

2 系統(tǒng)模型

2.1 科學工作流模型

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

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

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

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

2.2 云資源模型

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

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

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

Table 1 Types of VM表1 VM類型

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

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

2.3 計算平臺模型

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

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

工作流管理系統(tǒng)維護一個資源池Active_VMs信息列表，資源池信息列表中存儲每個申請到的資源實例的類型、開始時間和結(jié)束時間，如式（3）所示：

2.4 調(diào)度目標

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

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

3 CSACCP算法設(shè)計

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

3.1 基本定義

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

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

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

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

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

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

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

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

3.2 CSACCP算法

3.2.1 Gen_CCPSET算法生成CCP

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

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

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

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

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

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

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

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

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

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

3.2.2 CheapestMap算法

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

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

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

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

若其滿足工作流截止期限D(zhuǎn)，則計算vk的費用增長代價，最終返回最便宜的虛擬機實例cheapestvm。算法描述如下：

算法2CheapestMap(CCPi,VMs)

3.2.3 CSACCP算法

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

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

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

算法3CSACCP

3.3 時間復雜度分析

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

4 實驗結(jié)果及分析

4.1 實驗設(shè)置

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

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

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

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

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

4.2 對比算法

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

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

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

4.3 實驗結(jié)果分析

4.3.1 性能指標

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

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

因為存在多種不同性質(zhì)的科學工作流，所以需要一種標準化方法統(tǒng)一定義執(zhí)行成本。本文首先考慮了在最后期限內(nèi)失敗的成本，因此標準化執(zhí)行成本NEC定義為：

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

4.3.2 算法執(zhí)行時間

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

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

4.3.3 調(diào)度成功率

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

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

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

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

4.3.4 標準化執(zhí)行成本

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

Fig.5 Normalized schedule cost圖5 標準化執(zhí)行成本

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

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

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

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

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

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

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

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

5 結(jié)束語

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