林潮偉,林 兵,陳 星

1(福州大學(xué) 計算機(jī)與大數(shù)據(jù)學(xué)院,福州 350108)

2(福建省網(wǎng)絡(luò)計算與智能信息處理重點(diǎn)實驗室,福州 350108)

3(福建師范大學(xué) 物理與能源學(xué)院,福州 350117)

0 引 言

工作流應(yīng)用結(jié)構(gòu)復(fù)雜,通常包含數(shù)十個計算任務(wù),這些任務(wù)之間具有數(shù)據(jù)或控制流依賴關(guān)系.典型的工作流應(yīng)用[1]包括基于深度神經(jīng)網(wǎng)絡(luò)(Deep Neural Network,DNN)的應(yīng)用、物聯(lián)網(wǎng)(Internet of Things,IoT)應(yīng)用等.這些應(yīng)用計算復(fù)雜度高,對數(shù)據(jù)傳輸時延敏感,一般需要高性能的計算平臺來執(zhí)行完成.云計算提供強(qiáng)大的計算性能,但由于IoT設(shè)備和云端間的數(shù)據(jù)傳輸時延嚴(yán)重,導(dǎo)致IoT設(shè)備的時延敏感工作流應(yīng)用無法直接調(diào)度至云端執(zhí)行.移動邊緣計算[2,3](Mobile Edge Computing,MEC)作為一種不斷發(fā)展的計算范式,能夠提供一種更有效的方法,即在更接近數(shù)據(jù)創(chuàng)建點(diǎn)的位置處理數(shù)據(jù),使得延遲敏感的工作流應(yīng)用可以得到及時處理.考慮到云端虛擬機(jī)的強(qiáng)大存儲、計算能力和邊緣服務(wù)器的更靠近用戶端的優(yōu)勢,云邊協(xié)同計算模式作為一種融合云計算與邊緣計算差異化優(yōu)勢的新型計算范式[4,5],將數(shù)據(jù)密集型任務(wù)調(diào)度至邊緣,計算密集型任務(wù)調(diào)度至云端,云計算與邊緣計算有機(jī)結(jié)合,為移動用戶設(shè)備的各種請求提供不同的按需服務(wù).然而,由于云邊協(xié)同環(huán)境的資源異構(gòu)性高,各個計算節(jié)點(diǎn)的計算能力、帶寬、存儲等均存在差異,同時每個工作流應(yīng)用中任務(wù)之間存在復(fù)雜的數(shù)據(jù)依賴關(guān)系,如何在云邊協(xié)同環(huán)境下合理高效地調(diào)度多工作流應(yīng)用仍然存在重大挑戰(zhàn).

近年來,許多研究工作針對云計算或邊緣計算環(huán)境下的工作流應(yīng)用調(diào)度展開[6-8].工作流應(yīng)用調(diào)度是一個NP難問題[9],通?？紤]在單一平臺(云計算或邊緣計算)環(huán)境下,將工作流應(yīng)用的依賴任務(wù)分別調(diào)度到不同的計算節(jié)點(diǎn),滿足工作流應(yīng)用的服務(wù)質(zhì)量(Quality of Service,QoS)要求.云邊協(xié)同環(huán)境下的工作流應(yīng)用調(diào)度,不僅需要滿足工作流應(yīng)用的高計算復(fù)雜度需求,而且能夠有效降低數(shù)據(jù)傳輸時延[5].現(xiàn)有研究工作大多僅考慮單一工作流應(yīng)用的調(diào)度問題,而忽略了多個工作流應(yīng)用的調(diào)度,且在滿足工作流應(yīng)用截止時間約束前提下的調(diào)度代價優(yōu)化方面仍有較大的可挖掘空間.如何在滿足多個不同工作流應(yīng)用時延約束前提下,考慮不同工作流應(yīng)用的差異化生成時間,有效調(diào)度工作流應(yīng)用的依賴任務(wù)至合適的云邊計算節(jié)點(diǎn)上,降低多工作流應(yīng)用的總體執(zhí)行代價,仍是一項極具挑戰(zhàn)的研究.

目前關(guān)于工作流應(yīng)用調(diào)度的研究主要集中在確定性環(huán)境下,即計算節(jié)點(diǎn)的計算性能、傳輸帶寬等計算環(huán)境因素相對穩(wěn)定,不存在波動.然而,在云邊協(xié)同環(huán)境中,由于不同服務(wù)器之間的負(fù)載不同、帶寬波動、網(wǎng)絡(luò)擁塞等原因和計算機(jī)自身特性,工作流任務(wù)的執(zhí)行時間往往不能準(zhǔn)確地預(yù)測[10],并且即使是相同的數(shù)據(jù)在固定的服務(wù)器之間傳輸時,其傳輸時間也會時常變化.因此,在實際的調(diào)度過程中,服務(wù)器的性能和服務(wù)器之間的帶寬通常是波動的.調(diào)度環(huán)境的波動會對工作流應(yīng)用調(diào)度產(chǎn)生不確定的影響,這是不可忽視的,在建立工作流調(diào)度模型時,需要考慮到這種不確定性.目前的不確定性環(huán)境下的調(diào)度研究主要針對模糊作業(yè)車間調(diào)度[11]和實時嵌入式系統(tǒng)的任務(wù)調(diào)度[12]等,較少關(guān)注模糊云邊協(xié)同環(huán)境下工作流應(yīng)用調(diào)度的研究.

在前期工作中,云邊協(xié)同環(huán)境中基于DNN的應(yīng)用程序的代價驅(qū)動卸載[13],以及基于DNN的智能物聯(lián)網(wǎng)系統(tǒng)的節(jié)能卸載[14]得到解決,在工作流應(yīng)用調(diào)度方面已積累相關(guān)經(jīng)驗,并在云邊協(xié)同卸載方面也有一定工作基礎(chǔ).與本文工作相比,它們都處理某些云邊協(xié)同環(huán)境中的工作流調(diào)度,而不是模糊云邊協(xié)同環(huán)境.在本文研究中,進(jìn)一步解決了降低任務(wù)計算和數(shù)據(jù)傳輸導(dǎo)致的多個工作流應(yīng)用的執(zhí)行代價,且滿足相應(yīng)的截止時間約束,同時考慮調(diào)度策略對于實際調(diào)度中不同規(guī)模工作流應(yīng)用的決策實時性.三角模糊數(shù)[15]被用于來表示模糊環(huán)境下服務(wù)器的計算性能和傳輸帶寬.特別地,提出一種基于局部關(guān)鍵路徑的多工作流應(yīng)用調(diào)度策略(Workflow applications Scheduling strategy based on Partial Critical Path,WSPCP),該策略基于工作流應(yīng)用的數(shù)據(jù)依賴結(jié)構(gòu),采用預(yù)處理方法合并有向割邊;同時在調(diào)度過程中,將局部關(guān)鍵路徑的所有任務(wù)作為調(diào)度單元進(jìn)行統(tǒng)一調(diào)度,很大程度上避免了任務(wù)之間的數(shù)據(jù)傳輸,從而減少數(shù)據(jù)傳輸代價,從而實現(xiàn)在滿足每個工作流應(yīng)用截止時間約束的前提下,盡可能地降低模糊執(zhí)行代價.本文的主要貢獻(xiàn)包括以下3個部分:

1)考慮到實際調(diào)度過程中服務(wù)器的負(fù)載壓力、網(wǎng)絡(luò)擁塞等計算環(huán)境因素造成計算性能和傳輸帶寬的不穩(wěn)定性,采用三角模糊數(shù)來表示模糊云邊協(xié)同環(huán)境中服務(wù)器的計算性能和傳輸帶寬.

2)針對泊松到達(dá)的多工作流應(yīng)用,提出一種基于局部關(guān)鍵路徑的多工作流應(yīng)用調(diào)度策略(WSPCP),基于工作流應(yīng)用自身結(jié)構(gòu),提出合并有向割邊的預(yù)處理方法;同時,將局部關(guān)鍵路徑作為調(diào)度單元進(jìn)行統(tǒng)一調(diào)度,充分避免任務(wù)之間的數(shù)據(jù)傳輸,從而滿足多工作流應(yīng)用的時延約束,并降低其模糊執(zhí)行代價.

3)通過仿真實驗驗證,與其他基準(zhǔn)調(diào)度策略相比,在常用的工作流基準(zhǔn)數(shù)據(jù)集上,WSPCP可以在滿足多個工作流應(yīng)用的截止時間的前提下獲得更優(yōu)的可行調(diào)度方案,有效降低了模糊執(zhí)行代價.同時,對于不同規(guī)模的多工作流應(yīng)用,WSPCP能夠在平均秒級時間內(nèi)得到可行的調(diào)度方案,具有較好的決策實時性,能夠一定程度上應(yīng)對實際調(diào)度中多個應(yīng)用同時到達(dá)的極端情況.針對交通系統(tǒng)中的車輛識別應(yīng)用,考慮工作流應(yīng)用的任務(wù)規(guī)模、任務(wù)的計算復(fù)雜度、任務(wù)之間的數(shù)據(jù)傳輸量,進(jìn)一步分析WSPCP對于實際應(yīng)用的可行性.

本文的其余章節(jié)安排如下:第1節(jié)回顧相關(guān)工作,第2節(jié)給出多工作流應(yīng)用調(diào)度模型的定義,并對模糊云邊協(xié)同環(huán)境下的多工作流應(yīng)用調(diào)度進(jìn)行形式化表示;第3節(jié)詳細(xì)描述本文所提出的WSPCP策略;第4節(jié)設(shè)計仿真實驗環(huán)境,通過對比實驗,分析WSPCP的性能效果,以及對于實際應(yīng)用的可行性;最后,第5節(jié)概述本文的工作,并展望未來的研究方向.

1 相關(guān)工作

隨著移動邊緣計算的快速發(fā)展和云邊協(xié)同模式的廣泛應(yīng)用,IoT設(shè)備對于在邊緣節(jié)點(diǎn)運(yùn)行復(fù)雜應(yīng)用程序的需求越來越大[16].這些復(fù)雜的應(yīng)用程序可以表示為任務(wù)之間存在數(shù)據(jù)依賴關(guān)系的工作流應(yīng)用.在本節(jié)中,將簡要回顧并分析云計算和邊緣計算中的工作流應(yīng)用調(diào)度以及模糊不確定性環(huán)境中任務(wù)調(diào)度的研究.

近年來,云計算環(huán)境中的工作流應(yīng)用調(diào)度已經(jīng)展開了許多研究工作[17-19].Meng等人[8]提出一種基于粒子群優(yōu)化算法的安全感知調(diào)度方法,用于跨異構(gòu)云的實時資源分配.實驗結(jié)果表明,該策略能夠在調(diào)度和安全性能之間取得良好的平衡.Paknejad等人[19]提出一種增強(qiáng)的多目標(biāo)協(xié)同進(jìn)化算法,用于云環(huán)境中的工作流調(diào)度.實驗結(jié)果表明,該算法在代價、完工時間和能耗等性能指標(biāo)上均優(yōu)于同類算法.Qin等人[20]研究云工作流調(diào)度問題,在其執(zhí)行時間保持在截止時間內(nèi)的同時降低執(zhí)行代價.基于云工作流調(diào)度問題的特定知識,提出一種新型的基于知識的自適應(yīng)離散水波優(yōu)化算法(Knowledge-based Adaptive Discrete Water Wave Optimization,KADWWO).實驗結(jié)果表明,KADWWO算法的性能優(yōu)于最先進(jìn)的算法.然而,上述研究工作往往忽略了IoT設(shè)備向云端提交工作流應(yīng)用的數(shù)據(jù)傳輸,雖然云計算為調(diào)度工作流應(yīng)用提供了強(qiáng)大的計算性能,但由于IoT設(shè)備與云端之間的大量數(shù)據(jù)傳輸,可能會增加核心網(wǎng)絡(luò)的流量負(fù)載并導(dǎo)致高延遲.

邊緣計算技術(shù)能夠有效降低工作流調(diào)度和計算卸載的系統(tǒng)時延,帶來更好的用戶體驗[5,21,22].近年來,云邊協(xié)同環(huán)境中任務(wù)調(diào)度和卸載問題已引起廣泛研究.Xie等人[22]提出一種新的定向非局部收斂粒子群優(yōu)化算法(Directional and Non-local-Convergent PSO,DNCPSO),利用非線性慣性權(quán)重,通過定向搜索過程進(jìn)行變異和選擇操作,同時降低云邊環(huán)境下工作流的執(zhí)行成本和完成時間.仿真實驗表明,DNCPSO算法的性能優(yōu)于其他經(jīng)典算法和改進(jìn)算法.Hazra等人[23]提出一種節(jié)能任務(wù)卸載策略(Energy-Efficient Task Offloading,EETO),通過聯(lián)合卸載和調(diào)度光纖陀螺網(wǎng)絡(luò)中的實時IoT應(yīng)用,解決能源性能權(quán)衡問題.在不同QoS參數(shù)下的實驗結(jié)果表明,EETO策略比現(xiàn)有策略具有更好的性能.Zhao等人[24]提出一種邊緣環(huán)境下基于Q-learning算法的低負(fù)載分布式入侵檢測系統(tǒng)任務(wù)調(diào)度策略,該策略根據(jù)網(wǎng)絡(luò)變化動態(tài)調(diào)整調(diào)度策略,使得總體負(fù)載保持在較低水平,同時保持低負(fù)載和丟包率之間的平衡.實驗結(jié)果表明,與其他經(jīng)典方法相比,該策略具有更好的低負(fù)載性能,惡意特征檢測率等指標(biāo)沒有顯著降低.然而,現(xiàn)有的云邊協(xié)同環(huán)境下工作流應(yīng)用調(diào)度的研究很少考慮在滿足截止時間約束的同時優(yōu)化工作流應(yīng)用任務(wù)計算和數(shù)據(jù)傳輸造成的執(zhí)行代價.

在工作流應(yīng)用的實際調(diào)度過程中,服務(wù)器的性能和它們之間的帶寬通常會發(fā)生波動,這可能會對調(diào)度結(jié)果產(chǎn)生相當(dāng)大的影響.現(xiàn)有工作解決了模糊環(huán)境中的調(diào)度問題,但此類工作主要面向其他領(lǐng)域.Sun等人[11]考慮模糊柔性作業(yè)車間調(diào)度問題,將不確定的加工時間表示為三角模糊數(shù),提出一種有效的混合協(xié)同進(jìn)化算法來最小化模糊最大完工時間.通過五個基準(zhǔn)測試和三個處理時間模糊的大規(guī)模問題的測試,結(jié)果表明該算法的性能優(yōu)于現(xiàn)有方法,表現(xiàn)出較好的收斂能力.Muhuri等人[12]提出一種新的解決模糊不確定環(huán)境下實時嵌入式系統(tǒng)節(jié)能任務(wù)調(diào)度問題的方法,稱為“約束耦合節(jié)能遺傳算法”.實驗結(jié)果表明,該算法的性能優(yōu)于現(xiàn)有的同類算法.Wu等人[25]針對具有不確定參數(shù)的物聯(lián)網(wǎng)應(yīng)用提出一種模糊邏輯卸載策略,以優(yōu)化魯棒性和一致性指數(shù),其中三角模糊數(shù)與半梯形模糊數(shù)分別用于建模任務(wù)處理時間和數(shù)據(jù)傳輸時間.同時,設(shè)計一種多目標(biāo)分布估計算法,用于各種應(yīng)用中優(yōu)化模糊卸載策略.實驗結(jié)果表明,該算法在魯棒性和一致性指標(biāo)上均優(yōu)于經(jīng)典啟發(fā)式算法.盡管相關(guān)研究領(lǐng)域已經(jīng)取得了顯著進(jìn)展,但是在不確定性云邊協(xié)同環(huán)境中多工作流應(yīng)用的模糊調(diào)度仍然是一個極具價值的研究方向.

受到上述工作的啟發(fā),本文將提出一種啟發(fā)式調(diào)度策略,用于解決在模糊云邊協(xié)同環(huán)境中截止時間約束的多工作流應(yīng)用的代價驅(qū)動調(diào)度.

2 系統(tǒng)模型

云邊協(xié)同環(huán)境下的多工作流應(yīng)用調(diào)度框架如圖1所示,主要包括3個組成部分:帶截止時間約束的多工作流應(yīng)用、云邊協(xié)同環(huán)境以及啟發(fā)式調(diào)度器.

圖1 云邊協(xié)同環(huán)境下的多工作流應(yīng)用調(diào)度框架Fig.1 Framework model of workflow scheduling in edge-cloud environment

2.1 多工作流應(yīng)用模型

用戶在不同時間通過IoT設(shè)備向云邊協(xié)同環(huán)境提交工作流應(yīng)用,本文假設(shè)工作流應(yīng)用的到達(dá)滿足一個強(qiáng)度為λ的泊松過程[26],因此工作流應(yīng)用到達(dá)的時間間隔服從參數(shù)為λ的指數(shù)分布,其中,λ表示工作流的到達(dá)率.多工作流應(yīng)用W由多個工作流應(yīng)用{w1,w2,…,wn}組成,每個工作流應(yīng)用wi可以表示為一個三元組wi=(αi,di,Gi),αi表示第i個工作流應(yīng)用Wi到達(dá)的時間;di表示第i個工作流應(yīng)用的截止時間,在某個調(diào)度方案中,若所有工作流應(yīng)用都能在相應(yīng)的截止時間前被執(zhí)行完成,則稱該調(diào)度方案是可行的;Gi表示第i個工作流應(yīng)用的數(shù)據(jù)依賴結(jié)構(gòu).

此外,工作流應(yīng)用可能包含兩個及以上入任務(wù)或出任務(wù),可以通過為其添加虛擬入任務(wù)vin或虛擬出任務(wù)vout,將其轉(zhuǎn)化為僅含有一個入任務(wù)和出任務(wù)的工作流,具體操作為:設(shè)置虛擬入任務(wù)vin或虛擬出任務(wù)vout的計算量為0,并將原有的入任務(wù)和出任務(wù)分別與vin和vout通過虛擬數(shù)據(jù)邊連接,同時將上述虛擬數(shù)據(jù)邊的權(quán)值設(shè)置為0,即其傳輸數(shù)據(jù)量為0.值得注意的是,增加虛擬任務(wù)和虛擬數(shù)據(jù)邊不會對多工作流應(yīng)用調(diào)度的結(jié)果產(chǎn)生任何影響.

2.2 云邊協(xié)同環(huán)境

在多工作流應(yīng)用調(diào)度過程中,云邊協(xié)同環(huán)境主要向用戶提供計算服務(wù)和帶寬服務(wù),同時允許動態(tài)租賃.云邊協(xié)同環(huán)境S={Scloud,Sedge}由云和邊緣組成,具有不同的計算節(jié)點(diǎn),即云的虛擬機(jī)和邊緣的服務(wù)器.為了簡化表述,統(tǒng)一使用“服務(wù)器”表示云和邊緣中的計算節(jié)點(diǎn).云Scloud={s1,s2,…,su}包含的u個服務(wù)器,邊緣Sedge={su+1,su+2,…,su+v}包含v個服務(wù)器.服務(wù)器sk可以表示為:

(1)

根據(jù)服務(wù)器所屬平臺的類型,云邊協(xié)同環(huán)境中的服務(wù)器sr和st之間的帶寬βr,t可表示為:

(2)

2.3 多工作流應(yīng)用調(diào)度方案

在云邊協(xié)同環(huán)境中,啟發(fā)式調(diào)度器的目標(biāo)是給定一個調(diào)度方案,在每個工作流應(yīng)用都滿足截止時間約束的條件下,使得多工作流應(yīng)用的執(zhí)行代價最低.其根據(jù)調(diào)度方案中工作流應(yīng)用任務(wù)和服務(wù)器之間的映射關(guān)系,為工作流應(yīng)用任務(wù)分配相應(yīng)的服務(wù)器.

因此,多工作流應(yīng)用的調(diào)度方案可以被定義如下:

Γ=(W,S,M,ce,Tf)

(3)

(4)

(5)

2.3.1 確定性云邊協(xié)同環(huán)境下的調(diào)度

在本次研究中,主要關(guān)注服務(wù)器的任務(wù)計算能力和服務(wù)器之間的數(shù)據(jù)傳輸能力,并假定在執(zhí)行過程中有足夠的容量存儲傳輸數(shù)據(jù).因此,本文側(cè)重于考慮任務(wù)計算時間ttc和數(shù)據(jù)傳輸時間tdt,其計算方式具體如式(6)和式(7)所示:

(6)

(7)

(8)

(9)

(10)

(11)

其中,由于工作流調(diào)度過程中數(shù)據(jù)存儲、資源監(jiān)控等代價與上述代價相比可以忽略不計,從而只考慮任務(wù)計算代價和數(shù)據(jù)傳輸代價.

對于多工作流應(yīng)用的一個調(diào)度方案,其目標(biāo)是在所有工作流應(yīng)用的完成時間均滿足截止時間約束的同時,最小化其執(zhí)行代價.因此,多工作流應(yīng)用調(diào)度問題可形式化定義為:

(12)

2.3.2 不確定性云邊協(xié)同環(huán)境下的調(diào)度

(13)

圖2 三角模糊數(shù)的隸屬函數(shù)Fig.2 Membership function of triangular fuzzy number

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

基于上述形式化定義(12),模糊云邊協(xié)同環(huán)境下的多工作流應(yīng)用調(diào)度方案的優(yōu)化問題可形式化定義如式(22)所示:

(22)

(23)

(24)

(25)

(26)

綜上所述,基于上述形式化定義(22),模糊云邊協(xié)同環(huán)境下的多工作流應(yīng)用調(diào)度問題可轉(zhuǎn)化為式(27)所示:

(27)

3 基于局部關(guān)鍵路徑的多工作流應(yīng)用調(diào)度策略

本節(jié)首先介紹一些局部關(guān)鍵路徑相關(guān)的基本變量定義,然后給出基于局部關(guān)鍵路徑的多工作流應(yīng)用調(diào)度策略(Workflow applications Scheduling strategy based on Partial Critical Path,WSPCP)的具體描述,用于在滿足每個工作流應(yīng)用的截止時間約束的情況下,盡可能減少多工作流應(yīng)用的執(zhí)行代價.

3.1 基本定義

在本文中,將工作流應(yīng)用中已經(jīng)分配到某個服務(wù)器的任務(wù)稱為已調(diào)度任務(wù),反之,則是未調(diào)度任務(wù).在完成工作流應(yīng)用wi的調(diào)度前,任務(wù)vi,j的最早完成時間(Earliest Finish Time,EFT)可定義如下:

(28)

根據(jù)任務(wù)vi,j的最早完成時間,定義vi,j的最早開始時間(Earliest Start Time,EST)如下:

(29)

另外,由于虛擬入任務(wù)的計算量為0,其在任何服務(wù)器上的執(zhí)行時間均為0,因此虛擬入任務(wù)的最早完成時間和最早開始時間為工作流應(yīng)用的到達(dá)時間,即:

EST(vin)=EFT(vin)=αi

(30)

在WSPCP中,為了確保工作流應(yīng)用wi能夠在截止時間di之前完成,定義任務(wù)vi,j的最遲開始時間(Latest Start Time,LST)如式(31)所示,任務(wù)vi,j必須在LST(vi,j)前完成調(diào)度并開始執(zhí)行.

(31)

根據(jù)任務(wù)vi,j的最遲開始時間,定義vi,j的最遲完成時間(Latest Finish Time,LFT)如下:

(32)

同樣地,由于虛擬出任務(wù)的計算量為0,其在任何服務(wù)器上的執(zhí)行時間均為0,因此虛擬出任務(wù)的最早完成時間和最早開始時間為工作流應(yīng)用的到達(dá)時間,即:

LST(vout)=LFT(vout)=di

(33)

在WSPCP中,局部關(guān)鍵路徑(Partial Critical Path,PCP)是其最核心的思想之一.在傳統(tǒng)的調(diào)度策略中,往往以工作流應(yīng)用的單個任務(wù)作為調(diào)度單元進(jìn)行調(diào)度;與之不同的是,WSPCP將同一局部關(guān)鍵路徑上的所有任務(wù)作為調(diào)度單元進(jìn)行統(tǒng)一調(diào)度,從而有效壓縮依賴任務(wù)之間的數(shù)據(jù)傳輸量,減少數(shù)據(jù)傳輸代價.對于任務(wù)vi,j,其局部關(guān)鍵路徑定義如下:

(34)

其中,path(PCP(v),v)表示一條局部關(guān)鍵路徑,在任務(wù)v之前連接任務(wù)v的局部關(guān)鍵路徑PCP(v);CP(vi,j)表示vi,j的關(guān)鍵父任務(wù)(Critical Parent,CP),在任務(wù)vi,j的所有直接未調(diào)度父任務(wù)中,關(guān)鍵父任務(wù)到任務(wù)vi,j的數(shù)據(jù)最遲傳輸?shù)竭_(dá),具體定義如下:

(35)

根據(jù)上述定義可知,在PCP(vi,j)上的任何一個任務(wù),數(shù)據(jù)傳輸?shù)竭_(dá)其后繼任務(wù)的時間總是最遲的.

3.2 WSPCP

對于泊松到達(dá)的多工作流應(yīng)用,WSPCP實時監(jiān)測每個工作流應(yīng)用wi的到達(dá),進(jìn)行工作流應(yīng)用的任務(wù)調(diào)度,在滿足所有工作流應(yīng)用的截止時間約束的前提下,盡可能減少執(zhí)行代價.在調(diào)度過程中,WSPCP通過為局部關(guān)鍵路徑分配局部截止時間,即最遲完成時間,并對整個局部關(guān)鍵路徑進(jìn)行統(tǒng)一調(diào)度,而不會對單一任務(wù)進(jìn)行調(diào)度,這樣大大壓縮局部關(guān)鍵路徑上任務(wù)之間的數(shù)據(jù)傳輸量,減少數(shù)據(jù)執(zhí)行代價,具體過程如算法1所示.

算法1.WSPCP

procedureWorkflow_Applications_Scheduling(W,S)

Input:W,S

1.Initialization:M←null;

2.whileany ofWhas not arriveddo

3. ifwiarrivesthen

4. //每次生成1個新的線程,用于處理新到達(dá)的wi

5. #pragmaompparallelnum_threads(1){

6. //調(diào)用算法2,對wi進(jìn)行預(yù)處理

7. Workflow_Application_Preprocessing(wi);

9.forj=1toj=|Vi|do

10. 初始化任務(wù)vi,j為未調(diào)度任務(wù);

11. 計算EFT(vi,j),EST(vi,j),LST(vi,j),LFT(vi,j)

12.endfor

13.tstart(vin)=tend(vin)=αi,tstart(vout)=tend(vout)=di;

14. 標(biāo)記虛擬入任務(wù)vin和虛擬出任務(wù)vout為已調(diào)度任務(wù);

15. //調(diào)用算法3,基于局部關(guān)鍵路徑思想,調(diào)度所有任務(wù)

16. Scheduling_All_Parents(M,vout);

17. }

18.else

19. //Waiting for a workflow application arriving;

20.continue;

21.endif

22.endwhile

endprocedure

該算法描述了WSPCP的整體過程,對于泊松到達(dá)的工作流應(yīng)用wi,主要包括3個部分:1)調(diào)用算法2,對wi進(jìn)行預(yù)處理,基于wi的結(jié)構(gòu)特征,合并存在有向割邊的相鄰任務(wù),從而減少算法的時間復(fù)雜度;2)計算WSPCP過程中需要用到的相關(guān)變量,并標(biāo)記虛擬入任務(wù)vin和虛擬出任務(wù)vout為已調(diào)度任務(wù);3)調(diào)用算法3,以虛擬出任務(wù)vout作為輸入,基于關(guān)鍵父任務(wù)迭代機(jī)制,尋找?guī)Ь植拷刂谷掌诘木植筷P(guān)鍵路徑,并為局部關(guān)鍵路徑分配相應(yīng)的最適合服務(wù)器,并執(zhí)行所有任務(wù).

3.2.1 工作流應(yīng)用的預(yù)處理過程

由于多工作流應(yīng)用調(diào)度的任務(wù)規(guī)模較大,通過合并有向割邊可以有效減少任務(wù)規(guī)模,從而降低算法執(zhí)行時間.有向割邊的定義為:對于一條有向邊,其出節(jié)點(diǎn)的出度為1,且入節(jié)點(diǎn)的入度為1,則稱作有向割邊.如圖3所示的工作流應(yīng)用中,一共存在7條有向割邊,其中相同圖案的任務(wù)和有向邊(虛線箭頭)組成的結(jié)構(gòu)即為有向割邊.

圖3 工作流應(yīng)用中的有向割邊Fig.3 Directed cut-edge in workflow application

在工作流應(yīng)用的預(yù)處理過程中,算法2根據(jù)當(dāng)前工作流應(yīng)用wi的數(shù)據(jù)依賴結(jié)構(gòu)特征,將存在有向割邊的相鄰任務(wù)進(jìn)行合并,得到新任務(wù)的計算量為相鄰任務(wù)之和.對于存在大量有向割邊的工作流應(yīng)用,如Epigenomics和LIGO[28]等,預(yù)處理過程能夠大幅度減少其任務(wù)規(guī)模,降低WSPCP的執(zhí)行時間.

算法2.工作流應(yīng)用預(yù)處理

procedureWorkflow_Application_Preprocessing(wi)

Input:wi

1.記錄wi每個任務(wù)的入度和出度

2.do{

4.if出節(jié)點(diǎn)vi,p的出度為1and入節(jié)點(diǎn)vi,q的入度為1then

6. 合并出任務(wù)vi,p和入任務(wù)vi,q,并更新任務(wù)計算量;

7.endif

8.endfor

9.}whilewi存在有向割邊;

endprocedure

3.2.2 調(diào)度未調(diào)度任務(wù)

在算法1中,WSPCP調(diào)用算法3,以虛擬出任務(wù)vout作為輸入,調(diào)度工作流應(yīng)用wi的所有未調(diào)度任務(wù).

算法3.調(diào)度任務(wù)vi,j的所有未調(diào)度父任務(wù)

procedureScheduling_All_Parents(M,vi,j)

Input:M,vi,j

1.whilevi,j存在直接未調(diào)度父任務(wù)do

2.Initialization:v←vi,j,stack←null,PCP(vi,j)←null;

3.whilev存在直接未調(diào)度父任務(wù)then

4.stack.push(CP(v));

5.v=CP(v);

6.endwhile

7.whilestackis not emptydo

8.PCP(vi,j).append(stack.pop());

9.endwhile

10. //調(diào)用算法4,調(diào)度任務(wù)vi,j的局部關(guān)鍵路徑

11. Scheduling_Path(M,PCP(vi,j));

12.foreachvi,p∈PCP(vi,j)do

13. 更新vi,p所有未調(diào)度后繼任務(wù)的EFT和EST;

14. 更新vi,p所有未調(diào)度前驅(qū)任務(wù)的LST和LFT;

15. Scheduling_All_Parents(M,vi,p)

16.endfor

17.endwhile

endprocedure

3.2.3 調(diào)度局部關(guān)鍵路徑

在算法3中,Scheduling_All_Parents過程調(diào)用算法4,將任務(wù)vi,j的局部關(guān)鍵路徑統(tǒng)一調(diào)度到云邊協(xié)同環(huán)境中的最適合服務(wù)器上.

算法4.調(diào)度局部關(guān)鍵路徑

procedureScheduling_Path(M,PCP)

Input:M,PCP

1.foreachsk∈Sdo

2. 尋找執(zhí)行PCP的最適合服務(wù)器sk;

3.endfor

4.ifsk不存在then

5. 在滿足PCP的局部截止時間約束完成所有任務(wù)的條件下,租賃并初始化一個單位計算代價最小的服務(wù)器sk,即最適合服務(wù)器;

6.endif

7.將PCP調(diào)度到最適合服務(wù)器sk上;

8.foreachvi,p∈PCPdo

9.M=M∪(vi,p,sk);

11. 設(shè)置任務(wù)vi,p為已調(diào)度任務(wù);

12.endfor

endprocedure

該算法描述了局部關(guān)鍵路徑PCP的調(diào)度過程,利用貪心策略尋找執(zhí)行PCP的最適合服務(wù)器.對于局部關(guān)鍵路徑PCP,對應(yīng)的最合適服務(wù)器定義如下:云邊協(xié)同環(huán)境中的某個服務(wù)器sk,能夠在PCP對應(yīng)的局部截止時間內(nèi)完成PCP上的所有任務(wù),且同時滿足以下3個條件:

(36)

其中,t1和t2分別表示在執(zhí)行PCP前后服務(wù)器sk的實際執(zhí)行時間,「t1?表示根據(jù)要價單元時間uk的向上整合時間.特別地,若服務(wù)器sk剛啟動,則t1=0.

2)如果存在多個最低執(zhí)行增長代價相等的服務(wù)器,則選擇實際執(zhí)行時間最長的服務(wù)器sk.

(37)

如果不存在可用的最適合服務(wù)器,則租賃并初始化一個單位計算代價最小的服務(wù)器sk,同時能夠在滿足PCP局部截止時間約束的條件下完成所有任務(wù).最后,將PCP調(diào)度到最適合服務(wù)器sk上,同時將所有任務(wù)設(shè)置為已調(diào)度任務(wù).

4 仿真實驗與分析

4.1 實驗設(shè)置

所有實驗都在16 GB RAM和3.00GHz Intel i5-9500F CPU的Win 10系統(tǒng)下運(yùn)行,WSPCP和所有對比調(diào)度策略均在Python 3.8環(huán)境下實現(xiàn).

用戶每次提交的工作流應(yīng)用均來自于Bharathi等[28]所提出的5種小型工作流應(yīng)用模型:地震科學(xué)CyberShake、生物基因?qū)WEpigenomics、重力物理學(xué)LIGO、天文學(xué)Montage和生物信息學(xué)SIPHT.每種工作流應(yīng)用含有約30個任務(wù),具有不同的依賴結(jié)構(gòu),其計算需求和數(shù)據(jù)集大小等相關(guān)信息均被存儲在xml文件中.在本次實驗中,設(shè)置多工作流應(yīng)用的規(guī)模為20個.假定工作流應(yīng)用的到達(dá)是一個強(qiáng)度為λ的泊松過程,工作流應(yīng)用到達(dá)的時間間隔服從參數(shù)為λ的指數(shù)分布,用戶平均每隔2.5s向云邊協(xié)同環(huán)境提交工作流應(yīng)用,則工作流的平均間隔時間為1/λ=2.5,即λ取0.4.因此,對于工作流應(yīng)用wi,定義其到達(dá)時間αi如式(38)所示:

(38)

其中,randexp(λ)用于產(chǎn)生參數(shù)為λ的指數(shù)分布隨機(jī)數(shù).

另外,每個工作流應(yīng)用都有對應(yīng)的截止時間約束,并以此來測試調(diào)度策略的有效性.對于工作流應(yīng)用wi,定義其截止時間di如式(39)所示:

di=αi+bl*|W|*HEFT(wi),bl={2.0,2.5,3.0,3.5}

(39)

其中,HEFT(wi)表示用HEFT算法[29]調(diào)度工作流應(yīng)用wi所需的執(zhí)行時間.參數(shù)bl表示截止時間因子.

在模糊云邊協(xié)同環(huán)境中,假定初始時刻存在5個云服務(wù)器(s1,s2,…,s5)和5個邊緣服務(wù)器(s6,s7,…,s10).每個服務(wù)器具有特定的任務(wù)計算能力和單位計算代價.假定云服務(wù)器s1,s2,…,s5的計算能力分別為2.5,3.5,5.0,7.5,10.0GHz,邊緣服務(wù)器s6,s7,…,s10的計算能力約2.5GHz,分別為2.5,2.6,2.2,2.3,2.7GHz;假定計算能力最強(qiáng)的云服務(wù)器s5的單位計算代價為12.5 $/h或(5/24 $/min),以云服務(wù)器s5的單位時間計算代價為基準(zhǔn),其余服務(wù)器的單位計算代價近似與其計算能力成正比.在工作流應(yīng)用調(diào)度中,可以根據(jù)需要動態(tài)租賃并初始化具有上述性能的服務(wù)器.

目前主流的商業(yè)云服務(wù),如Amazon EC2,通常按1分鐘或1小時為要價單元時間μi進(jìn)行付費(fèi).在本次實驗中,用戶提交的工作流應(yīng)用均為小型規(guī)模,選擇以1分鐘為單位進(jìn)行付費(fèi).

兩個服務(wù)器si和sj之間的帶寬和單位數(shù)據(jù)傳輸代價,根據(jù)二者所屬環(huán)境fi和fj的不同,如表1進(jìn)行設(shè)置.

表1 不同服務(wù)器si和sj之間的帶寬Table 1 Bandwidths between different servers

第2.3.2節(jié)詳細(xì)闡述了如何將計算性能pk和帶寬br,t模糊化為對應(yīng)的三角模糊數(shù),參數(shù)δ1和δ2分別取為0.75和1.2.為了比較實驗結(jié)果的好壞,第2.3.2節(jié)同時給出了模糊云邊協(xié)同環(huán)境下的多工作流應(yīng)用模糊執(zhí)行代價和模糊完成時間的去模糊化方法,參數(shù)?取為1;另外,基于時效性的考慮,設(shè)置參數(shù)η的值為0.95.

4.2 基準(zhǔn)策略

WSPCP是一種啟發(fā)式調(diào)度策略,為了驗證該策略對于降低多工作流應(yīng)用模糊執(zhí)行代價的有效性,在本次實驗中,將以下3個調(diào)度策略作為基準(zhǔn)策略,用于比較WSPCP和其他基準(zhǔn)策略的調(diào)度性能.

1)WSGS(Workflow applications Scheduling based on Greedy Strategy):該策略采用與WSPCP相同的預(yù)處理方法,在調(diào)度過程中,對于泊松到達(dá)的每個工作流應(yīng)用,采用最早完成時間優(yōu)先[29]的策略為每個任務(wù)選擇執(zhí)行的服務(wù)器.當(dāng)現(xiàn)有服務(wù)器無法滿足截止時間約束時,允許在云邊協(xié)同環(huán)境中租賃并初始化新的服務(wù)器.

2)WSPG(Workflow applications Scheduling strategy based on Particle swarm optimization employing Genetic operators):該策略采用服務(wù)器和優(yōu)先級嵌套的編碼策略,服務(wù)器編碼采用離散值表示執(zhí)行任務(wù)的服務(wù)器編號,優(yōu)先級編碼采用連續(xù)值表示同一時刻服務(wù)器中待執(zhí)行任務(wù)的優(yōu)先級大小;采用PSO-GA更新策略[14]對粒子編碼進(jìn)行更新以尋找較優(yōu)的調(diào)度方案,參數(shù)w,c1,c2根據(jù)文獻(xiàn)[14]進(jìn)行設(shè)置,種群規(guī)模和迭代次數(shù)分別設(shè)置為100和1000.

3)WSRS(Workflow applications Scheduling based on Random Searching):該策略采用與WSPG相同的優(yōu)先級和服務(wù)器嵌套的編碼策略,使用隨機(jī)搜索策略生成新的種群,在相應(yīng)的定義域內(nèi)隨機(jī)生成每個粒子的優(yōu)先級和服務(wù)器編碼,并將粒子映射到對應(yīng)的調(diào)度方案,記錄隨機(jī)搜索過程中的最優(yōu)解,每次迭代之間互不影響,最終輸出種群的最優(yōu)解,即最優(yōu)調(diào)度方案,其中,種群規(guī)模和迭代次數(shù)分別設(shè)置為100和1000.

4.3 實驗結(jié)果與分析

4.3.1 不同截止時間約束下的調(diào)度性能

為了比較WSPCP和其他基準(zhǔn)策略在模糊云邊協(xié)同環(huán)境中多工作流應(yīng)用的調(diào)度性能,在不同的截止時間約束下,對多工作流應(yīng)用調(diào)度進(jìn)行4組仿真實驗,包括嚴(yán)格(bl=2.0)、 中等(bl=2.5)、微小(bl=3.0)和寬松(bl=3.5)4種截止時間約束,并分析WSPCP在降低多工作流應(yīng)用模糊執(zhí)行代價方面的優(yōu)越性.對于每種截止時間約束,記錄10次獨(dú)立重復(fù)實驗中的最優(yōu)和平均模糊執(zhí)行代價及其適應(yīng)度(單位:10-3$).表2展示了在不同調(diào)度策略下多工作流應(yīng)用的最優(yōu)模糊執(zhí)行代價,其中,最優(yōu)解用粗體表示,不可行解用符號“*”標(biāo)記.

表2 不同調(diào)度策略下多工作流應(yīng)用的最優(yōu)模糊執(zhí)行代價Table 2 Optimal fuzzy execution cost of workflow applications based on different scheduling strategies

從優(yōu)化目標(biāo)來看,本文所提出的調(diào)度策略WSPCP在4種截止時間約束下都得到了最優(yōu)的調(diào)度方案,即多工作流應(yīng)用的模糊執(zhí)行代價最小,而WSPG的性能次之.WSPCP采用預(yù)處理方法合并有向割邊,降低了問題的任務(wù)規(guī)模;同時將局部關(guān)鍵路徑的所有任務(wù)作為調(diào)度單元進(jìn)行調(diào)度,很大程度上避免了任務(wù)之間的數(shù)據(jù)傳輸,從而減少數(shù)據(jù)傳輸代價,最終得到最優(yōu)的調(diào)度方案.而WSPG作為一個全局搜索策略,由于受到解空間規(guī)模的限制,難以在有限的迭代次數(shù)內(nèi)得到更優(yōu)的調(diào)度方案,但仍然優(yōu)于傳統(tǒng)的貪心策略,即WSGS.值得注意的是,WSRS在指數(shù)級的解空間中進(jìn)行無差別的隨機(jī)搜索,僅在寬松的截止時間約束下可以得到可行的調(diào)度方案,對于多工作流調(diào)度這一約束優(yōu)化問題而言,WSRS是無法接受的.

從截止時間約束來看,WSPCP和WSGS在任何情況下都能得到滿足約束的可行調(diào)度方案.在嚴(yán)格(bl=2.0)的截止時間約束下,WSPG和WSRS是無效的,無法得到可行的調(diào)度方案.隨著截止時間約束的放寬(bl≥2.5),多工作流應(yīng)用的模糊執(zhí)行代價呈降低趨勢,且WSPG能夠得到可行的調(diào)度方案.然而,僅在寬松(bl=3.5)的截止時間約束下,WSRS能夠得到可行解.這是因為多工作流應(yīng)用調(diào)度是一個組合優(yōu)化問題,具有大量的局部極值點(diǎn),是不連續(xù)的、高度非線性的NP難問題.在嚴(yán)格的截止時間約束下,作為全局搜索策略,對于指數(shù)級規(guī)模的解空間,WSPG在有限的迭代次數(shù)內(nèi)無法得到更優(yōu)的調(diào)度方案,即使它能夠?qū)饪臻g進(jìn)行有方向、有目標(biāo)地探索;而WSRS所采用的隨機(jī)搜索策略效率較低,在解空間內(nèi)進(jìn)行無差別地探索,難以搜索到高質(zhì)量的、可行的調(diào)度方案.

此外,對于每種截止時間約束下的10次獨(dú)立重復(fù)實驗,圖4展示了在不同調(diào)度策略下多工作流應(yīng)用的平均模糊執(zhí)行代價.從圖4中可以看出,在4種截止時間約束下,WSPCP所產(chǎn)生的調(diào)度方案下的多工作流應(yīng)用的平均模糊執(zhí)行代價均優(yōu)于其他基準(zhǔn)策略.特別地,在嚴(yán)格(bl=2.0)的截止時間約束下,相較于其他基準(zhǔn)策略,WSPCP對于多工作流應(yīng)用平均模糊執(zhí)行代價的降低約為7.5%～70.0%.由此可見,WCPCP在不同截至?xí)r間約束下的魯棒性更強(qiáng).

圖4 不同調(diào)度策略下多工作流應(yīng)用的平均模糊執(zhí)行代價Fig.4 Average fuzzy execution cost of workflow applications based on different scheduling strategies

綜上所述,相較于其他基準(zhǔn)策略,WSPCP將局部關(guān)鍵路徑上所有任務(wù)作為調(diào)度單元進(jìn)行統(tǒng)一調(diào)度,很大程度上避免了任務(wù)之間的數(shù)據(jù)傳輸,減少數(shù)據(jù)傳輸?shù)臅r間和代價,從而總是能夠得到更優(yōu)的可行調(diào)度方案.特別地,在嚴(yán)格的截止時間約束下,WSPCP仍然可以得到滿足截止時間約束的可行調(diào)度方案,同時降低多工作流應(yīng)用的模糊執(zhí)行代價,表現(xiàn)出更優(yōu)的性能.

4.3.2 實際應(yīng)用中的決策實時性與調(diào)度分析

在實際應(yīng)用中,往往還需要考慮多工作流應(yīng)用的平均到達(dá)率和應(yīng)用規(guī)模等.在極端情況下,多個工作流應(yīng)用在同一時刻被提交至云邊協(xié)同環(huán)境中執(zhí)行,這種情形則考慮調(diào)度策略的決策實時性.為了比較WSPCP和其他基準(zhǔn)策略在模糊云邊協(xié)同環(huán)境中的決策時間,在中等(bl=2.5)的截止時間約束下,對4種不同規(guī)模的多工作流應(yīng)用調(diào)度進(jìn)行實驗,包括20、30、50和100,并分析WSPCP的調(diào)度決策實時性.對于不同規(guī)模的多工作流應(yīng)用調(diào)度,記錄10次獨(dú)立重復(fù)實驗的總決策時間(單位:s).圖5展示了在不同工作流應(yīng)用規(guī)模下不同調(diào)度策略的總決策時間,為了方便對比,圖5的縱坐標(biāo)采用底數(shù)為4的對數(shù)刻度,將總決策時間控制在合理的區(qū)間范圍內(nèi).值得注意的是,當(dāng)工作流應(yīng)用的規(guī)模為100時,WSPG和WSRS的總決策時間將超過64800s(即18 hour),這是無法接受的決策時間,因此在圖5中不展示二者的實際決策時間,僅以填充圖案為橫線的柱狀表示.

圖5 不同工作流應(yīng)用規(guī)模下不同調(diào)度策略的總決策時間Fig.5 Total decision time of different scheduling strategies under different workflow application scales

由圖5可以看出,與全局調(diào)度策略WSPG和WSRS相比,兩個啟發(fā)式調(diào)度策略WSPCP和WSGS在決策時間上具有絕對的優(yōu)勢,二者的單次決策時間僅1s不到,能夠做到接近實時調(diào)度.這是因為WSPCP和WSGS基于有向割邊的預(yù)處理機(jī)制,降低工作流應(yīng)用的任務(wù)規(guī)模,同時采用啟發(fā)式方法,基于某種尋優(yōu)策略,能夠快速得到較優(yōu)的可行調(diào)度方案;而WSPG和WSRS則需要在全局解空間中不斷迭代搜索,由于多工作流應(yīng)用調(diào)度的解空間隨著工作流應(yīng)用的規(guī)模指數(shù)級增長,因此需要花費(fèi)更多的決策時間,此類調(diào)度策略更適合靜態(tài)調(diào)度的情形.相對于WSGS,WSPCP所需的決策時間更久,這是因為對于每個到達(dá)的工作流應(yīng)用,WSPCP需要尋找工作流應(yīng)用的局部關(guān)鍵路徑,從而將其統(tǒng)一調(diào)度到服務(wù)器上,以減少任務(wù)之間的數(shù)據(jù)傳輸.從4.3.1節(jié)的結(jié)論來看,同樣是秒級的決策時間,較少的時間差能夠得到更優(yōu)的工作流應(yīng)用調(diào)度方案,這是值得的.

另外,工作流應(yīng)用的實際情況,包括其任務(wù)規(guī)模、任務(wù)的計算復(fù)雜度、任務(wù)之間的數(shù)據(jù)傳輸量等因素,也是實際調(diào)度過程中可能遇到的挑戰(zhàn).特別地,作為交通系統(tǒng)中的工作流應(yīng)用之一,車輛識別應(yīng)用的核心技術(shù)是DNN,而工作流應(yīng)用調(diào)度決策是影響車輛識別應(yīng)用中DNN性能的關(guān)鍵問題之一[1].處理能力有限的交通攝像頭會定期記錄道路車輛的圖像,但是通常無法在其截止時間內(nèi)完成應(yīng)用,因此往往需要將此類應(yīng)用提交到云邊協(xié)同環(huán)境進(jìn)行處理.在不確定性云邊協(xié)同環(huán)境中,計算環(huán)境的不確定性因素對此類問題的系統(tǒng)延遲影響很大,容易導(dǎo)致對最優(yōu)調(diào)度方案的誤判,很難從眾多方案中選擇最佳的服務(wù)器解決方案.本文所提出的調(diào)度策略WSPCP能夠為車輛識別應(yīng)用做出高效的工作流應(yīng)用調(diào)度決策,同時可以降低主要由層內(nèi)計算和層間數(shù)據(jù)傳輸在截止時間內(nèi)引起的執(zhí)行代價.具體而言,WSPCP可以將車輛識別應(yīng)用中的復(fù)雜DNN層(任務(wù))可以調(diào)度到云端執(zhí)行,而簡單的DNN層(任務(wù))則在邊緣進(jìn)行處理,云和邊緣平臺之間相互協(xié)作,以較低的執(zhí)行代價和系統(tǒng)延遲執(zhí)行DNN層;將局部關(guān)鍵路徑作為整體統(tǒng)一調(diào)度到同一服務(wù)器上執(zhí)行,從而一定程度上避免DNN層(任務(wù))之間的數(shù)據(jù)傳輸,有效減低數(shù)據(jù)傳輸產(chǎn)生的代價和時延.

5 結(jié)束語

針對模糊云邊協(xié)同環(huán)境下多工作流應(yīng)用調(diào)度,本文將服務(wù)器的計算性能和服務(wù)器之間的帶寬表示三角模糊數(shù),以體現(xiàn)云邊協(xié)同環(huán)境中的不確定性對多工作流應(yīng)用調(diào)度的影響.同時,針對泊松到達(dá)的多工作流應(yīng)用,提出一種基于局部關(guān)鍵路徑的多工作流應(yīng)用調(diào)度策略WSPCP,用于優(yōu)化截止時間約束下多工作流應(yīng)用的模糊執(zhí)行代價.實驗結(jié)果表明,與其他基準(zhǔn)策略相比,所提出的策略在多工作流應(yīng)用調(diào)度方面表現(xiàn)出良好的性能,在不同的截止時間約束下,WSPCP都能獲得多工作流應(yīng)用最優(yōu)的可行調(diào)度方案,同時實現(xiàn)了模糊執(zhí)行代價的有效優(yōu)化.在實際應(yīng)用中,對于不同規(guī)模的多工作流應(yīng)用,WSPCP展現(xiàn)了良好的決策實時性.同時,針對工作流應(yīng)用的實際情況,包括工作流應(yīng)用的任務(wù)規(guī)模、任務(wù)的計算復(fù)雜度、任務(wù)之間的數(shù)據(jù)傳輸量等因素,WSPCP具有一定的可行性.

在未來的工作中,希望建立一個適用于現(xiàn)實世界中多工作流應(yīng)用的實時調(diào)度系統(tǒng),整合云邊協(xié)同環(huán)境中的計算資源,考慮工作流應(yīng)用任務(wù)規(guī)模龐大、多個應(yīng)用同一時刻到達(dá)、工作流應(yīng)用執(zhí)行出錯等實際應(yīng)用的各類極端情況,對IoT設(shè)備提交的工作流應(yīng)用進(jìn)行高效地調(diào)度.同時,根據(jù)當(dāng)前云邊協(xié)同環(huán)境中服務(wù)器的實時負(fù)載情況和租賃成本,動態(tài)調(diào)整服務(wù)器的開啟和關(guān)閉,進(jìn)一步優(yōu)化多工作流應(yīng)用的執(zhí)行代價.