• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    一種多重約束下確保成功率的云工作流調(diào)度方法

    2021-02-25 08:51:04張艮山劉旭寧
    計算機應(yīng)用與軟件 2021年2期
    關(guān)鍵詞:代價期限實例

    張艮山 劉旭寧

    (石家莊學(xué)院信息技術(shù)系 河北 石家莊 050035)

    0 引 言

    根據(jù)需求的不同,云計算可以動態(tài)地將資源提供至用戶任務(wù),實例租用方式是即付即用的,這與傳統(tǒng)計算模式不同,其更為靈活的特征給云計算作為處理科學(xué)工作流任務(wù)以及實施工作流調(diào)度帶來了極大的便利。大規(guī)??茖W(xué)工作流應(yīng)用的常規(guī)建模形式是圖論中的有向無環(huán)圖DAG,圖中頂點代表工作流中大量相互依賴或相互獨立的任務(wù)集。這些任務(wù)間或存在著直接關(guān)聯(lián)(執(zhí)行先后有嚴格次序),或無直接關(guān)聯(lián)可并行執(zhí)行。為了滿足云工作流的服務(wù)質(zhì)量,工作流調(diào)度需要在既定約束條件下搜索有效調(diào)度方案,將工作流結(jié)構(gòu)中的各個任務(wù)映射和調(diào)度至云資源實例上,并優(yōu)化目標函數(shù)。

    云計算按需提供和即付即用的資源使用方式使得目前的任務(wù)調(diào)度算法具有以下不足:1) 實例租用價格沒有利用更切合實際的商業(yè)云賬單模型;2) 實例利用時間相對固定;3) 在考慮多種約束條件的工作流調(diào)度問題時,所使用的啟發(fā)式算法或搜索算法時間復(fù)雜度較高,實施成本太大。針對1),本文在設(shè)計工作流調(diào)度算法中應(yīng)用Amazon EC2的實例賬單價格模型,同時在已經(jīng)支付的賬單周期中,前一任務(wù)的空閑賬單時間仍可被其他調(diào)度任務(wù)所利用,以此節(jié)省任務(wù)執(zhí)行代價。針對2),本文所考慮的場景中一旦實例空閑即可釋放,資源獲取更加靈活,資源利用也更加充分。針對3),本文不僅同步考慮預(yù)算和期限的雙重約束,還同步優(yōu)化執(zhí)行效率和代價,設(shè)計了更加高效復(fù)雜度更低的調(diào)度算法。

    1 相關(guān)工作

    多目標工作流調(diào)度可劃分為兩種情形:單工作流調(diào)度、多工作流調(diào)度。單工作流調(diào)度不適合云計算環(huán)境,與云計算的使用特征不符。單工作流調(diào)度目前主要體現(xiàn)在以下幾種類型:1) 在期限約束下優(yōu)化執(zhí)行代價。文獻[1]基于任務(wù)副本方法設(shè)計了期限約束下的工作流調(diào)度代價最優(yōu)化算法。文獻[2]設(shè)計了期限約束的動態(tài)代價啟發(fā)式調(diào)度算法,在公有云環(huán)境中進行了單個工作流的調(diào)度優(yōu)化。文獻[3-4]分別采用無啟發(fā)式和搜索式方法進行了工作流調(diào)度優(yōu)化。2) 在預(yù)算約束下優(yōu)化執(zhí)行時間。文獻[5-7]均設(shè)計了滿足預(yù)算約束的啟發(fā)式算法最小化執(zhí)行時間。文獻[8]設(shè)計的SABA算法是一種考慮安全與預(yù)算感知的工作流調(diào)度算法,在實現(xiàn)安全調(diào)度的同時提高了調(diào)度效率。以上兩種研究類型均屬于單約束單目標,此時調(diào)度方案的求解模型相對比較簡單,但其缺陷在于僅在單方面從效率或代價方面進行任務(wù)調(diào)度優(yōu)化,而云環(huán)境下的調(diào)度問題中這兩個因素是并存的,必須同步考慮。3) 同步實現(xiàn)執(zhí)行時間和執(zhí)行代價最優(yōu)。部分研究試圖在工作流調(diào)度中實現(xiàn)時間和代價的平衡。文獻[9]根據(jù)Critical-Path-First機制,通過工作流的擴展與壓縮來實現(xiàn)目標優(yōu)化。文獻[10]則利用帕累托的概念實現(xiàn)兩個指標優(yōu)化。同樣地,文獻[11]通過設(shè)計一種反映偏好的有效因子,實現(xiàn)了工作流執(zhí)行效率和代價優(yōu)化。但是以上工作多數(shù)為多約束下的單目標指標優(yōu)化或不做約束下同時優(yōu)化兩個指標。4) 預(yù)算與期限多約束。文獻[12]利用搜索機制對任務(wù)重分配,實現(xiàn)了一種雙約束調(diào)度算法。文獻[13]以自適應(yīng)混合啟發(fā)式算法對混合云環(huán)境中的工作流調(diào)度問題進行求解。文獻[14]提出了宏觀多工作流調(diào)度和微觀單工作流調(diào)度算法。文獻[15]提出多個工作流結(jié)構(gòu)下?lián)碛薪刂箷r間約束的吞吐量優(yōu)化調(diào)度算法,可以一定程度保證工作流的完成比例。文獻[16]則在資源分配過程中同樣采用了任務(wù)優(yōu)先級機制進行多工作流調(diào)度。以上研究方法的問題在于:(1) 考慮代價優(yōu)化時的資源定價多是固定定價,而非目前商業(yè)云所通用的云帳單模型,因此在進行目標優(yōu)化時得到的任務(wù)調(diào)度方案不一定能夠真正優(yōu)化調(diào)度代價;(2) 調(diào)度策略中所用的資源相對固定,無法反映云資源特有的彈性提供環(huán)境。

    2 系統(tǒng)模型

    工作流廣泛應(yīng)用于復(fù)雜分布式科學(xué)計算建模問題,有向無環(huán)圖DAG是工作流的最常用抽象工具。利用DAG抽象,一個工作流可定義為G=(T,E),T={t0,t1,…,tn}為頂點任務(wù)集,E={ei,j|ti,tj∈T}為邊集,即任務(wù)依賴。邊ei,j∈E(ti,tj∈T)代表兩個任務(wù)ti和tj之間的有向邊的偏序約束,此時,任務(wù)ti為tj的父親,任務(wù)tj為ti的子代任務(wù)。

    本文考慮的場景為IaaS云服務(wù)模型,IaaS通過提供包括不同CPU、內(nèi)存、存儲、網(wǎng)絡(luò)帶寬的實際類型來提供云服務(wù),服務(wù)按照不同定價使用。本文在算法設(shè)計中考慮了Amazon EC2的云資源實例,以最小賬單時間租用,若實際使用時間小于賬單時間,仍按賬單時間付費。令實例集合為P={p0,p1,…,pn}。

    pred(ti)={tj|(tj,ti)∈E}

    (1)

    任務(wù)ti的所有直接子任務(wù)可表示為:

    succ(ti)={tj|(ti,tj)∈E}

    (2)

    如圖1所示的工作流結(jié)構(gòu)中,任務(wù)t8的父親任務(wù)為t5、t6和t7,任務(wù)t1的子任務(wù)為t2、t3和t4。若一個任務(wù)沒有父親任務(wù)則為工作流的入口任務(wù),若一個任務(wù)沒有子任務(wù)則為工作流的出口任務(wù)。圖中,任務(wù)t1為工作流的入口任務(wù),任務(wù)t9為工作流的出口任務(wù)。換言之:

    圖1 工作流結(jié)構(gòu)

    pred(tentry)=?

    (3)

    succ(texit)=?

    (4)

    工作流的完成時間稱為調(diào)度長度或makespan,表示為Lms。由于出口texit是整個工作流執(zhí)行的最后一個任務(wù),可以認為該任務(wù)的最終完成時間即為工作流的調(diào)度長度。因此,其可以表述如下:

    Lms=FT(texit)

    (5)

    式中:FT(texit)為工作流最后一個任務(wù)texit的完成時間。

    工作流結(jié)構(gòu)是目前科學(xué)計算領(lǐng)域中最常用的任務(wù)結(jié)構(gòu)形式,它定義了任務(wù)的觸發(fā)順序和觸發(fā)條件,直接關(guān)聯(lián)的任務(wù)間必須按照先后次序進行部署,無直接關(guān)聯(lián)的任務(wù)則可以并行執(zhí)行。而作為最常用的工作流結(jié)構(gòu)表示模型,本文采用的有向無環(huán)圖DAG結(jié)構(gòu)則較為明確的定義的了工作流的結(jié)構(gòu)特征,其開始任務(wù)和結(jié)束任務(wù)均可以在DAG中明確表示。在設(shè)計工作流任務(wù)調(diào)度算法過程中,有向無環(huán)圖DAG的存儲方式和編程表達也比較有利于進行實驗環(huán)境的搭建和性能測試。

    令Ci,j表示任務(wù)ti和tj之間數(shù)據(jù)傳輸?shù)臅r間:

    (6)

    如果兩個任務(wù)ti和tj調(diào)度到相同的實例上(即pi=pj),則任務(wù)間的數(shù)據(jù)傳輸發(fā)生在本地機器上,通信代價基本為0。否則,通信時間為數(shù)據(jù)傳輸量data與數(shù)據(jù)中心平均帶寬β間的比值。

    ti的最早開始時間EST計算為:

    (7)

    式中:wtj表示任務(wù)tj在最快實例上的執(zhí)行時間。任務(wù)ti在實例pj上的執(zhí)行代價為:

    (8)

    式中:cj表示在單個時間周期里任務(wù)執(zhí)行時租用實例pj的代價;Nt表示租用實例的時間周期數(shù)量。工作流中所有任務(wù)的執(zhí)行總代價可表示為:

    (9)

    該代價模型應(yīng)用了Amazon EC2的實例賬單價格模型,同時在已經(jīng)支付的賬單周期中,前一任務(wù)的空閑賬單時間仍可被其他調(diào)度任務(wù)所利用(取式(8)中上限整數(shù)部分),以此節(jié)省任務(wù)的總體執(zhí)行代價。

    3 預(yù)算/期限感知調(diào)度算法

    為了同時滿足預(yù)算和期限約束,并在調(diào)度長度和調(diào)度代價上取得同步優(yōu)化的效果,BDAS算法將劃分為五個階段實行。1) 工作流結(jié)構(gòu)分層:將工作流劃分為若干不具有相關(guān)性的包任務(wù),稱之為層次level;2) 預(yù)算分配:利用某種策略將總體預(yù)算B分配至每個level中;3) 期限分配:將總體截止時間D分割并在不同level間進行分配,每個level得到層次期限;4) 任務(wù)選擇:根據(jù)就緒隊列中待執(zhí)行任務(wù)的優(yōu)先級,選擇調(diào)度任務(wù);5) 實例選擇:以時間和代價的均衡性作為參考,選擇最優(yōu)實例。

    3.1 工作流分層

    由于工作流結(jié)構(gòu)中的任務(wù)或者具有直接相關(guān)性,或者不具備直接關(guān)聯(lián)。那么,工作流分層的目的就是通過分離或?qū)θ蝿?wù)進行劃分,使得在同一個層次中的任務(wù)不具有相關(guān)性,以此盡可能最大化任務(wù)執(zhí)行的可并行程度,以此節(jié)省任務(wù)調(diào)度的時間,而具有直接關(guān)聯(lián)的任務(wù)則必須依據(jù)先后關(guān)系執(zhí)行。這樣,每個層次即可考慮為一個包括若干不相關(guān)任務(wù)的包任務(wù)。本文利用一種期限底部分層的方法將任務(wù)劃分至不同的層次中。將任務(wù)ti的層次描述為從ti至texit間路徑邊的最大值。那么,任務(wù)texit的層次將總為1。而其他任務(wù)則有:

    (10)

    所有任務(wù)根據(jù)其分層可劃分至任務(wù)分層集合TLS中,則:

    TLS(l)={ti|L(ti)=l}

    (11)

    式中:l表示層次,l∈{1,2,…,L(tentry)}。

    3.2 預(yù)算分配

    預(yù)算分配的思想是將全局預(yù)算B在不同層次中進行分配,在考慮分配至一個層次的可用子預(yù)算subB(l)的情況下將任務(wù)調(diào)度至實例上,其優(yōu)勢是可以將除去已經(jīng)使用后的全部預(yù)算按層次全部預(yù)留至下層任務(wù)。先將預(yù)算B全部分配給tentry,tentry調(diào)度完成后將剩余預(yù)算分配至下一層任務(wù)。將分配至一個層次上的子預(yù)算稱為層次預(yù)算,預(yù)算分配策略是將預(yù)算分配至最早的層次上,然后將未使用的剩余預(yù)算繼續(xù)分配至下一層次上,表示如下:

    (12)

    式中:TaskCostti由式(8)定義。將剩余預(yù)算定義為調(diào)度層次l中的所有任務(wù)后的剩余費用值。

    3.3 期限分配

    期限分配階段的目標是將初始定義的整體截止時間在劃分后的工作流不同層次上進行分配,即將整體的截止時間約束分割成不同層次間的子截止時間的約束。換言之,若在所分配的子期限內(nèi)層次中的所有任務(wù)可以保證完成,則整體截止時間同樣可以得到滿足。策略需要考慮每個層次的執(zhí)行時間以及層次中任務(wù)的數(shù)量,從而得到更低的代價。一旦任務(wù)被劃分入各自層次后,每個層次中的任務(wù)即可按比例從整體期限D(zhuǎn)中分配相應(yīng)子期限。令subD(l)表示層次期限,即分配至每個層次l的子期限。為了滿足整體期限,需要確保每個層次中的每個任務(wù)在其分配的子期限內(nèi)完成。每個層次l的初始估計期限計算為:

    (13)

    式中:ECT(ti)表示在所有資源間ti的最早完成時間,定義為:

    (14)

    式中:pred(ti)為ti的父任務(wù)集;wti為ti的最小執(zhí)行時間;l為父任務(wù)ti的層次。tentry沒有父親任務(wù),故其ECT=0。

    計算層次期限值后,需要根據(jù)截止時間的比例和每個層次中任務(wù)的數(shù)量將期限在所有任務(wù)間進行非均勻分配。引入一個比例單元∝deadline定義為:

    (15)

    式中:|subD(l)|表示層次l的期限長度;|TSL(l)|表示每個層次中的任務(wù)數(shù)量。

    定義期限因子DF為:

    (16)

    式中:subD(1)表示包括出口任務(wù)的層次。式(16)的分子部分表示剩余的期限,即總體截止時間與出口任務(wù)所在層次子期限之差值。

    將每個層次的期限的長度更新為期限因子DF的函數(shù):

    subD(l)=DF×|subD(l)|×|TSL(l)|+subD(l)

    (17)

    可見,擁有越長任務(wù)執(zhí)行時間和越多任務(wù)數(shù)量的層次,將獲得更多的截止時間分配。

    3.4 任務(wù)選擇

    由于處于相同層次中的任務(wù)間不具有相關(guān)性,所有這部分任務(wù)可以并行同步執(zhí)行。算法執(zhí)行過程中,待執(zhí)行的就緒任務(wù)將被置入就緒隊列中,而從就緒隊列中選擇執(zhí)行任務(wù)的依據(jù)是最早開始時間EST?;谌蝿?wù)的最早開始時間對任務(wù)進行調(diào)度次序選擇,可以確保盡可能短的工作流任務(wù)完成時間,從而提高任務(wù)調(diào)度效率。BDAS算法中,任務(wù)將按層次執(zhí)行,這表明只有在前一層次中的所有任務(wù)得到調(diào)度后,其下層次中的任務(wù)才可以開始執(zhí)行。

    對于某個任務(wù)是否為就緒任務(wù)的判斷依據(jù)為是否其所有父親任務(wù)已完成并已接收所有數(shù)據(jù),若滿足該條件,該任務(wù)即可進入就緒隊列。同一層中的任務(wù)由于任務(wù)間均沒有依賴性,故可以同步并行執(zhí)行。而選擇任務(wù)的依據(jù)是根據(jù)就緒隊列中的任務(wù)的優(yōu)先級來決定,此時優(yōu)先級的定義依據(jù)為最早開始時間EST。ti的最早開始時間EST計算為:

    因此,調(diào)度算法需要首先計算每個任務(wù)在實例上的EST,而最先開始執(zhí)行的任務(wù)也擁有最高的選擇優(yōu)先級,該任務(wù)也將被選為執(zhí)行的候選任務(wù)(該任務(wù)擁有最高的優(yōu)先級)。

    3.5 實例選擇

    處于以下狀況時需要進行實例選擇:1) 每個任務(wù)已被分配至一個層次中;2) 每個層次的預(yù)算和期限已被分配;3) 每個就緒任務(wù)的優(yōu)先級已被分配。實例選擇過程中,需要均衡任務(wù)的執(zhí)行時間和執(zhí)行代價。本文算法在進行實例選擇時將兼顧考慮到任務(wù)的執(zhí)行時間和執(zhí)行代價,通過設(shè)計的均衡函數(shù)選擇最佳的任務(wù)執(zhí)行實例,確保在截止時間和預(yù)算兩個不同的約束狀況下都能夠完成對任務(wù)的有效調(diào)度。

    對于當(dāng)前任務(wù)ti,其在實例pj上的最早執(zhí)行時間表示為ECT(ti|pj),該時間是任務(wù)在實例上完成的最早時間,由式(14)定義?;诖耍梢杂嬎惝?dāng)前任務(wù)的估計層次期限與任務(wù)在實例pj上的最早完成時間的差異:

    (18)

    式中:subDlti表示分配給包括任務(wù)ti所在層次的子期限;ECTmin表示在所有實例中得到的任務(wù)最小執(zhí)行時間。

    (19)

    式中:subBlti表示分配給包括任務(wù)ti所在層次的子預(yù)算;TaskCostmin表示ti在所有實例上執(zhí)行的最小代價(最優(yōu)代價)。

    為了尋找最優(yōu)實例,算法利用Cost/Time均衡因子CTTF實現(xiàn)執(zhí)行代價與執(zhí)行時間的均衡。CTTF值可以調(diào)整當(dāng)前任務(wù)在所有實例上的Time值和Cost值。為了代價最小化,目前已有的算法會將任務(wù)調(diào)度至最便宜可用的實例上(最慢實例),從而滿足其分配的子期限。然而,在這種策略下,任務(wù)執(zhí)行將花費更多時間,進而導(dǎo)致其子任務(wù)的EST出現(xiàn)延時。為了避免這種情況,在滿足期限的同時較貴的實例是更好的選擇,但又可能導(dǎo)致超過預(yù)算。因此,CTTF的作用即是在時間和代價間取得均衡。

    利用式(18)和式(19)計算任務(wù)的Time和Cost值時,會出現(xiàn)以下四種不同的情況:

    1)Cost>0,Time>0。此情況為最優(yōu)情形,其表明可以得到充足的預(yù)算進行工作流調(diào)度,同時,截止時間也相對寬松。當(dāng)分配預(yù)算和期限時,每個層次可以得到相對大的份額。因此,任務(wù)所在層次的子預(yù)算和子期限均較為充足,故Cost和Time值均為正值。

    2)Cost≤0,Time>0。層次l分配的預(yù)算已被支付(subBlti=0),因此,無法啟動新的實例,由于此時已無預(yù)算。另外一個可能的情形是當(dāng)前任務(wù)ti在實例pj上的代價高于剩余子預(yù)算(式(19)的分子)。若滿足以上兩種情況之一,則式(19)的值小于或等于0。

    3)Cost>0,Time≤0。此時為較緊密的期限情形(實例計算能力較低,無法滿足任務(wù)層次分割的子期限),導(dǎo)致式(18)中的ECT值大于或等于任務(wù)層次的子期限。若滿足此情況,式(18)的值變?yōu)樨撝祷?。

    4)Cost≤0,Time≤0。此時為較緊密的期限和預(yù)算,即當(dāng)前的子預(yù)算和子期限分別小于TaskCost和ECT。對于任務(wù)ti,式(19)和式(18)均小于或等于0。均衡函數(shù)定義為:

    (20)

    具有最大CTTF值的實例將被選擇為執(zhí)行任務(wù)ti的實例。

    4 實 驗

    4.1 實驗配置

    利用科學(xué)工作流調(diào)度仿真平臺WorkFloSim[13]進行仿真,所構(gòu)成的數(shù)據(jù)中心包括六種實例類型,實例類型的相關(guān)參數(shù)如表1所示。將不同實例類型間任務(wù)進行數(shù)據(jù)傳輸?shù)膸捲O(shè)為20 MB/s,實例的處理能力以MFLOPS計算度量,即資源每秒鐘可進行的百萬浮點操作數(shù)。此外,在實例租用價格方面,本文參考Amazon EC2的云資源實例定價機制,其定價利用以小時為單位的賬單機制。

    表1 實例類型以及能力參數(shù)

    選擇四種具有代表性且性能較被認可的云環(huán)境中的工作流調(diào)度算法與本文的BDAS算法進行性能比較,包括Hybrid算法[11]、MTCT算法[18]、CWFT算法[19]、SABA算法[8]。為了測試算法在處理不同類型的工作流結(jié)構(gòu)上的優(yōu)勢以體現(xiàn)算法的適應(yīng)性,選擇不同科學(xué)領(lǐng)域中的工作流結(jié)構(gòu)進行測試[20],包括CyberShake工作流、EPIGENOMIC工作流、LIGO工作流、Montage工作流。其中:CyberShake和LIGO兩種工作流的特點是存儲需求較大,前者是地震科學(xué)中仿真工作流應(yīng)用類型,后者為物理學(xué)中引力波的工作流應(yīng)用類型;Epigenomic工作流屬于計算密集型,是生物信息學(xué)中的工作流應(yīng)用類型;Montage工作流屬于輸入/輸出密集型,是天文學(xué)中的工作流應(yīng)用類型。此外,CyberShake工作流也是數(shù)據(jù)密集型。為了表現(xiàn)不同規(guī)模的工作流,仿真過程中分別配置200、400和800個工作流任務(wù)進行測試。

    為了測試算法對工作流執(zhí)行預(yù)算和期限的滿足程度,以一種靈活方式生成工作流的整體預(yù)算和期限值。具體方式如下:

    D=minD+αD×(maxD-minD)

    (21)

    B=minB+αB×(maxB-minB)

    (22)

    式中:minD為所有任務(wù)均調(diào)度至處理能力最差(代價相應(yīng)最小)的實例上執(zhí)行算法得到的調(diào)度長度;maxB為此時算法得到的對應(yīng)調(diào)度代價;maxD為所有任務(wù)均調(diào)度至處理能力最強(代價相應(yīng)最大)的實例上執(zhí)行算法得到的調(diào)度長度;minB為此時算法得到的對應(yīng)調(diào)度代價;αD和αB分別表示處于0至1之間的期限因子和預(yù)算因子。通過式(21)和式(22)中設(shè)置期限和預(yù)算約束,可以確保算法尋求調(diào)度解時滿足此時給出的約束條件。實驗中分別設(shè)置αD、αB的取值為{0.1,0.3,0.5}進行測試,以此觀察算法在不同的期限和預(yù)算緊密程度下算法的適應(yīng)性。而在理論上,兩個因子取值增加,成功調(diào)度工作流概率應(yīng)用是有所提高的。

    4.2 性能指標

    為了測試算法的性能,以下指標被選取進行性能比較,包括:調(diào)度成功率、時間比率和代價比率。

    調(diào)度成功率SR:該指標表示滿足預(yù)算和期限兩個約束條件時成功執(zhí)行的實驗次數(shù)與總仿真次數(shù)(nTot)的比值:

    (23)

    時間比率TR:該指標表示整體期限D(zhuǎn)與工作流調(diào)度的實際時間的比值:

    (24)

    代價比率CR:該指標表示整體預(yù)算B與工作流調(diào)度的實際代價間的比值:

    (25)

    顯然,TR和CR的取值若小于1,則說明算法得到的工作流調(diào)度沒有滿足期限和預(yù)算的約束條件。

    4.3 實驗分析

    圖2-圖5展示了五種算法得到的調(diào)度結(jié)果中的平均調(diào)度成功率SR。可以明顯地看出,本文算法相較其他四種對比算法在所有四種類型的工作流結(jié)構(gòu)中均得到了更高的調(diào)度成功率。換言之,BDAS算法得到的同時滿足預(yù)算和期限的調(diào)度結(jié)果次數(shù)是最多的。由于四種工作流的任務(wù)類型和結(jié)構(gòu)特征也有所差異,所有算法得到的平均調(diào)度成功率也不同。BDAS算法通過分層后的任務(wù)以及預(yù)算和期限的子分割機制,可以有效解決雙約束時的工作流調(diào)度問題,同時同步降低工作流的執(zhí)行時間和執(zhí)行代價。此外,還可以看到,若增加預(yù)算因子αB,工作流的各層次將擁有更多的可用預(yù)算,從而使得BDAS算法的平均調(diào)度成功率SR會進一步得到增加。對于αD=0.1所表達的較為緊密的截止時間,在四種工作流的多數(shù)實驗情形中,僅本文算法實現(xiàn)成功調(diào)度的可能性最大。

    圖2 CyberShake工作流

    圖3 Epigenomic工作流

    圖4 LIGO工作流

    圖5 Montage工作流

    圖6是改變預(yù)算因子得到的時間比率TR指標情況,圖7是改變期限因子得到的代價比率CR指標情況。如指標的定義可知,如果TR大于1,則表明算法得到的工作流調(diào)度解的執(zhí)行時間Makespan是小于整體期限約束的,反之亦然。同樣對于代價比率也有同樣的結(jié)果。圖6表明,本文算法得到的工作流調(diào)度方案的執(zhí)行時間對于不同程度的預(yù)算因子,總可以滿足期限約束。然而,根據(jù)圖7的CR指標,若降低αD,本文算法的代價將超過預(yù)算。圖2-圖5給出的SR指標的含義是在算法同時滿足期限約束和預(yù)算約束時成功調(diào)度的工作流的比例大小。圖7所示的CWFT算法雖然在降低執(zhí)行代價方面表現(xiàn)不錯,但在圖6所示的TR指標結(jié)構(gòu)中卻無法滿足期限約束,其SR指標性能是所有算法中表現(xiàn)最差的。多數(shù)情況下,SABA算法均無法得到成功調(diào)度,即無法同時滿足兩個條件的約束,原因在于SABA算法進行任務(wù)調(diào)度并未控制執(zhí)行代價,雖然該算法在總體執(zhí)行時間優(yōu)化上性能是最好的,但其代價性能是最差的。

    圖6 時間比率指標

    圖7 代價比率指標

    5 結(jié) 語

    為了求解在期限和預(yù)算雙重約束條件上的云工作流調(diào)度解,本文提出了一種新的調(diào)度算法。算法將工作流調(diào)度過程劃分為五個子階段,通過科學(xué)工作流結(jié)構(gòu)的仿真實驗,證明了算法在調(diào)度成功率和執(zhí)行時間與執(zhí)行代價的同步優(yōu)化上較同類型算法的性能更優(yōu)。

    猜你喜歡
    代價期限實例
    愛的代價
    海峽姐妹(2017年12期)2018-01-31 02:12:22
    代價
    婚姻期限
    幸福(2016年6期)2016-12-01 03:08:35
    成熟的代價
    企業(yè)會計檔案保管期限延長之我見
    我們的約定沒有期限
    完形填空Ⅱ
    完形填空Ⅰ
    勞動合同期限有幾種?
    代價
    99国产精品一区二区蜜桃av| 男人的好看免费观看在线视频| 日本欧美国产在线视频| 女的被弄到高潮叫床怎么办| 97超碰精品成人国产| 三级经典国产精品| 亚洲精品亚洲一区二区| 一本—道久久a久久精品蜜桃钙片 精品乱码久久久久久99久播 | 久久草成人影院| 亚洲人成网站在线观看播放| 美女脱内裤让男人舔精品视频 | 国产精品美女特级片免费视频播放器| 高清在线视频一区二区三区 | 不卡一级毛片| 在线免费观看的www视频| 91久久精品国产一区二区成人| 99热这里只有是精品在线观看| 亚洲第一电影网av| 伊人久久精品亚洲午夜| 村上凉子中文字幕在线| 国产精品爽爽va在线观看网站| 亚洲欧美日韩高清专用| 亚洲人成网站高清观看| 夜夜看夜夜爽夜夜摸| 国产高清激情床上av| 国产黄色小视频在线观看| 久久精品夜色国产| 天堂av国产一区二区熟女人妻| 久久久a久久爽久久v久久| 国产黄片美女视频| avwww免费| 国产精品女同一区二区软件| 亚洲成a人片在线一区二区| 欧美潮喷喷水| 国产免费一级a男人的天堂| 我的女老师完整版在线观看| 一个人观看的视频www高清免费观看| 国产亚洲欧美98| 中文字幕av在线有码专区| 悠悠久久av| 欧美精品国产亚洲| 男人和女人高潮做爰伦理| 午夜久久久久精精品| 国产精品.久久久| 久久久午夜欧美精品| 色哟哟·www| 国产淫片久久久久久久久| av在线老鸭窝| 亚洲中文字幕一区二区三区有码在线看| 男女做爰动态图高潮gif福利片| 超碰av人人做人人爽久久| 欧美xxxx性猛交bbbb| 欧美一级a爱片免费观看看| 99视频精品全部免费 在线| 2021天堂中文幕一二区在线观| 丰满乱子伦码专区| 人妻少妇偷人精品九色| 日韩一区二区三区影片| 久久精品国产亚洲av天美| 亚洲美女搞黄在线观看| 综合色av麻豆| 成人特级av手机在线观看| 欧美性感艳星| 狠狠狠狠99中文字幕| 国产视频首页在线观看| 亚洲婷婷狠狠爱综合网| 好男人视频免费观看在线| 午夜激情欧美在线| 中出人妻视频一区二区| 国产又黄又爽又无遮挡在线| 在线播放国产精品三级| 中文资源天堂在线| av天堂中文字幕网| 五月伊人婷婷丁香| 黄色视频,在线免费观看| 国产精华一区二区三区| 人妻系列 视频| 如何舔出高潮| 一级毛片aaaaaa免费看小| 国产老妇女一区| 国产一区二区三区av在线 | 熟女人妻精品中文字幕| 非洲黑人性xxxx精品又粗又长| 老师上课跳d突然被开到最大视频| 国产精品人妻久久久久久| 变态另类成人亚洲欧美熟女| 神马国产精品三级电影在线观看| 我的女老师完整版在线观看| 亚洲国产精品成人综合色| 特大巨黑吊av在线直播| 国产白丝娇喘喷水9色精品| 国产不卡一卡二| a级毛片a级免费在线| 国产亚洲精品久久久com| 97热精品久久久久久| www日本黄色视频网| 五月伊人婷婷丁香| 亚洲熟妇中文字幕五十中出| 两个人视频免费观看高清| 欧美zozozo另类| 少妇人妻精品综合一区二区 | 久久99热6这里只有精品| 如何舔出高潮| 日韩欧美在线乱码| 插逼视频在线观看| 亚洲成人精品中文字幕电影| 国产男人的电影天堂91| 最近视频中文字幕2019在线8| 性色avwww在线观看| 免费看日本二区| 亚洲最大成人中文| 99热网站在线观看| 亚洲国产精品成人久久小说 | 国产高清有码在线观看视频| 精品99又大又爽又粗少妇毛片| 亚洲色图av天堂| 美女国产视频在线观看| av女优亚洲男人天堂| 亚洲人成网站在线观看播放| 成人三级黄色视频| 成人无遮挡网站| 亚洲av成人精品一区久久| 日韩av不卡免费在线播放| 一级毛片久久久久久久久女| 一卡2卡三卡四卡精品乱码亚洲| 婷婷精品国产亚洲av| 国产精品人妻久久久影院| 乱系列少妇在线播放| 免费av观看视频| 精品人妻视频免费看| 欧美在线一区亚洲| 国产高清三级在线| 边亲边吃奶的免费视频| 免费大片18禁| 高清毛片免费看| 亚洲国产高清在线一区二区三| 国产精品人妻久久久影院| 可以在线观看的亚洲视频| 亚洲欧美成人精品一区二区| 一区福利在线观看| 男人和女人高潮做爰伦理| 国产精品人妻久久久久久| av国产免费在线观看| 亚洲高清免费不卡视频| 一级毛片aaaaaa免费看小| 国产av在哪里看| 91在线精品国自产拍蜜月| 亚洲av不卡在线观看| 在线a可以看的网站| 淫秽高清视频在线观看| 特大巨黑吊av在线直播| 三级国产精品欧美在线观看| 一级毛片久久久久久久久女| 九九爱精品视频在线观看| 身体一侧抽搐| 欧美日韩乱码在线| 久久人妻av系列| 亚洲av中文av极速乱| 亚洲欧美日韩卡通动漫| 精品久久久久久久久久免费视频| 只有这里有精品99| 97热精品久久久久久| 国产精品野战在线观看| 欧美bdsm另类| 国产成人aa在线观看| 特级一级黄色大片| 亚洲av免费在线观看| 久久精品夜色国产| 日本成人三级电影网站| a级毛片免费高清观看在线播放| 久久精品国产99精品国产亚洲性色| 网址你懂的国产日韩在线| 国产av不卡久久| 成年免费大片在线观看| 国产精品一区二区在线观看99 | 欧美精品一区二区大全| 岛国在线免费视频观看| 十八禁国产超污无遮挡网站| 亚洲欧美精品专区久久| 午夜老司机福利剧场| 亚洲丝袜综合中文字幕| 草草在线视频免费看| 乱系列少妇在线播放| 黄色配什么色好看| 国产黄a三级三级三级人| 女人被狂操c到高潮| 成人亚洲欧美一区二区av| 欧美性猛交黑人性爽| 亚洲av电影不卡..在线观看| 欧美精品一区二区大全| 18禁在线无遮挡免费观看视频| 免费一级毛片在线播放高清视频| 一区福利在线观看| 非洲黑人性xxxx精品又粗又长| 黄色日韩在线| 国产一区二区三区在线臀色熟女| 高清在线视频一区二区三区 | 中出人妻视频一区二区| 精品久久久久久久久av| 舔av片在线| av女优亚洲男人天堂| 黄色欧美视频在线观看| 国内少妇人妻偷人精品xxx网站| 亚洲内射少妇av| 久久久久九九精品影院| 成人鲁丝片一二三区免费| 国产av麻豆久久久久久久| av.在线天堂| 日韩欧美三级三区| 亚洲av免费高清在线观看| 老女人水多毛片| 全区人妻精品视频| 国产成年人精品一区二区| 久久久久九九精品影院| 黄色欧美视频在线观看| 一进一出抽搐gif免费好疼| 国产高清视频在线观看网站| 久久午夜亚洲精品久久| 亚洲在线自拍视频| 亚洲第一区二区三区不卡| 97超视频在线观看视频| 一级毛片久久久久久久久女| 日韩视频在线欧美| 国内揄拍国产精品人妻在线| 99热6这里只有精品| 欧美最新免费一区二区三区| 黄色视频,在线免费观看| 丝袜喷水一区| 村上凉子中文字幕在线| 亚洲成人久久爱视频| 国产白丝娇喘喷水9色精品| 九九热线精品视视频播放| 亚洲精品乱码久久久v下载方式| 国内少妇人妻偷人精品xxx网站| 夜夜爽天天搞| 国产伦理片在线播放av一区 | 能在线免费观看的黄片| 夜夜看夜夜爽夜夜摸| 一夜夜www| 亚洲在线观看片| 色噜噜av男人的天堂激情| 一进一出抽搐动态| 寂寞人妻少妇视频99o| 国产高清有码在线观看视频| 国产亚洲精品av在线| 亚洲av免费在线观看| 欧美成人免费av一区二区三区| 在线观看av片永久免费下载| 午夜免费激情av| 伦精品一区二区三区| 亚洲18禁久久av| 免费黄网站久久成人精品| 久久精品人妻少妇| 亚洲四区av| 黄色配什么色好看| 免费看美女性在线毛片视频| av专区在线播放| 九九久久精品国产亚洲av麻豆| 一级黄片播放器| 永久网站在线| 久久午夜福利片| 欧美日韩国产亚洲二区| 一本—道久久a久久精品蜜桃钙片 精品乱码久久久久久99久播 | 亚洲国产高清在线一区二区三| 国产高清有码在线观看视频| 麻豆成人av视频| 欧美精品国产亚洲| 国产高清三级在线| 久久精品国产清高在天天线| 性欧美人与动物交配| 日本免费一区二区三区高清不卡| 禁无遮挡网站| 免费av不卡在线播放| 日本免费a在线| 成人一区二区视频在线观看| 高清日韩中文字幕在线| 别揉我奶头 嗯啊视频| 久久99精品国语久久久| 亚洲成人久久爱视频| 夜夜看夜夜爽夜夜摸| 色播亚洲综合网| 亚洲国产日韩欧美精品在线观看| 国产精品免费一区二区三区在线| 亚洲美女搞黄在线观看| 26uuu在线亚洲综合色| 久久人人爽人人片av| 午夜福利在线观看免费完整高清在 | 99久久人妻综合| 人人妻人人澡欧美一区二区| 韩国av在线不卡| 欧美精品一区二区大全| 国产片特级美女逼逼视频| av福利片在线观看| 亚洲高清免费不卡视频| 亚洲色图av天堂| 国产黄色小视频在线观看| 国产成人午夜福利电影在线观看| 久久久精品94久久精品| 免费人成在线观看视频色| 色哟哟·www| 国产乱人偷精品视频| 国产 一区精品| 午夜激情欧美在线| 亚洲精品自拍成人| 人妻少妇偷人精品九色| 22中文网久久字幕| 日韩 亚洲 欧美在线| 你懂的网址亚洲精品在线观看 | 日本三级黄在线观看| 欧美日韩在线观看h| 欧美xxxx性猛交bbbb| 两个人的视频大全免费| 日韩高清综合在线| 黄色日韩在线| 国产成人福利小说| 亚洲av不卡在线观看| 成人高潮视频无遮挡免费网站| 免费观看精品视频网站| 国产亚洲5aaaaa淫片| 日韩av在线大香蕉| 免费一级毛片在线播放高清视频| 少妇丰满av| 在线免费十八禁| 人妻制服诱惑在线中文字幕| 亚洲av成人av| av女优亚洲男人天堂| 国产精品.久久久| 精品久久久久久久久av| 晚上一个人看的免费电影| 男的添女的下面高潮视频| 日日干狠狠操夜夜爽| 国产久久久一区二区三区| 不卡视频在线观看欧美| www.色视频.com| 能在线免费看毛片的网站| 特大巨黑吊av在线直播| 两个人的视频大全免费| 国产精品精品国产色婷婷| 精品久久久久久成人av| 久久精品91蜜桃| 久久久精品欧美日韩精品| 久久精品国产亚洲av天美| 日韩一本色道免费dvd| 免费搜索国产男女视频| 看片在线看免费视频| 成人国产麻豆网| 久久精品夜色国产| 欧美区成人在线视频| 国产精品爽爽va在线观看网站| 久久久久久久久久久丰满| 亚洲激情五月婷婷啪啪| 亚洲高清免费不卡视频| 久久久久久久久中文| 国产精品av视频在线免费观看| 最近2019中文字幕mv第一页| 白带黄色成豆腐渣| 国产高清视频在线观看网站| 亚洲在线自拍视频| 亚洲精品粉嫩美女一区| 国产欧美日韩精品一区二区| 国产一区二区亚洲精品在线观看| 欧美高清成人免费视频www| 国产一区二区激情短视频| 成人综合一区亚洲| 九色成人免费人妻av| 国产精品电影一区二区三区| 亚洲欧洲日产国产| 亚洲欧美成人精品一区二区| 天美传媒精品一区二区| 人妻制服诱惑在线中文字幕| 91久久精品国产一区二区成人| 99久久九九国产精品国产免费| 亚洲国产精品成人综合色| 看十八女毛片水多多多| 久久久久九九精品影院| 成人毛片60女人毛片免费| 一本一本综合久久| 男的添女的下面高潮视频| 可以在线观看的亚洲视频| 在线观看av片永久免费下载| 一级黄片播放器| 人人妻人人澡欧美一区二区| 久久精品国产99精品国产亚洲性色| 少妇人妻一区二区三区视频| 亚洲av电影不卡..在线观看| 免费av毛片视频| 精品久久久久久久久久久久久| 日日撸夜夜添| 啦啦啦韩国在线观看视频| 99在线人妻在线中文字幕| 免费观看精品视频网站| 国产一区二区三区在线臀色熟女| 亚洲在久久综合| 欧美zozozo另类| 人人妻人人澡人人爽人人夜夜 | 精品人妻偷拍中文字幕| 欧美xxxx性猛交bbbb| 波多野结衣高清无吗| 国产视频内射| 最新中文字幕久久久久| 国产在视频线在精品| 国产精品一及| 欧美最黄视频在线播放免费| 久久久精品欧美日韩精品| 欧美日韩国产亚洲二区| 卡戴珊不雅视频在线播放| 在线观看66精品国产| 日韩欧美精品免费久久| 国产成人精品久久久久久| 简卡轻食公司| 亚洲自拍偷在线| 亚洲av电影不卡..在线观看| 国产精品,欧美在线| av在线老鸭窝| 丰满乱子伦码专区| 国产探花极品一区二区| 一个人观看的视频www高清免费观看| 亚洲色图av天堂| 高清毛片免费观看视频网站| 两个人的视频大全免费| 亚洲成a人片在线一区二区| 91av网一区二区| 亚洲精品乱码久久久v下载方式| 我的女老师完整版在线观看| 国产av麻豆久久久久久久| 激情 狠狠 欧美| 伦精品一区二区三区| 欧美在线一区亚洲| 久久精品91蜜桃| 国产精品一区www在线观看| 蜜臀久久99精品久久宅男| 久久草成人影院| 男女做爰动态图高潮gif福利片| 最近最新中文字幕大全电影3| 天堂√8在线中文| 欧美高清成人免费视频www| 国产黄片视频在线免费观看| 国产精品一区二区在线观看99 | 一边亲一边摸免费视频| 97超碰精品成人国产| 精品免费久久久久久久清纯| .国产精品久久| 亚洲精品国产av成人精品| 国产精品综合久久久久久久免费| 久久久国产成人精品二区| 国产高清激情床上av| 国产高清三级在线| 久久久精品欧美日韩精品| 国内精品一区二区在线观看| 久久国内精品自在自线图片| 亚洲精品久久久久久婷婷小说 | av在线老鸭窝| 九九热线精品视视频播放| 免费看光身美女| 六月丁香七月| 麻豆久久精品国产亚洲av| 97人妻精品一区二区三区麻豆| 麻豆成人午夜福利视频| 22中文网久久字幕| 中出人妻视频一区二区| 久久中文看片网| 丝袜喷水一区| 国产一区二区三区在线臀色熟女| 九草在线视频观看| 国产精品嫩草影院av在线观看| 一进一出抽搐gif免费好疼| 国产69精品久久久久777片| 婷婷六月久久综合丁香| 免费观看精品视频网站| 免费观看人在逋| 一个人看的www免费观看视频| 亚洲最大成人手机在线| 波多野结衣高清无吗| 中文字幕制服av| 国产精品一及| 欧美高清成人免费视频www| 日日摸夜夜添夜夜爱| 中文亚洲av片在线观看爽| 1024手机看黄色片| 成人三级黄色视频| 国产高清三级在线| av在线天堂中文字幕| 色综合色国产| 国产成人影院久久av| 天堂中文最新版在线下载 | 日本黄大片高清| 国产精品一二三区在线看| 最新中文字幕久久久久| 99精品在免费线老司机午夜| 欧美日韩乱码在线| 欧美三级亚洲精品| 久久久久性生活片| 99热网站在线观看| kizo精华| 日韩欧美精品免费久久| 2022亚洲国产成人精品| 精品久久久久久成人av| 麻豆国产97在线/欧美| 日韩,欧美,国产一区二区三区 | 国产真实乱freesex| 免费看a级黄色片| 久久精品国产鲁丝片午夜精品| 菩萨蛮人人尽说江南好唐韦庄 | 中文字幕久久专区| 亚洲av一区综合| 全区人妻精品视频| 成年免费大片在线观看| 国产精品,欧美在线| 欧美高清成人免费视频www| 国产成人a∨麻豆精品| av在线蜜桃| 欧美丝袜亚洲另类| 日韩制服骚丝袜av| 国产伦精品一区二区三区四那| av在线播放精品| 欧美三级亚洲精品| 一级av片app| 爱豆传媒免费全集在线观看| 91精品一卡2卡3卡4卡| 毛片一级片免费看久久久久| 91午夜精品亚洲一区二区三区| 99热这里只有精品一区| 国产精品日韩av在线免费观看| 免费看光身美女| 亚洲四区av| 12—13女人毛片做爰片一| 麻豆国产av国片精品| 波多野结衣高清无吗| 国产精品久久久久久久久免| avwww免费| 十八禁国产超污无遮挡网站| 色哟哟·www| 国产成人一区二区在线| 成人午夜高清在线视频| 波野结衣二区三区在线| 一级毛片我不卡| 一进一出抽搐gif免费好疼| 日本撒尿小便嘘嘘汇集6| 91av网一区二区| 久久精品国产亚洲av天美| 深夜精品福利| 成人欧美大片| 我要看日韩黄色一级片| 伦理电影大哥的女人| 春色校园在线视频观看| 99久久久亚洲精品蜜臀av| 麻豆av噜噜一区二区三区| 看非洲黑人一级黄片| 乱码一卡2卡4卡精品| 国产一区二区亚洲精品在线观看| 亚洲性久久影院| 偷拍熟女少妇极品色| 人妻制服诱惑在线中文字幕| 亚洲五月天丁香| 日本-黄色视频高清免费观看| 成人性生交大片免费视频hd| 波多野结衣高清无吗| 欧美色欧美亚洲另类二区| 3wmmmm亚洲av在线观看| 99久久人妻综合| 少妇的逼好多水| 日韩成人伦理影院| av视频在线观看入口| 亚洲经典国产精华液单| 国产精华一区二区三区| 中文字幕av成人在线电影| 成年免费大片在线观看| eeuss影院久久| 尤物成人国产欧美一区二区三区| 五月玫瑰六月丁香| 亚洲无线观看免费| 亚洲精品影视一区二区三区av| 欧美日韩一区二区视频在线观看视频在线 | 少妇人妻一区二区三区视频| 一级av片app| 婷婷色综合大香蕉| 亚洲美女搞黄在线观看| 97超视频在线观看视频| 欧美最黄视频在线播放免费| 嫩草影院精品99| 久久久久久久久久成人| av卡一久久| 不卡一级毛片| 日韩一区二区三区影片| 久久精品国产自在天天线| 老女人水多毛片| 国国产精品蜜臀av免费| 搞女人的毛片| 97热精品久久久久久| 一进一出抽搐gif免费好疼| 麻豆av噜噜一区二区三区| 久久亚洲精品不卡| 日韩视频在线欧美| 偷拍熟女少妇极品色| 亚洲经典国产精华液单| 久久久久网色| 国产亚洲5aaaaa淫片| 欧洲精品卡2卡3卡4卡5卡区| 中文精品一卡2卡3卡4更新| 欧美日本视频| 男女视频在线观看网站免费| 久久精品91蜜桃| 久久精品国产亚洲网站| 男女下面进入的视频免费午夜| 男女那种视频在线观看| av免费在线看不卡| 日日摸夜夜添夜夜添av毛片| 一级毛片我不卡| 欧美日韩精品成人综合77777| 国产精品野战在线观看| 久久久久九九精品影院| 少妇被粗大猛烈的视频| 亚洲人成网站在线观看播放| 亚洲最大成人手机在线| 婷婷六月久久综合丁香|