云邊協(xié)同計(jì)算架構(gòu)下大規(guī)模工廠接入的任務(wù)調(diào)度

滿君豐，趙龍乾，彭 成，李倩倩

(湖南工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，湖南 株洲 412007)

0 引言

由李伯虎院士在云制造基礎(chǔ)上提出的智慧云制造[1]，基于泛在網(wǎng)絡(luò)，以人為中心，借助信息化制造技術(shù)和智能科學(xué)技術(shù)等深度融合的數(shù)字化、網(wǎng)絡(luò)化、智能化技術(shù)手段，使用戶能夠通過云制造服務(wù)平臺(tái)隨時(shí)隨地按需獲取制造資源與能力，進(jìn)而智慧地完成制造全生命周期的各類活動(dòng)。《中國(guó)制造2025》指出，智慧云制造的總體目標(biāo)是實(shí)現(xiàn)制造過程的智能、高效、協(xié)同、綠色、安全[2]。

工業(yè)云與邊緣計(jì)算是智慧云制造的關(guān)鍵技術(shù)之一,是時(shí)下熱門的網(wǎng)絡(luò)范例，涉及異構(gòu)工業(yè)環(huán)境中的無縫連接，其通過將分布式工業(yè)設(shè)備聚集到一個(gè)公共資源池并調(diào)動(dòng)這些工業(yè)設(shè)備來進(jìn)行本地化生產(chǎn)制造。在工業(yè)環(huán)境下的云邊協(xié)同計(jì)算中，信息流是信息動(dòng)態(tài)交換的過程，其通過工業(yè)設(shè)備與網(wǎng)絡(luò)、工業(yè)設(shè)備與基礎(chǔ)設(shè)施、工業(yè)設(shè)備與工業(yè)設(shè)備之間信息的動(dòng)態(tài)交互，實(shí)現(xiàn)協(xié)作數(shù)據(jù)傳感和信息分析[3-4]。

傳統(tǒng)的工業(yè)云方案缺乏高效的任務(wù)調(diào)度方法，難以適配先進(jìn)工業(yè)生產(chǎn)過程中海量數(shù)據(jù)的實(shí)時(shí)分析和實(shí)時(shí)控制。任務(wù)調(diào)度亦是邊緣計(jì)算系統(tǒng)中的重要問題之一，其目的是獲得最佳的系統(tǒng)吞吐量和計(jì)算性能。傳統(tǒng)的調(diào)度算法包括啟發(fā)式調(diào)度算法、元啟發(fā)式調(diào)度算法等，在啟發(fā)式調(diào)度算法方面，最小完工時(shí)間調(diào)度算法雖然顯著提高了總?cè)蝿?wù)的完成率，但是調(diào)度器的計(jì)算資源和任務(wù)信息需要很高的維護(hù)成本；Min-min調(diào)度算法主要用于執(zhí)行時(shí)間短的任務(wù)，但是容易造成資源負(fù)載不均衡。啟發(fā)式調(diào)度算法沒有考慮不同應(yīng)用場(chǎng)景下的實(shí)際約束問題，其為啟發(fā)算法的改進(jìn)，是隨機(jī)算法與局部搜索算法結(jié)合的產(chǎn)物，旨在發(fā)現(xiàn)最優(yōu)或相對(duì)最優(yōu)的解決方案。粒子群算法是一類典型的元啟發(fā)算法，該算法在云計(jì)算任務(wù)調(diào)度領(lǐng)域可以獲得更好的效果，主要缺點(diǎn)是不考慮用戶預(yù)算；遺傳算法根據(jù)優(yōu)勝劣汰的規(guī)則，通過不斷迭代產(chǎn)生新的最優(yōu)解的近似解，但是在處理大規(guī)模組合問題時(shí)的效率較低。列表調(diào)度算法是異構(gòu)系統(tǒng)下經(jīng)典的調(diào)度算法，包括靜態(tài)調(diào)度算法和動(dòng)態(tài)調(diào)度算法。靜態(tài)調(diào)度算法根據(jù)任務(wù)之間的優(yōu)先級(jí)構(gòu)造相應(yīng)的調(diào)度列表，Sequential算法是典型的靜態(tài)調(diào)度算法；動(dòng)態(tài)調(diào)度算法根據(jù)處理器的使用情況和任務(wù)之間的依賴關(guān)系動(dòng)態(tài)構(gòu)造相應(yīng)的調(diào)度列表，處理器關(guān)鍵路徑(Critical Path on Processors， CPOP)算法是典型的動(dòng)態(tài)調(diào)度算法。傳統(tǒng)調(diào)度算法在高維度、高精度數(shù)據(jù)的處理和分析方面具有局限性，而云制造場(chǎng)景下的任務(wù)具有多種類、多模態(tài)、小批量等特征，因此傳統(tǒng)調(diào)度算法難以解決云制造場(chǎng)景下的問題。以鈑金行業(yè)為例，生產(chǎn)車間專注于鈑金零件的自動(dòng)化切割、沖孔、成形、剪切和嵌套過程，其生產(chǎn)隊(duì)列中有20～200個(gè)作業(yè)可供調(diào)度，需要在工作鏈的上下游進(jìn)行多站點(diǎn)協(xié)同和多任務(wù)并行，從而實(shí)現(xiàn)工廠車間的智能化集成應(yīng)用。在未來的十年里，越來越多的制造企業(yè)將采用工業(yè)4.0模式實(shí)現(xiàn)全球協(xié)同化制造，而隨著制造過程任務(wù)種類和任務(wù)規(guī)模的不斷增加，亟需研究面向云邊協(xié)同計(jì)算架構(gòu)的大規(guī)模工廠接入任務(wù)調(diào)度方法，以有效提高任務(wù)執(zhí)行效率，獲得較好的云邊協(xié)同效果[5-10]。

1 國(guó)內(nèi)外研究現(xiàn)狀及分析

近年來，人工智能在制造、交通、金融、醫(yī)藥等領(lǐng)域得到廣泛發(fā)展。然而，隨著機(jī)器學(xué)習(xí)和深度學(xué)習(xí)技術(shù)在云制造、無人駕駛等關(guān)鍵應(yīng)用領(lǐng)域的深度滲透，國(guó)內(nèi)外學(xué)者開始探索先進(jìn)的云邊協(xié)同方法來保證交互的實(shí)時(shí)性、精準(zhǔn)性和高效性。HUANG等[11]提出利用最佳剩余空間比來完成云邊協(xié)同任務(wù)，利用權(quán)衡模型將調(diào)度問題簡(jiǎn)化為線性規(guī)劃問題，通過線性規(guī)劃松弛給出了一個(gè)基于極值點(diǎn)求解的調(diào)度方案；WANG等[12]提出一種基于雙圖模型的動(dòng)態(tài)調(diào)度算法(Dynamic Tasks Scheduling algorithm based on Weighted Bi-graph model, DTSWB)，將調(diào)度問題轉(zhuǎn)化為最優(yōu)化雙圖匹配問題，建立了整數(shù)規(guī)劃模型，通過任務(wù)卸載、信息收集、任務(wù)分配和資源匹配4步實(shí)現(xiàn)了高效的任務(wù)調(diào)度。然而，上述方案往往只適用于求解整數(shù)線性規(guī)劃問題，其要求所有或部分決策變量都必須假定為非負(fù)整數(shù)，但是在實(shí)際的工業(yè)領(lǐng)域中，該解決方案過于理想，通過四舍五入得到的整數(shù)解會(huì)產(chǎn)生較大誤差。針對(duì)上述問題，JIAN等[13]提出一種改進(jìn)的混沌蝙蝠群算法，解決了傳統(tǒng)的云計(jì)算調(diào)度算法在任務(wù)復(fù)雜度與系統(tǒng)性能之間的平衡問題，通過引入混沌因子和二階震蕩機(jī)制，提高了系統(tǒng)中動(dòng)態(tài)參數(shù)的更新速度；WANG等[14]提出一種基于蟻群優(yōu)化算法的多任務(wù)協(xié)同調(diào)度算法(Cooperative Multi-tasks Scheduling based on Ant Colony Optimization algorithm, CMSACO)，算法考慮了任務(wù)利潤(rùn)、任務(wù)期限、任務(wù)依賴性、節(jié)點(diǎn)異構(gòu)性和負(fù)載均衡等因素，通過將調(diào)度問題轉(zhuǎn)化為約束優(yōu)化問題找到一個(gè)可行解。然而蟻群算法涉及的參數(shù)較多，容易使初始值選取不當(dāng)，同時(shí)采用單一的蟻群算法容易陷入局部最優(yōu)，在處理大規(guī)模組合問題時(shí)效率較低，不能很好地解決連續(xù)問題，而且在選取信息素等相關(guān)參數(shù)時(shí)大多憑借個(gè)人經(jīng)驗(yàn)，缺乏充分的理論依據(jù)。由于自身的局限性，LI等[15]將數(shù)據(jù)塊的最優(yōu)放置和任務(wù)的最優(yōu)調(diào)度相結(jié)合，通過高效存儲(chǔ)邊緣端設(shè)備中的數(shù)據(jù)減少提交任務(wù)的計(jì)算延遲和響應(yīng)時(shí)間。然而，上述方案均未考慮任務(wù)分配的硬件資源對(duì)處理時(shí)間的影響，以及未來應(yīng)對(duì)大規(guī)模工廠接入智能制造系統(tǒng)的現(xiàn)實(shí)需求，本文針對(duì)實(shí)際大型制造業(yè)生產(chǎn)車間中部署的邊緣端服務(wù)器和云端服務(wù)器協(xié)同作業(yè)的場(chǎng)景，給出了可靠的解決方案，并提出云邊協(xié)同計(jì)算架構(gòu)下大規(guī)模工廠接入的任務(wù)調(diào)度方法。

2 問題描述

隨著工業(yè)組網(wǎng)技術(shù)的迅猛發(fā)展，終端設(shè)備數(shù)量快速增加，海量數(shù)據(jù)的分析和處理增加了工業(yè)云平臺(tái)的運(yùn)行負(fù)擔(dān)，邊緣計(jì)算的出現(xiàn)將部分計(jì)算任務(wù)從云端遷移到邊緣側(cè)，為云制造的普及和發(fā)展提供了有力的技術(shù)支撐。

2.1 有向無環(huán)圖任務(wù)描述

根據(jù)工業(yè)物聯(lián)網(wǎng)環(huán)境的要求，云邊協(xié)同架構(gòu)主要由遠(yuǎn)端服務(wù)器集群組成的云端部件和邊緣端服務(wù)器集群組成的邊緣端部件構(gòu)成[16]。圖1所示為云邊協(xié)同計(jì)算架構(gòu)的工作過程示意圖。從具體業(yè)務(wù)上看，云端部件主要負(fù)責(zé)對(duì)終端設(shè)備所采集的數(shù)據(jù)進(jìn)行重量級(jí)模型訓(xùn)練，邊緣端部件進(jìn)行輕量級(jí)模型訓(xùn)練，以減少模型訓(xùn)練的時(shí)間和網(wǎng)絡(luò)時(shí)延，縮短系統(tǒng)的閉環(huán)響應(yīng)時(shí)間，提高工廠設(shè)備整體的生產(chǎn)效率。

簡(jiǎn)單起見，本文假設(shè)某工廠部署的邊緣端服務(wù)器中運(yùn)行的一個(gè)任務(wù)與云端服務(wù)器中運(yùn)行的一個(gè)任務(wù)有信息交換。圖3所示為云邊協(xié)同計(jì)算架構(gòu)下的2個(gè)DAG任務(wù)圖，云端部件下的DAG1中包含3個(gè)任務(wù)，邊緣端部件下的DAG2中包含5個(gè)任務(wù)，2個(gè)DAG任務(wù)圖共包含8個(gè)任務(wù)。其中：圓圈表示任務(wù)節(jié)點(diǎn)，云端部件和邊緣端部件中的節(jié)點(diǎn)分別用虛點(diǎn)和實(shí)線表示，圓圈中的字母表示任務(wù)節(jié)點(diǎn)的編號(hào)，云端部件用大寫字母，邊緣端部件用小寫字母，節(jié)點(diǎn)編號(hào)不區(qū)分大小寫，例如圓圈中字母a表示任務(wù)節(jié)點(diǎn)ta，ta=tA。帶箭頭的實(shí)線邊表示事件邊，邊上的數(shù)字表示兩個(gè)任務(wù)之間的事件計(jì)算開銷；帶箭頭的虛線邊表示云端部件和邊緣端部件的通信代價(jià)，邊上的數(shù)字表示兩個(gè)任務(wù)之間的通信延遲。每個(gè)DAG中包括1個(gè)入口任務(wù)節(jié)點(diǎn)和1個(gè)出口任務(wù)節(jié)點(diǎn)。考慮到不同任務(wù)的通信延遲，例如云計(jì)算的通信延遲約為100 ms，小型數(shù)據(jù)中心的通信延遲約為10 ms～40 ms，路由器的通信延遲約為5 ms，終端設(shè)備之間的通信延遲約為1 ms～2 ms[17]。這里通過time指令獲得兩個(gè)任務(wù)之間的事件計(jì)算開銷。

2.2 資源環(huán)境

任務(wù)調(diào)度是一個(gè)在規(guī)定時(shí)間內(nèi)將任務(wù)與資源進(jìn)行匹配的過程。調(diào)度算法是在任務(wù)的時(shí)限要求和資源約束的條件上，找到一組能夠有效提升應(yīng)用程序處理速度的調(diào)度方案。云邊協(xié)同計(jì)算架構(gòu)下的調(diào)度資源由云端部件和邊緣端部件共同組成，每個(gè)部件由多個(gè)性能異構(gòu)的物理機(jī)組成，每個(gè)物理機(jī)又虛擬化出多個(gè)虛擬機(jī)。假設(shè)有m個(gè)物理機(jī)節(jié)點(diǎn)，每個(gè)物理機(jī)由k個(gè)性能異構(gòu)的虛擬機(jī)組成，物理機(jī)之間通過網(wǎng)絡(luò)互聯(lián)。在每個(gè)物理機(jī)上，任務(wù)的執(zhí)行與通信可以同時(shí)執(zhí)行，分配到虛擬機(jī)上的任務(wù)之間的通信開銷為0，任務(wù)的執(zhí)行是非搶占式的。

2.3 任務(wù)調(diào)度目標(biāo)

云邊協(xié)同計(jì)算架構(gòu)下DAG任務(wù)圖調(diào)度是將相關(guān)任務(wù)分別調(diào)度到云端服務(wù)器和邊緣端服務(wù)器中的處理器上執(zhí)行。任務(wù)調(diào)度的目標(biāo)包括以下方面：

(1)整個(gè)任務(wù)集在處理器上的執(zhí)行時(shí)間makespan值盡可能小。

(2)針對(duì)邊緣端服務(wù)器設(shè)計(jì)扁平化的調(diào)度策略，而不是通過云端服務(wù)器來統(tǒng)一管理。

(4)Slack表示松馳度，用于度量任務(wù)調(diào)度算法的魯棒性，其反映一個(gè)任務(wù)調(diào)度算法所產(chǎn)生任務(wù)處理時(shí)間的不確定程度[18]。Slack的定義為

(1)

(5)不公平程度Unfairness(S)是用來衡量多DAG調(diào)度算法S不公平程度的重要指標(biāo)[19]，

Unfairness(S)=

?a∈A。

(2)

式中：A為給定的多個(gè)DAG的集合；AvgSlowdown是所有Slowdown的平均值；Slowdown反映DAG的滯后程度，Slowdown(a)=Mmulti(a)/Mown(a)。

3 云邊協(xié)同任務(wù)調(diào)度模型

3.1 云邊協(xié)同模式下的多DAG合并

有別于傳統(tǒng)的企業(yè)資源計(jì)劃(Enterprise Resource Planning, ERP)、制造執(zhí)行系統(tǒng)(Manufacturing Executive System, MES)等工業(yè)應(yīng)用軟件[20]，工業(yè)大數(shù)據(jù)下的軟件與產(chǎn)業(yè)鏈上下游會(huì)建立安全數(shù)據(jù)聯(lián)系，以實(shí)現(xiàn)信息共享和知識(shí)互補(bǔ)。因此云邊協(xié)同模式下的工業(yè)應(yīng)用軟件總體上可分為云邊相離類任務(wù)、云邊相交類任務(wù)、云邊包含類任務(wù)3類。圖4所示為云邊協(xié)同模式下的任務(wù)調(diào)度關(guān)系圖，其中圖4a為云邊相離類任務(wù)，即云端部件與邊緣端部件中的任務(wù)互不干擾，無數(shù)據(jù)往來；圖4b為云邊相交類任務(wù)，即云端部件與邊緣端部件中的任務(wù)互相通信，有數(shù)據(jù)交換；圖4c為云邊包含類任務(wù)，即云端部件中的任務(wù)是邊緣端部件中任務(wù)的子任務(wù)，或者邊緣端部件是云端部件中任務(wù)的子任務(wù)。

(1)云邊相離類任務(wù) 該類任務(wù)的特點(diǎn)是云端部件和邊緣端部件中的任務(wù)沒有數(shù)據(jù)往來，合并的方法是增加一個(gè)虛擬的入口任務(wù)節(jié)點(diǎn)和出口任務(wù)節(jié)點(diǎn)，然后更新虛擬入口任務(wù)節(jié)點(diǎn)和出口任務(wù)節(jié)點(diǎn)與相關(guān)任務(wù)節(jié)點(diǎn)的通信延遲和計(jì)算開銷，即

DAG_C=DAG_A∪DAG_B,DAG_A

≠DAG_B。

(3)

式中：集合DAG_A為DAG1；集合DAG_B為DAG2；集合DAG_C為DAG合并圖。圖5a所示為云邊相離類任務(wù)的DAG合并圖。

(2)云邊相交類任務(wù) 該類任務(wù)的特點(diǎn)是云端部件與邊緣端部件中的任務(wù)有數(shù)據(jù)交換，合并的方式是入口任務(wù)節(jié)點(diǎn)同時(shí)作為每個(gè)子DAG入口任務(wù)節(jié)點(diǎn)的父親節(jié)點(diǎn)，然后通過替換實(shí)現(xiàn)DAG合并，

DAG_C=DAG_A⊕DAG_B,

DAG_A∩DAG_B。

(4)

圖5b所示為云邊相交類任務(wù)的DAG合并圖，其中虛線節(jié)點(diǎn)表示云端部件和邊緣端部件為相同任務(wù)。

(3)云邊包含類任務(wù) 該類任務(wù)的特點(diǎn)是云端部件中的任務(wù)為邊緣端部件中任務(wù)的子任務(wù)，或者邊緣端部件是云端部件中任務(wù)的子任務(wù)，因此通過式(5)實(shí)現(xiàn)DAG合并。圖5c所示為云邊包含類任務(wù)的DAG合并圖。在實(shí)際云制造中，通過冗余的方式可以增強(qiáng)系統(tǒng)的健壯性[21]。

DAG_C=

(5)

3.2 云邊協(xié)同模式下的多DAG分割

tES(j)為一個(gè)任務(wù)j的最早可能開始時(shí)間，任何一個(gè)任務(wù)都必須在其所有前驅(qū)任務(wù)全部完工后才能開始；tEF(j)為任務(wù)j的最早可能完成時(shí)間，即任務(wù)按最早開始時(shí)間所能達(dá)到的完成時(shí)間。計(jì)算公式為：

tES(j)=0；

tES(j)=maxk{tES(k)+t(k)};

tEF(j)=tES(j)+t(j)。

(6)

tLS(j)為一個(gè)任務(wù)j的最遲開始時(shí)間，即任務(wù)j在不影響整個(gè)任務(wù)如期完成的前提下，必須開始的最晚時(shí)間；tLF(j)為任務(wù)j的最遲完成時(shí)間，即任務(wù)按最遲時(shí)間開始所能達(dá)到的完成時(shí)間。計(jì)算公式為：

tLS(j)=maxk{tLS(k)-t(k)}；

tLF(j)=tLS(j)+t(j)。

(7)

式(6)是由起始點(diǎn)向終點(diǎn)逐個(gè)遞推的過程，式(7)是由終點(diǎn)向起始點(diǎn)逐個(gè)遞推的過程，本文通過式(6)和式(7)找到DAG合并圖的關(guān)鍵路徑CP={cp1,cp2,…,cpm},m∈N。DAG合并圖由關(guān)鍵任務(wù)集CTS和非關(guān)鍵任務(wù)集NCTS組成，其類型分為邊緣端任務(wù)EST和云端任務(wù)CST，定義如下：

DAG=CTS+NCTS；

CTS=CTSEST+CTSCST；

NCTS=NCTSEST+NCTSCST；

{CTS,NCTS}=nEST+mCST,n∈N,m∈N。

(8)

DAG任務(wù)圖的關(guān)鍵路徑是進(jìn)入任務(wù)到退出節(jié)點(diǎn)的最長(zhǎng)路徑，該路徑上的每個(gè)任務(wù)為所有關(guān)鍵路徑提供的最低成本。本文根據(jù)式(8)對(duì)合并后的DAG進(jìn)行分割，圖6所示為云邊協(xié)同計(jì)算架構(gòu)下DAG合并圖的分割圖，虛線箭頭形成的路徑為DAG合成圖的關(guān)鍵路徑，其中圖6a為云邊包含類任務(wù)DAG分割圖，每個(gè)子圖的度分別為{2,0,0,2}；圖6b為云邊相交類任務(wù)DAG分割圖，每個(gè)子圖的度分別為{2,2,0}；圖6c為云邊包含類任務(wù)DAG分割圖，每個(gè)子圖的度分別為{2,1,0}。

3.3 云邊協(xié)同模式下的任務(wù)分配

本文提出的改進(jìn)的異構(gòu)最早完成時(shí)間(Improved Heterogeneous Earliest Finish Time，IHEFT)算法主要由權(quán)值分配、任務(wù)優(yōu)先級(jí)分配、處理器選擇3個(gè)階段構(gòu)成。假設(shè)用R表示處理器資源集合，R={CPUs,GPUs,FPGAs}，GPUs是使用最廣泛的加速器，F(xiàn)PGAs可以提供更好的性能功率比，它們?cè)诟咝阅苡?jì)算等多個(gè)應(yīng)用領(lǐng)域中發(fā)揮了重要的作用[22-23]。用無向圖RG=(T,C)描述任務(wù)在不同處理器上的計(jì)算性能，其中T表示任務(wù)節(jié)點(diǎn)，C={c11,c12,…,cnm},n∈N*,m∈N*(n為任務(wù)個(gè)數(shù)，m為處理器個(gè)數(shù))表示任務(wù)在不同處理器上的計(jì)算性能，則任務(wù)的平均計(jì)算性能

(9)

在任務(wù)優(yōu)先級(jí)分配階段，需要建立多源異構(gòu)場(chǎng)景下的任務(wù)優(yōu)先級(jí)列表。因?yàn)樵趯?shí)際云制造環(huán)境中，無論云端任務(wù)還是邊緣端任務(wù)都具有任務(wù)的多種類、大規(guī)模、強(qiáng)關(guān)聯(lián)等特征，所以原來任務(wù)之間邊的權(quán)值不能準(zhǔn)確反映云邊協(xié)同計(jì)算架構(gòu)下任務(wù)的優(yōu)先級(jí)，需要根據(jù)DAG合并圖關(guān)鍵路徑的邊的權(quán)值之和來確定云邊協(xié)同計(jì)算架構(gòu)下任務(wù)的優(yōu)先級(jí)。根據(jù)優(yōu)先級(jí)的值將云邊協(xié)同計(jì)算架構(gòu)下的DAG合并圖降序排列，構(gòu)成任務(wù)圖列表，以便后期進(jìn)行任務(wù)調(diào)度。云邊協(xié)同計(jì)算架構(gòu)下DAG合并圖Dk的優(yōu)先級(jí)rank(Dk)等于該圖關(guān)鍵路徑上所有事件邊的權(quán)值之和，即

(10)

后續(xù)任務(wù)調(diào)度操作將從任務(wù)圖列表具有較高優(yōu)先級(jí)的任務(wù)圖開始優(yōu)先分配處理器資源。根據(jù)任務(wù)圖列表構(gòu)成相應(yīng)的路徑列表，路徑pk的優(yōu)先級(jí)

(11)

在云邊協(xié)同計(jì)算架構(gòu)下的DAG分割圖中，云端子圖有ξ個(gè)，其度值為o={o1,o2,…,oξ}；邊緣端子圖有ζ個(gè)，其度值為o={o1,o2,…,oζ}。由此得到第i個(gè)任務(wù)圖在調(diào)度執(zhí)行時(shí)所需要的處理器數(shù)量

(12)

式中函數(shù)wj為采用云邊協(xié)同計(jì)算架構(gòu)下子圖度的計(jì)算策略。通過DAG分割可以確定其資源集合類型，并在處理器分配階段根據(jù)DAG分割所得結(jié)果向任務(wù)分配資源[24-25]。DAG分割后的任務(wù)集按IHEFT算法選擇和調(diào)度處理器。

4 云邊協(xié)同任務(wù)調(diào)度算法

為了充分利用云端和邊緣端資源實(shí)現(xiàn)任務(wù)的高效計(jì)算，本文提出云邊協(xié)同任務(wù)調(diào)度(Cloud and Edge Collaborative Task Scheduling, CECTS)算法，算法包括DAG合并、DAG分割、處理器分配3個(gè)步驟，其中DAG合并用于減少處理冗余任務(wù)帶來的時(shí)間開銷。

4.1 DAG合并算法

假設(shè)云邊協(xié)同計(jì)算架構(gòu)下有m個(gè)工廠，其中部署的邊緣端服務(wù)器和云端服務(wù)器共執(zhí)行n個(gè)任務(wù)，則DAG合并算法如算法1所示。

算法1DAG合并算法。

輸入：DAG。

輸出：MergeDAG。

1: function Merging(DAG):

2: while DAGi∈DAG且i∈{1,2,…,m}do

3: while SubDAGj∈DAGi且j∈{1,2,…,n}do

4: MergeDAGj=SubDAGj

5: if(MergeDAGj≠SubDAGj+1)

6: MergeDAGj=MergeDAGj∪SubDAGj+1

7: if(MergeDAGj∩SubDAGj+1)

8: MergeDAGj=MergeDAGj⊕SubDAGj+1

9: if(MergeDAGj?SubDAGj+1)

10: MergeDAGj=SubDAGj+1

11: if(MergeDAGj?SubDAGj+1)

12: MergeDAGj=MergeDAGj

13: end if

14: end while

15: return MergeDAG

16: end function

算法第2～15行根據(jù)DAG任務(wù)圖子圖的類型對(duì)邊緣任務(wù)集和云端任務(wù)集進(jìn)行合并操作，包括云邊相離、云邊相交、邊緣端任務(wù)包含云端任務(wù)、云端任務(wù)包含邊緣端任務(wù)4種情況。算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)，而且工廠數(shù)越多，其優(yōu)點(diǎn)越明顯。

4.2 DAG分割算法

本文采用關(guān)鍵路徑算法對(duì)所得到的DAG合并圖進(jìn)行分割處理，并將分割后的任務(wù)分為關(guān)鍵任務(wù)集和非關(guān)鍵任務(wù)集兩類，其分割規(guī)則如算法2所示。

算法2DAG分割算法。

輸入：MergeDAGj。

輸出：CTSj,NCTSj。

1: function Partitioning(MergeDAGj,CP(MergeDAGj)):

2: N←order tasks based on level

3: whileN is not empty do

4: while ti∈MergeDAGj且i∈{1,2,…,ξ+ζ} do

5: if(ti∈CP(MergeDAGj))

6: add task tiin CTS

7: remove task tifrom N

8: else

9: add task tiin NCTS

10: remove task tifrom N

11: end else

12: end if

13: end while

14: return CTSj,NCTSj

15: end function

算法第2行遍歷每個(gè)DAG合并圖獲得節(jié)點(diǎn)個(gè)數(shù)，第3～14行對(duì)DAG合并圖進(jìn)行分割處理，將屬于關(guān)鍵路徑的任務(wù)置于關(guān)鍵任務(wù)集，不屬于關(guān)鍵路徑的任務(wù)置于非關(guān)鍵任務(wù)集。該算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)，而且任務(wù)數(shù)越多，其優(yōu)點(diǎn)越明顯。

4.3 處理器分配算法

本文采用IHEFT算法對(duì)所得到的DAG分割圖進(jìn)行任務(wù)調(diào)度處理，并按關(guān)鍵路徑權(quán)重之和rank(Dk)對(duì)DAG任務(wù)圖進(jìn)行排序，得到云邊協(xié)同計(jì)算架構(gòu)下不同工廠的優(yōu)先級(jí)列表；將每個(gè)工廠的任務(wù)按rank(pk)排序，然后將任務(wù)分配到?個(gè)處理器上。處理器分配算法如算法3所示。

算法3處理器分配算法。

輸入：CTSj,NCTSj。

輸出：rank(Dk)j,rank(pk)j,?j。

1: function IHEFT(CTSj,NCTSj):

4: if task tiis the last task then

5: rank value of ti=its average execution time

6: else:

8: end if

9: Sort the DAG in a scheduling list by descending order of rank(Dk)jvalues

10: Sort the tasks in a scheduling list by descending order of rank(pk)jvalues

11: Assign task tito the best processor base on ?jlist

12: return set of processors with the mapping tasks, rank(Dk)j, rank(pk)j

13: end function

算法第2行遍歷每個(gè)DAG分割圖的任務(wù)節(jié)點(diǎn)，計(jì)算每個(gè)任務(wù)在處理器上的平均計(jì)算性能，第3行計(jì)算DAG合并圖關(guān)鍵路徑的邊的權(quán)值之和，第4～8行計(jì)算DAG分割圖路徑的優(yōu)先級(jí)，第9行按任務(wù)圖優(yōu)先級(jí)降序排序，第10行按路徑優(yōu)先級(jí)降序排序，第11行將任務(wù)分配到最佳的處理器上，第12行返回映射任務(wù)的處理器集等相關(guān)信息。該算法的時(shí)間復(fù)雜度為O(1),空間復(fù)雜度為O(1)，而且任務(wù)數(shù)越多，其優(yōu)點(diǎn)越明顯。

5 仿真實(shí)驗(yàn)與結(jié)果分析

5.1 實(shí)驗(yàn)?zāi)康?/h3>

為了驗(yàn)證本文CECTS算法，在相同實(shí)驗(yàn)條件下與Sequential和CPOP算法進(jìn)行比較，主要比較任務(wù)跨度makespan、任務(wù)平均等待時(shí)間AWT和平均Slack值。

5.2 模擬環(huán)境

基于SimGrid提供的模擬器工具包，構(gòu)建一個(gè)異構(gòu)多核處理器仿真環(huán)境[26]。實(shí)驗(yàn)使用的計(jì)算機(jī)配置為Intel Core i5-7200U CPU @ 2.5 GHz 2.7 GHZ處理器，8 GB內(nèi)存。

5.3 任務(wù)調(diào)度過程分析

采用云邊協(xié)同計(jì)算架構(gòu)，假設(shè)云端服務(wù)器和邊緣端服務(wù)器中運(yùn)行的任務(wù)如圖7所示，以下詳細(xì)分析CECTS算法進(jìn)行多DAG任務(wù)圖的合并、分割，以及在分布式異構(gòu)計(jì)算環(huán)境下的處理器分配過程。

表1 DAG1任務(wù)集在處理器集上的調(diào)度時(shí)間

表2 DAG2任務(wù)集在處理器集上的調(diào)度時(shí)間

由于DAG1和DAG2為相交類任務(wù)，根據(jù)DAG合并算法可得DAG任務(wù)圖合并圖(如圖8a)，根據(jù)DAG分割算法可得DAG任務(wù)圖分割圖(如圖8b)，根據(jù)DAG處理器分配算法可得處理器資源平均利用率(如表3)。

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

CECTS算法的時(shí)間復(fù)雜度為O(n)，采用某鼓風(fēng)機(jī)現(xiàn)場(chǎng)采集的實(shí)際數(shù)據(jù)進(jìn)行分析，可知與傳統(tǒng)集中式遍歷方式相比，CECTS算法具有優(yōu)越性。圖9所示為邊緣端服務(wù)器數(shù)量增加對(duì)計(jì)算時(shí)間開銷的影響。

由式(11)可得DAG任務(wù)圖分割圖子圖的度為{2,0,3}，即將云邊協(xié)同計(jì)算架構(gòu)下的云端任務(wù)分配到2個(gè)處理器上，邊緣端任務(wù)分配到3個(gè)處理器上。

任務(wù)集經(jīng)過CECTS算法調(diào)度后，任務(wù)與處理器的對(duì)應(yīng)關(guān)系如圖10所示，圖10a和10b分別表示同一任務(wù)集在不同網(wǎng)絡(luò)環(huán)境下的調(diào)度策略。圖11a和圖11b所示分別為同一任務(wù)集通過Sequential和CPOP算法調(diào)度的結(jié)果。由圖10和圖11可知，CECTS算法的任務(wù)平均執(zhí)行時(shí)間為54 s，Sequential算法的任務(wù)平均執(zhí)行時(shí)間為97 s，CPOP算法的任務(wù)平均執(zhí)行時(shí)間為61 s。同時(shí)可見，在減少任務(wù)執(zhí)行時(shí)間的情況下，CECTS算法可以減少處理器的使用數(shù)量，圖10中云端處理器的使用個(gè)數(shù)為2個(gè)，圖11b中云端處理器的使用個(gè)數(shù)為3個(gè)。

系統(tǒng)的處理器利用率是實(shí)時(shí)系統(tǒng)運(yùn)行性能的重要指標(biāo)，其可以表征系統(tǒng)的時(shí)間特性和任務(wù)狀態(tài)[27]，表3所示為3種算法的處理器資源平均利用率?？梢?，采用CECTS算法的處理器資源平均利用率最高。

表3 3種算法的處理器資源平均利用率 %

分別采用3種算法對(duì)10個(gè)DAG任務(wù)圖進(jìn)行調(diào)度，表4所示為3核處理器下3種算法Slack值的對(duì)比情況。分別采用3種算法對(duì)DAG任務(wù)圖模型進(jìn)行調(diào)度，得到所有任務(wù)的跨度、平均等待時(shí)間和平均Slack值，如圖12所示。

表4 CECTS,CPOP,Sequential算法的Slack值

從實(shí)驗(yàn)數(shù)據(jù)可見，隨著DAG數(shù)量的增加，任務(wù)調(diào)度的跨度和任務(wù)平均等待時(shí)間均會(huì)相應(yīng)增加?？傮w來說，CECTS算法的性能最佳，CPOP算法其次，Sequential算法最差。在任務(wù)調(diào)度的跨度方面，CECTS算法比CPOP算法最低降低17%，最高降低28%；CECTS算法比Sequential算法最低降低74%，最高降低80%。在平均任務(wù)等待時(shí)間方面，CECTS算法比CPOP算法最低降低47%，最高降低54%；CECTS算法比Sequential算法最低降低96%，最高降低97%。在平均Slack值方面，CECTS算法比CPOP算法最低降低52%，最高降低63%；CECTS算法比Sequential算法最低降低84%，最高降低93%。

調(diào)度算法的公平性用于表明多個(gè)DAG任務(wù)圖調(diào)度算法的可靠程度，是反映該算法能否公平處理不同優(yōu)先級(jí)別任務(wù)需求的重要指標(biāo)。圖13所示為CECTS算法和CPOP算法的公平程度，其中CPOP算法比CECTS算法最低提高了106.25%，最高提高了176.92%，CECTS算法的方差為0.001 246，CPOP算法的方差為0.006 462，而且隨著任務(wù)圖數(shù)量的增加，CECTS的穩(wěn)定性更好。

任務(wù)完成率定義為任務(wù)完成的數(shù)量與任務(wù)總數(shù)的比值，更高的任務(wù)完成率能夠帶來更好的服務(wù)質(zhì)量。通過比較CECTS算法與Min-min算法、DTSWB、CMSACO，得到任務(wù)完成率對(duì)比圖，如圖14所示?？梢姡?dāng)任務(wù)數(shù)在60個(gè)以內(nèi)時(shí)，CECTS算法、DTSWB、CMSACO都能保持較好的任務(wù)完成率，Min-min算法因負(fù)載不均衡導(dǎo)致任務(wù)完成率只有80%左右；當(dāng)任務(wù)數(shù)達(dá)到80個(gè)時(shí)，DTSWB和CMSACO的任務(wù)完成率均明顯降低，分別為78.2%和77.4%；當(dāng)任務(wù)數(shù)為100時(shí)，DTSWB的任務(wù)完成率只有53.2%，而本文CECTS算法的任務(wù)完成率為89.7%，具有較好的穩(wěn)定性。

負(fù)載率表示使用處理器資源的利用率，定義為處理器使用的數(shù)量與其總數(shù)的比值。提升負(fù)載率有助于加快任務(wù)的處理速度，從而提高服務(wù)質(zhì)量。圖15所示為CECTS算法、DTSWB和CMSACO的負(fù)載率對(duì)比圖，可見，當(dāng)任務(wù)數(shù)量達(dá)到一定規(guī)模時(shí)，CECTS算法、DTSWB和CMSACO都能保持較好的負(fù)載率；當(dāng)任務(wù)數(shù)量在30個(gè)以內(nèi)時(shí)，DTSWB和CMSACO因負(fù)載不均衡導(dǎo)致負(fù)載率只有80%左右，而CECTS算法的負(fù)載率為96%左右，具有較好的穩(wěn)定性。

通過以上實(shí)驗(yàn)分析可知，CECTS算法在平均任務(wù)等待時(shí)間、平均Slack值兩方面均優(yōu)于CPOP算法和Sequential算法；在算法的公平程度方面，CECTS算法具有較高的公平性，且隨DAG數(shù)量的增加保持了較好的穩(wěn)定性。通過比較CECTS算法、DTSWB和CMSACO可知，本文CECTS算法在任務(wù)完成率和負(fù)載率方面均有比較突出的優(yōu)勢(shì)。

6 結(jié)束語

隨著網(wǎng)絡(luò)信息技術(shù)的不斷發(fā)展，以智能制造為主導(dǎo)的新型工業(yè)模式得到廣泛應(yīng)用，本文針對(duì)云制造場(chǎng)景，給出云邊協(xié)同計(jì)算架構(gòu)下大規(guī)模工廠接入的任務(wù)調(diào)度方法，通過多任務(wù)圖合并、任務(wù)圖分割和處理器分配3個(gè)步驟對(duì)復(fù)雜場(chǎng)景下的任務(wù)調(diào)度問題進(jìn)行求解。仿真結(jié)果表明，與其他調(diào)度算法相比，本文提出的CECTS算法可以減少處理冗余任務(wù)的時(shí)間開銷，并按云邊協(xié)同方式將任務(wù)調(diào)度到合適的處理器上，在整體上提高了任務(wù)處理的速度，從而使任務(wù)在大規(guī)模邊緣端服務(wù)器資源受限的情況下得到更高效的處理。

考慮存在特定需求、設(shè)備作業(yè)期間的突發(fā)事件及未知用戶對(duì)系統(tǒng)的影響，下一步將改進(jìn)和細(xì)化需求分析模型，在獲取真實(shí)數(shù)據(jù)后，對(duì)本文方案的有效性進(jìn)行評(píng)估，并進(jìn)一步提高算法性能。另外，還將深入研究邊緣側(cè)設(shè)備協(xié)同作業(yè)的任務(wù)調(diào)度方案，以對(duì)本文工作進(jìn)行補(bǔ)充。