基于資源匹配的邊緣異構(gòu)集群在線任務(wù)調(diào)度

摘" 要： 隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展，終端業(yè)務(wù)對(duì)時(shí)延和算力的要求越來(lái)越高，采用異構(gòu)處理器構(gòu)建邊緣集群成為解決通用芯片算力不足的可行方案。然而現(xiàn)有的任務(wù)調(diào)度研究往往只考慮CPU、內(nèi)存等通用計(jì)算資源，缺少對(duì)異構(gòu)計(jì)算技術(shù)與邊緣計(jì)算相融合場(chǎng)景的考慮。針對(duì)邊緣側(cè)的異構(gòu)在線任務(wù)調(diào)度問(wèn)題，結(jié)合時(shí)延和負(fù)載均衡兩個(gè)指標(biāo)，提出一個(gè)異構(gòu)資源匹配度的概念，建立一種算力、需求和匹配度模型，并基于此設(shè)計(jì)一個(gè)在線任務(wù)調(diào)度算法。仿真實(shí)驗(yàn)結(jié)果表明，對(duì)比現(xiàn)有算法，所提算法在不增加計(jì)算復(fù)雜度和時(shí)延的前提下，有效提升了集群負(fù)載均衡，減少了資源碎片，提高了邊緣側(cè)處理性能。

關(guān)鍵詞： 邊緣計(jì)算； 異構(gòu)集群； 任務(wù)調(diào)度； 資源匹配； 負(fù)載均衡； 異構(gòu)計(jì)算

中圖分類號(hào)： TN929.5?34； TP393.0" " " " " " " 文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " " " "文章編號(hào)： 1004?373X（2025）06?0031?08

Edge heterogeneous clusters online task scheduling based on resource matching

CHEN Jun1， WANG Xin2， ZENG Hao2， QIN Jian2

（1. Southwest China Institute of Electronic Technology， Chengdu 610036， China;

2. College of Communication Engineering， Chongqing University， Chongqing 400030， China）

Abstract： With the development of mobile internet， terminal services have increasingly requirements on latency and computing power. Using heterogeneous processor to build edge clusters has become a feasible solution to solve the lack of computing power of general?purpose chips. However， current task scheduling research often focuses on general?purpose computing resources such as CPUs and memory， overlooking the integration of heterogeneous computing technologies with edge computing. In allusion to the heterogeneous online task scheduling problem on the edge side， a concept of heterogeneous resource matching degree is proposed by combining the indicators of latency and load balancing. The simulation experimental results show that， in comparison with existing algorithms， the proposed algorithm can effectively improve cluster load balancing， reduce resource fragmentation， and enhance edge side processing performance without increasing computational complexity and latency.

Keywords： edge computing; heterogeneous cluster; task scheduling; resource matching; load balancing; heterogeneous computing

0" 引" 言

隨著智能終端的普及，產(chǎn)生的數(shù)據(jù)遠(yuǎn)超過(guò)去幾十年的總和，而受性能、能耗等因素限制，僅靠終端很難滿足用戶在算力和延遲方面的需求。為此，人們分別在云端和邊端提出了云計(jì)算和邊緣計(jì)算。其中邊緣計(jì)算作為云計(jì)算在邊緣端的延伸部分，可大幅降低時(shí)延，提高網(wǎng)絡(luò)和計(jì)算資源利用率，但是其計(jì)算資源相較云計(jì)算中心還是受限的。因此，如何為邊緣側(cè)設(shè)計(jì)合理的調(diào)度方法，優(yōu)化資源和任務(wù)配置以滿足用戶需求，成為亟待解決的問(wèn)題。

此外，傳統(tǒng)的計(jì)算核心通常采用CPU，隨著摩爾定律已逼近極限，性能提升也逐漸到達(dá)了瓶頸。為應(yīng)對(duì)復(fù)雜計(jì)算場(chǎng)景，人們引入了GPU、FPGA、ASIC等處理器進(jìn)行硬件加速，尤其在邊緣側(cè)，往往由異構(gòu)計(jì)算節(jié)點(diǎn)共同構(gòu)成邊緣服務(wù)器集群。大量異構(gòu)算力資源的引入一方面能提供互為補(bǔ)充的計(jì)算能力，但另一方面更加提高了任務(wù)調(diào)度算法的復(fù)雜性。

廣義的任務(wù)調(diào)度是指邊緣計(jì)算服務(wù)器對(duì)終端提交任務(wù)的執(zhí)行位置和執(zhí)行順序進(jìn)行協(xié)調(diào)，一般由任務(wù)資源匹配和任務(wù)順序調(diào)度[1]兩個(gè)子問(wèn)題組成。分別從資源和任務(wù)的角度出發(fā)，通過(guò)調(diào)度策略將任務(wù)和資源進(jìn)行匹配，并以合理的方式排序處理，以達(dá)到優(yōu)化特定指標(biāo)并提升資源利用率的目的。在任務(wù)調(diào)度算法的優(yōu)化過(guò)程中，需要綜合考慮任務(wù)截止時(shí)間、用戶滿意度、輸入時(shí)間、執(zhí)行任務(wù)的成本以及能耗等參數(shù)。任務(wù)調(diào)度一般可分為獨(dú)立任務(wù)調(diào)度和相互依賴任務(wù)調(diào)度。在異構(gòu)計(jì)算資源的場(chǎng)景下，由于不同芯片的指令集和微架構(gòu)差異，很難在運(yùn)行時(shí)（runtime）調(diào)整拆分方式。預(yù)先將原始任務(wù)劃分為多個(gè)獨(dú)立子任務(wù)模塊[2]更加實(shí)際可行。

在線任務(wù)調(diào)度算法指的是一個(gè)任務(wù)到達(dá)時(shí)，調(diào)度策略立即對(duì)其進(jìn)行調(diào)度，并將其映射到指定的計(jì)算節(jié)點(diǎn)上。傳統(tǒng)的在線任務(wù)調(diào)度算法包括輪詢調(diào)度算法（Round Robin， RR）、機(jī)會(huì)負(fù)載均衡算法（OLB）、最小執(zhí)行時(shí)間算法（MET）以及最小完成時(shí)間算法（MCT）等。針對(duì)在線任務(wù)調(diào)度的相關(guān)研究，文獻(xiàn)[3]提出一種Tetris算法，通過(guò)將任務(wù)和資源的CPU、內(nèi)存、硬盤等多種資源進(jìn)行打包，讓任務(wù)像俄羅斯方塊一樣調(diào)度到資源中，取得了集群效率和平均完成時(shí)間上的提高。文獻(xiàn)[4]提出OnDisc調(diào)度算法，考慮的是所有處理時(shí)間已知、計(jì)算資源之間不存在差異的情況。文獻(xiàn)[5]提出在線期限感知任務(wù)調(diào)度算法Dedas，將任務(wù)調(diào)度分為資源匹配和順序調(diào)度兩部分，不僅滿足截止時(shí)間的任務(wù)數(shù)量達(dá)到最大化，而且算法增加了對(duì)網(wǎng)絡(luò)資源的考量。文獻(xiàn)[6]提出了一種基于優(yōu)先級(jí)的任務(wù)調(diào)度算法，面向云?霧?端三層計(jì)算環(huán)境，這種調(diào)度算法根據(jù)任務(wù)的優(yōu)先級(jí)（高、中或低）將請(qǐng)求放入適當(dāng)?shù)膬?yōu)先級(jí)隊(duì)列，再檢查霧服務(wù)器可用的資源并分配給高優(yōu)先級(jí)的任務(wù)，若資源不足，則將任務(wù)分配給云中心進(jìn)行計(jì)算。這種算法成功減少了總體響應(yīng)時(shí)間和成本。

上述相關(guān)研究通常聚焦在CPU、內(nèi)存、通信等方面，忽略了邊緣計(jì)算場(chǎng)景下計(jì)算資源的異構(gòu)特點(diǎn)。針對(duì)該問(wèn)題，本文提出了異構(gòu)資源匹配度指標(biāo)，建立了算力、需求和匹配度模型，并基于此設(shè)計(jì)了相應(yīng)的邊緣側(cè)在線任務(wù)調(diào)度算法。實(shí)驗(yàn)結(jié)果表明，本文的調(diào)度算法可以綜合考慮任務(wù)時(shí)延和節(jié)點(diǎn)負(fù)載均衡，有效提升了邊緣集群的性能。

1" 異構(gòu)集群任務(wù)調(diào)度

1.1" 問(wèn)題定義

假設(shè)在某時(shí)刻，邊緣異構(gòu)集群中有n個(gè)計(jì)算節(jié)點(diǎn)i∈{1，2，…，n}，任務(wù)調(diào)度節(jié)點(diǎn)接收到m個(gè)計(jì)算任務(wù)Tj（j∈{1，2，…，m}）。由于獨(dú)立任務(wù)具有原子性，不可分割，且為了避免遷移開(kāi)銷，不考慮任務(wù)調(diào)度后計(jì)算節(jié)點(diǎn)將任務(wù)遷移至其他節(jié)點(diǎn)的情況，對(duì)于任務(wù)Tj來(lái)說(shuō)，式（1）定義了二進(jìn)制變量[xji]來(lái)表示任務(wù)Tj是否被調(diào)度至計(jì)算節(jié)點(diǎn)i上進(jìn)行處理。

用[dj]表示任務(wù)Tj的可容忍時(shí)延，即超出該時(shí)延，無(wú)法滿足用戶的需求。本文用[tji]來(lái)表示將任務(wù)Tj分配在計(jì)算節(jié)點(diǎn)[i]上時(shí)的任務(wù)完成時(shí)間（包括計(jì)算時(shí)間和通信時(shí)間），則tji需滿足：

根據(jù)以上分析，任務(wù)調(diào)度問(wèn)題可拆解為任務(wù)優(yōu)先級(jí)調(diào)度和任務(wù)?資源匹配兩個(gè)子問(wèn)題，如圖1所示。子問(wèn)題1實(shí)現(xiàn)對(duì)任務(wù)集合T的排序，確定任務(wù)的先后順序并生成任務(wù)隊(duì)列；子問(wèn)題2則是根據(jù)計(jì)算節(jié)點(diǎn)集合R和任務(wù)集合T的模型進(jìn)行資源匹配，使資源滿足任務(wù)需求。任務(wù)調(diào)度就是對(duì)這兩個(gè)子問(wèn)題進(jìn)行優(yōu)化研究，實(shí)現(xiàn)對(duì)邊緣計(jì)算資源的高效、合理利用。

1.2" 異構(gòu)資源算力模型

為了對(duì)邊緣計(jì)算下的異構(gòu)計(jì)算資源進(jìn)行性能評(píng)估，需要選定合適的性能指標(biāo)。對(duì)于通用型計(jì)算芯片如CPU和GPU，一般可采用計(jì)算頻率MIPS（Million Instruction Per Second）作為算力評(píng)價(jià)指標(biāo)。但由于架構(gòu)差異，該指標(biāo)無(wú)法準(zhǔn)確反映異構(gòu)設(shè)備的計(jì)算能力，故本文采用FLOPS（Floating?point Operations Per Second）作為通用處理器算力指標(biāo)。該指標(biāo)面向大多數(shù)任務(wù)都存在的浮點(diǎn)運(yùn)算，可以屏蔽硬件架構(gòu)差異，更好地反映硬件算力。而對(duì)于專用計(jì)算芯片，如FPGA、ASIC等，則采用每秒運(yùn)行次數(shù)（Operations Per Second， OPS）來(lái)衡量芯片性能，本文將采用TOPS（1012 OPS）、GOPS（109 OPS）等常用單位。這些單位可以與特定專用計(jì)算任務(wù)的算力描述相對(duì)應(yīng)，例如神經(jīng)網(wǎng)絡(luò)中的AlexNet處理224×224的圖像，需要1.4 GOPS的計(jì)算能力[7]。另外需注意，本文提到的任務(wù)在GPU、FPGA、ASIC等異構(gòu)處理器上運(yùn)行時(shí)，需要有該任務(wù)在此處理器上的代碼及編譯實(shí)現(xiàn)，后文將不再?gòu)?qiáng)調(diào)。

式中：[cjCfiC]、[cjGfiG]、[cjAfiA]分別代表任務(wù)j在不同異構(gòu)芯片上的執(zhí)行時(shí)間，其中[cjC]、[cjG]、[cjA]分別表示任務(wù)j對(duì)CPU、GPU和專用計(jì)算芯片（ASIC、FPGA、NPU等）的算力需求，[fiC]、[fiG]、[fiA]分別表示計(jì)算節(jié)點(diǎn)i可以提供的計(jì)算資源算力，式中[cjGfiG]和[cjAfiA]的系數(shù)[α]和[β]根據(jù)任務(wù)的不同實(shí)現(xiàn)方案可以取0或1。

2" 在線任務(wù)調(diào)度算法

在線任務(wù)調(diào)度指的是當(dāng)一個(gè)任務(wù)到達(dá)時(shí)，根據(jù)當(dāng)前計(jì)算資源的情況，立即決定該任務(wù)應(yīng)該被調(diào)度到哪個(gè)計(jì)算節(jié)點(diǎn)上。在這個(gè)場(chǎng)景下只有一個(gè)任務(wù)等待調(diào)度，因此不需要考慮任務(wù)優(yōu)先級(jí)排序問(wèn)題，應(yīng)該重點(diǎn)關(guān)注子問(wèn)題2即任務(wù)資源匹配問(wèn)題。需要注意的是，由于這個(gè)過(guò)程是實(shí)時(shí)在線調(diào)度，調(diào)度過(guò)程本身的開(kāi)銷不可忽略，并且在邊緣計(jì)算場(chǎng)景下計(jì)算任務(wù)數(shù)量和計(jì)算節(jié)點(diǎn)數(shù)量的規(guī)模遠(yuǎn)遠(yuǎn)小于傳統(tǒng)云計(jì)算場(chǎng)景下的規(guī)模。任務(wù)調(diào)度算法本身不能太過(guò)復(fù)雜，不合適采用算法復(fù)雜度高、適合解決大規(guī)模調(diào)度問(wèn)題的群體智能搜索方法，因此，本文基于啟發(fā)式方法，設(shè)計(jì)了一種基于異構(gòu)資源匹配的在線任務(wù)調(diào)度策略。

2.1" 異構(gòu)資源匹配度

在邊緣計(jì)算系統(tǒng)中，異構(gòu)計(jì)算資源種類多樣，算力差別巨大。請(qǐng)求計(jì)算資源的任務(wù)根據(jù)其計(jì)算特性的不同，往往有針對(duì)不同加速芯片的編程實(shí)現(xiàn)，這也造成了任務(wù)對(duì)于資源的需求各不相同，情況往往比較復(fù)雜。因此，本文引入了異構(gòu)資源匹配度的概念，評(píng)估任務(wù)和異構(gòu)資源的匹配程度并融合于經(jīng)典任務(wù)調(diào)度算法，可以使任務(wù)調(diào)度算法更加適應(yīng)邊緣計(jì)算異構(gòu)資源場(chǎng)景。

異構(gòu)資源匹配度指標(biāo)從任務(wù)角度和資源角度出發(fā)，分析任務(wù)對(duì)異構(gòu)資源的需求并計(jì)算節(jié)點(diǎn)中異構(gòu)資源的算力性能，評(píng)估任務(wù)和異構(gòu)資源的匹配度。根據(jù)第1節(jié)任務(wù)調(diào)度模型，定義任務(wù)j對(duì)于異構(gòu)資源節(jié)點(diǎn)i的匹配度Sji為：

式中：Eji描述了任務(wù)j在計(jì)算節(jié)點(diǎn)i上的時(shí)延匹配度；Bji描述了任務(wù)j分配到計(jì)算節(jié)點(diǎn)i上的負(fù)載均衡匹配度；[w1]和[w2]代表時(shí)延匹配度和負(fù)載均衡匹配度的權(quán)重系數(shù)，滿足[w1+w2=1]的約束條件，當(dāng)邊緣計(jì)算場(chǎng)景和任務(wù)調(diào)度優(yōu)化指標(biāo)發(fā)生變化時(shí)，可根據(jù)需求對(duì)異構(gòu)資源匹配度的權(quán)重進(jìn)行調(diào)整，也可以增加新的匹配指標(biāo)共同組成異構(gòu)資源匹配度。當(dāng)節(jié)點(diǎn)資源滿足任務(wù)需求（Rik·（1-pik）≥Tjk）且完成時(shí)間小于等于任務(wù)最大容忍時(shí)延（Tji≤dj）時(shí)，異構(gòu)資源匹配度可由Eji和Bji計(jì)算得出；否則異構(gòu)資源匹配度為0。下面分別對(duì)Eji和Bji進(jìn)行詳細(xì)說(shuō)明。

時(shí)延匹配度Eji描述了任務(wù)j在計(jì)算節(jié)點(diǎn)i上的完成時(shí)間匹配情況，當(dāng)計(jì)算節(jié)點(diǎn)資源和任務(wù)更加匹配時(shí)，任務(wù)在該計(jì)算節(jié)點(diǎn)上的計(jì)算效率往往更高，任務(wù)完成時(shí)間更少。時(shí)延匹配度Eji的計(jì)算方法如式（12）所示，此時(shí)的任務(wù)完成時(shí)間小于等于任務(wù)最大容忍時(shí)延（tji≤dj）。根據(jù)tji和dj之間的比例關(guān)系進(jìn)行歸一化，時(shí)延匹配度Eji取0.5～1（考慮到當(dāng)tji=dj時(shí)，節(jié)點(diǎn)可以滿足任務(wù)時(shí)延需求，因此時(shí)延匹配度不為0）。需注意的是，當(dāng)計(jì)算節(jié)點(diǎn)i包含多個(gè)異構(gòu)芯片，計(jì)算資源同時(shí)滿足任務(wù)j的優(yōu)選方案、次選方案、備選方案中的兩種及以上時(shí)，默認(rèn)選用優(yōu)選方案下的任務(wù)完成時(shí)間計(jì)算時(shí)延匹配度。

負(fù)載均衡匹配度Bji描述了任務(wù)j與計(jì)算節(jié)點(diǎn)i在對(duì)負(fù)載均衡要求的匹配情況。計(jì)算節(jié)點(diǎn)往往由多個(gè)異構(gòu)芯片共同構(gòu)成，在運(yùn)行過(guò)程中，這些異構(gòu)芯片的利用率各不相同，當(dāng)計(jì)算節(jié)點(diǎn)某芯片資源利用率處于較高水平，而其他芯片資源利用率很低時(shí)，容易使得剩余資源難以被單獨(dú)分配，就會(huì)有很多資源碎片，導(dǎo)致資源浪費(fèi)。負(fù)載均衡就是為了讓異構(gòu)資源的利用率處于均衡狀態(tài)，盡量減少資源碎片，從而提升計(jì)算資源整體利用率。負(fù)載均衡匹配度Bji的計(jì)算方法如式（13）所示。

式中：[δi]為計(jì)算節(jié)點(diǎn)i的資源利用率方差，可由第k個(gè)資源的利用率pik和平均資源利用率[pi]計(jì)算得出；[δ′ij]為任務(wù)j分配到計(jì)算節(jié)點(diǎn)i后的預(yù)期資源利用率方差，可由第k個(gè)資源的預(yù)期利用率[p′jk]和預(yù)期平均資源利用率[p′j]計(jì)算得出。當(dāng)[δigt;δ′ij]時(shí)，表明任務(wù)分配后，計(jì)算節(jié)點(diǎn)的資源利用率方差減小，負(fù)載更加均衡，Bji取值0～1之間；當(dāng)[δi≤δ′ij]時(shí)，表明任務(wù)分配后，負(fù)載均衡程度變差，則匹配度取0。負(fù)載均衡匹配度的計(jì)算要求任務(wù)調(diào)度算法可以實(shí)時(shí)感知各計(jì)算節(jié)點(diǎn)的資源利用率情況。

通過(guò)時(shí)延匹配度和負(fù)載均衡度匹配共同組成異構(gòu)資源匹配度的概念，用于評(píng)估任務(wù)和異構(gòu)資源的匹配程度，在調(diào)度過(guò)程中給任務(wù)選擇更加匹配的計(jì)算節(jié)點(diǎn)。

2.2" 算法流程

本文設(shè)計(jì)的基于異構(gòu)資源匹配的在線任務(wù)調(diào)度算法的核心思想是：根據(jù)任務(wù)對(duì)計(jì)算資源的需求和計(jì)算節(jié)點(diǎn)的算力性能進(jìn)行分析，并引入了異構(gòu)資源匹配度的概念來(lái)評(píng)估任務(wù)和異構(gòu)資源的匹配程度，從而實(shí)現(xiàn)邊緣計(jì)算異構(gòu)資源場(chǎng)景下在線任務(wù)的合理調(diào)度。在線任務(wù)調(diào)度算法流程如圖2所示。當(dāng)有一個(gè)任務(wù)到達(dá)任務(wù)調(diào)度節(jié)點(diǎn)時(shí)，算法首先會(huì)對(duì)任務(wù)和計(jì)算節(jié)點(diǎn)的數(shù)據(jù)模型進(jìn)行初始化；然后遍歷系統(tǒng)中所有邊緣計(jì)算節(jié)點(diǎn)，計(jì)算異構(gòu)資源匹配度；等待遍歷完成后，算法選擇具有最大資源匹配度的節(jié)點(diǎn)，并將任務(wù)調(diào)度至該節(jié)點(diǎn)執(zhí)行計(jì)算。該問(wèn)題實(shí)際上是一個(gè)多因素優(yōu)化問(wèn)題，需要在資源受限的條件下求解任務(wù)調(diào)度時(shí)延和負(fù)載均衡的最優(yōu)解。由于邊緣計(jì)算場(chǎng)景下計(jì)算任務(wù)數(shù)量和計(jì)算節(jié)點(diǎn)數(shù)量的規(guī)模有限，因此解空間有限，本文算法可以簡(jiǎn)單高效地完成任務(wù)調(diào)度。

在對(duì)計(jì)算節(jié)點(diǎn)進(jìn)行遍歷的過(guò)程中，首先判斷節(jié)點(diǎn)資源是否滿足任務(wù)需求[Rik·（1-pik）≥T1k]，若不滿足，則異構(gòu)資源匹配度[S1i]為0；若滿足條件，則計(jì)算任務(wù)完成時(shí)間[t1i]，并判斷是否滿足任務(wù)時(shí)延需求（[t1i≤d1]）。若不滿足，則異構(gòu)資源匹配度[S1i]為0；若滿足則分別計(jì)算時(shí)延匹配度[E1i]和負(fù)載均衡匹配度[B1i]，求解最終異構(gòu)資源匹配度[S1i]。

在線任務(wù)調(diào)度算法步驟如下。

輸入：

Tj：當(dāng)前待調(diào)度任務(wù)資源需求模型

dj：任務(wù)最大容忍時(shí)延

dataj：任務(wù)數(shù)據(jù)量大小

i：當(dāng)前計(jì)算節(jié)點(diǎn)集合

bwi：計(jì)算節(jié)點(diǎn)帶寬

pik：計(jì)算節(jié)點(diǎn)資源利用率

輸出：

Rmax：匹配度最高的計(jì)算節(jié)點(diǎn)

1.for each node i do

2.if all [Rik·（1-pik）≥Tjk] then" " " " " " " " " " //資源是否滿足

3.tji←get Finish Time（Tj，dataj，Ri，bwi） //計(jì)算任務(wù)完成時(shí)間

4.if tjigt;dj then " " " " " " " " " " "http://是否滿足容忍時(shí)延

5.Sji=0

6.continue

7.else

8.Eji←1-0.5[tjidj] " " " " " " " " " " " " " " " "http://計(jì)算時(shí)延匹配度

9.Bji←get Blance Matching Degree（[pik]）" " " " " " "http://均衡匹配度

10.Sji←[w1Eji+w2Bji] " " " " " " " " "http://異構(gòu)資源匹配度

11.end if

12.else

13.Sji=0

14.continue

15.end if

16.end for

17.return Rmax←get Max Value（Sji）

3" 實(shí)驗(yàn)與分析

為了對(duì)任務(wù)調(diào)度算法進(jìn)行仿真和評(píng)估，本節(jié)對(duì)任務(wù)調(diào)度仿真工具和仿真環(huán)境配置進(jìn)行了研究，并在此基礎(chǔ)上進(jìn)行了仿真實(shí)驗(yàn)和結(jié)果分析。

3.1" 實(shí)驗(yàn)配置

為了讓仿真環(huán)境更加貼合邊緣計(jì)算中異構(gòu)計(jì)算資源的任務(wù)調(diào)度場(chǎng)景，針對(duì)傳統(tǒng)仿真工具未考慮異構(gòu)計(jì)算資源的問(wèn)題，本文基于數(shù)據(jù)中心作業(yè)調(diào)度仿真框架CloudSimPy[10]進(jìn)行擴(kuò)展，設(shè)計(jì)了異構(gòu)資源任務(wù)調(diào)度仿真框架，用于邊緣計(jì)算環(huán)境中異構(gòu)資源任務(wù)調(diào)度算法的仿真與評(píng)估，整體架構(gòu)圖如圖3所示。

異構(gòu)資源任務(wù)調(diào)度的仿真流程為：

1） Scripts主程序創(chuàng)建計(jì)算節(jié)點(diǎn)集群，讀取任務(wù)集合及參數(shù)信息，加載調(diào)度算法，調(diào)用Core包各模塊進(jìn)行仿真；

2） Scheduler根據(jù)任務(wù)信息和資源信息做出任務(wù)調(diào)度決策；

3） Broker根據(jù)Scheduler將指定的Task提交至Cluster；

4） Cluster根據(jù)Scheduler將Task分配給指定的Machine；

5） Machine根據(jù)任務(wù)信息分配計(jì)算資源和通信資源，執(zhí)行Task；

6） 循環(huán)步驟2）～步驟5），直至任務(wù)集合調(diào)度完成。

Monitor負(fù)責(zé)輸出仿真過(guò)程中各節(jié)點(diǎn)資源的實(shí)時(shí)監(jiān)控信息，Scripts負(fù)責(zé)輸出任務(wù)調(diào)度過(guò)程信息。

邊緣集群包括8個(gè)異構(gòu)計(jì)算節(jié)點(diǎn)，采用具有代表性、性能和架構(gòu)各異的芯片，詳細(xì)算力參數(shù)根據(jù)芯片官方手冊(cè)或相關(guān)文獻(xiàn)得出[11]。計(jì)算節(jié)點(diǎn)如表1所示，共配置了4個(gè)CPU節(jié)點(diǎn)、2個(gè)CPU+GPU異構(gòu)節(jié)點(diǎn)、2個(gè)CPU+FPGA異構(gòu)節(jié)點(diǎn)，這8個(gè)計(jì)算節(jié)點(diǎn)共同構(gòu)成了當(dāng)前邊緣計(jì)算環(huán)境的異構(gòu)資源。該仿真環(huán)境包含了CPU、GPU、FPGA等計(jì)算資源，且性能差異較大，滿足本文研究的場(chǎng)景。

任務(wù)集合參數(shù)配置則以目前流行的深度學(xué)習(xí)應(yīng)用為例，這類任務(wù)往往需要高性能算力支持，難以在算力較弱的邊緣設(shè)備本地運(yùn)行。在仿真中對(duì)任務(wù)運(yùn)算量的估計(jì)采用文獻(xiàn)[11]方法，常見(jiàn)邊緣計(jì)算任務(wù)計(jì)算量如表2所示，其中神經(jīng)網(wǎng)絡(luò)的計(jì)算量采用乘加運(yùn)算次數(shù)（Multiply?ACCumulate operation， MACC）來(lái)度量。仿真任務(wù)在實(shí)現(xiàn)異構(gòu)處理器上的多種不同方案時(shí)，針對(duì)通用芯片（浮點(diǎn)數(shù)實(shí)現(xiàn)）和專用芯片（定點(diǎn)數(shù)實(shí)現(xiàn)）采用了不同算力指標(biāo)。對(duì)通用芯片采用的浮點(diǎn)數(shù)運(yùn)算[12]來(lái)說(shuō)，1 MACC約為2 FLOPS；對(duì)專用芯片采用的定點(diǎn)數(shù)運(yùn)算[13]來(lái)說(shuō)，1 MACC約為2 OPS。對(duì)任務(wù)來(lái)說(shuō)，當(dāng)一個(gè)任務(wù)有異構(gòu)芯片加速實(shí)現(xiàn)方法時(shí)，一般傾向于將任務(wù)的少部分計(jì)算量（邏輯控制部分）分配給CPU，大部分計(jì)算量（并行運(yùn)算部分）分配給GPU/FPGA。

據(jù)此并參考表2中的數(shù)據(jù)，仿真中采用了5類不同的任務(wù)來(lái)生成仿真環(huán)境下的任務(wù)集合數(shù)據(jù)集，如表3所示。

3.2" 實(shí)驗(yàn)結(jié)果與分析

本節(jié)主要對(duì)設(shè)計(jì)的在線任務(wù)調(diào)度算法和批處理任務(wù)調(diào)度算法進(jìn)行了仿真和評(píng)估，對(duì)比算法選擇了典型的隨機(jī)算法、RR算法、FirstFit算法和MCT算法，主要關(guān)注算法在任務(wù)時(shí)延和資源負(fù)載均衡指標(biāo)方面的表現(xiàn)，分別對(duì)應(yīng)任務(wù)平均響應(yīng)時(shí)間和計(jì)算節(jié)點(diǎn)異構(gòu)資源利用率方差。

將邊緣計(jì)算任務(wù)集合中任務(wù)數(shù)量分別設(shè)置為50、100，任務(wù)到達(dá)時(shí)間在0～10 s內(nèi)且服從泊松分布。根據(jù)任務(wù)集合中異構(gòu)任務(wù)的數(shù)量占比，分為異構(gòu)任務(wù)多（80%的任務(wù)有異構(gòu)芯片需求）、異構(gòu)任務(wù)少（20%的任務(wù)有異構(gòu)芯片需求）、均衡三種情況，并分別生成對(duì)應(yīng)的任務(wù)集合進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)過(guò)程中分別對(duì)5個(gè)不同調(diào)度算法的兩個(gè)指標(biāo)進(jìn)行了測(cè)量，包括平均響應(yīng)時(shí)間和節(jié)點(diǎn)異構(gòu)資源負(fù)載均衡，實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

平均響應(yīng)時(shí)間指的是從提交任務(wù)到任務(wù)完成花費(fèi)時(shí)間的平均值，該指標(biāo)是在線任務(wù)調(diào)度中最關(guān)鍵的指標(biāo)之一。圖4對(duì)比了仿真系統(tǒng)分別采用5種不同的在線任務(wù)調(diào)度算法時(shí)，任務(wù)平均響應(yīng)時(shí)間的表現(xiàn)情況。當(dāng)任務(wù)數(shù)量不同或異構(gòu)任務(wù)占比不同時(shí)，可以明顯看出：MCT算法表現(xiàn)最佳，這是因?yàn)镸CT算法只考慮了單個(gè)任務(wù)完成所需時(shí)間作為參數(shù)；本文設(shè)計(jì)的基于異構(gòu)資源匹配度的在線調(diào)度算法與MCT算法表現(xiàn)相近；而隨機(jī)算法、RR算法和FirstFit算法因?yàn)椴](méi)有考慮到異構(gòu)資源的性能差異對(duì)任務(wù)完成時(shí)間造成的影響，因此平均響應(yīng)時(shí)間較長(zhǎng)。

節(jié)點(diǎn)異構(gòu)資源負(fù)載均衡指的是單個(gè)計(jì)算節(jié)點(diǎn)內(nèi)異構(gòu)資源利用率的方差，方差越大，說(shuō)明計(jì)算節(jié)點(diǎn)的異構(gòu)芯片利用率越不均衡，容易存在資源碎片，從而造成浪費(fèi)；反之，則說(shuō)明該節(jié)點(diǎn)異構(gòu)芯片利用率處于均衡狀態(tài)，資源碎片較少。實(shí)驗(yàn)過(guò)程中對(duì)多個(gè)計(jì)算節(jié)點(diǎn)的異構(gòu)資源利用率方差求平均值，并計(jì)算整個(gè)調(diào)度過(guò)程中的平均值來(lái)作為負(fù)載均衡的衡量。

圖5展示了仿真系統(tǒng)分別采用5種不同的在線任務(wù)調(diào)度算法時(shí)，計(jì)算節(jié)點(diǎn)的負(fù)載均衡情況。從圖5a）可以看出，當(dāng)任務(wù)數(shù)量為50時(shí)，本文算法在三種異構(gòu)任務(wù)占比不同的情況下都取得了最優(yōu)值，并且當(dāng)異構(gòu)任務(wù)占比增多時(shí)，可以更高效地利用節(jié)點(diǎn)異構(gòu)資源，從而降低方差值。此外，圖5b）顯示了當(dāng)單位時(shí)間內(nèi)到達(dá)的任務(wù)數(shù)量增加時(shí)，本文算法同樣可以保持良好性能。綜合圖5可以看出，當(dāng)任務(wù)數(shù)量不同或異構(gòu)任務(wù)占比不同時(shí)，采用本文在線調(diào)度算法，節(jié)點(diǎn)異構(gòu)資源利用率的方差均可以達(dá)到最低，這是因?yàn)樵撍惴紤]了異構(gòu)資源負(fù)載均衡作為匹配條件之一。

在邊緣計(jì)算場(chǎng)景下，任務(wù)對(duì)于時(shí)延往往比較敏感，因此調(diào)度算法本身的時(shí)間復(fù)雜度十分重要。對(duì)于本文算法，假設(shè)有一個(gè)等待調(diào)度的任務(wù)和n個(gè)異構(gòu)計(jì)算節(jié)點(diǎn)，由前述算法1流程可知，每個(gè)機(jī)器進(jìn)行一次異構(gòu)資源匹配度的計(jì)算，一共需要n次循環(huán)，因此算法的時(shí)間復(fù)雜度為O（n）。表4展示了傳統(tǒng)算法與本文調(diào)度算法在時(shí)間復(fù)雜度上的對(duì)比。除了RR算法外，本文算法在考慮了異構(gòu)計(jì)算資源的情況下，對(duì)比其他算法并未額外增加時(shí)間復(fù)雜度。

綜上可知：本文設(shè)計(jì)的基于異構(gòu)資源匹配的在線任務(wù)調(diào)度算法在平均響應(yīng)時(shí)間方面可以達(dá)到次優(yōu)值，并且與達(dá)到最優(yōu)值的MCT算法較為接近；在節(jié)點(diǎn)異構(gòu)資源均衡方面，該算法明顯優(yōu)于其他對(duì)比算法，且未增加運(yùn)算復(fù)雜度。說(shuō)明本文算法可以在保持平均響應(yīng)時(shí)間的基礎(chǔ)上，提高任務(wù)和資源的匹配程度，減小資源碎片并提升異構(gòu)資源的利用率。

4" 結(jié)" 語(yǔ)

本文針對(duì)異構(gòu)計(jì)算資源場(chǎng)景下的在線任務(wù)調(diào)度問(wèn)題建立了數(shù)學(xué)模型，結(jié)合時(shí)延和負(fù)載均衡兩個(gè)指標(biāo)，提出了異構(gòu)資源匹配度的概念，并基于此設(shè)計(jì)調(diào)度算法。為了適配異構(gòu)計(jì)算資源場(chǎng)景，本文對(duì)任務(wù)調(diào)度仿真工具進(jìn)行了改進(jìn)，并在此基礎(chǔ)上進(jìn)行仿真，對(duì)比同類型在線任務(wù)調(diào)度算法，本文算法在保證任務(wù)總體時(shí)延的基礎(chǔ)上，有效減少了資源不均衡，提高了節(jié)點(diǎn)性能。

本文主要針對(duì)的是獨(dú)立任務(wù)，但是在實(shí)際場(chǎng)景中，存在一些計(jì)算量龐大的計(jì)算任務(wù)，單個(gè)計(jì)算節(jié)點(diǎn)無(wú)法獨(dú)立完成的情況。下一步將針對(duì)異構(gòu)計(jì)算資源的依賴任務(wù)調(diào)度方法進(jìn)行深入研究，這將涉及到任務(wù)分割、執(zhí)行順序依賴、異構(gòu)資源實(shí)現(xiàn)方法等，是一個(gè)更具挑戰(zhàn)性的問(wèn)題。

參考文獻(xiàn)

[1] 王凌，吳楚格，范文慧.邊緣計(jì)算資源分配與任務(wù)調(diào)度優(yōu)化綜述[J].系統(tǒng)仿真學(xué)報(bào)，2021，33（3）：509?520.

[2] 覃劍，石昌偉，張媛，等.邊緣視頻處理的細(xì)粒度劃分與重組部署算法[J].電子學(xué)報(bào)，2021，49（11）：2152?2159.

[3] GRANDL R， ANANTHANARAYANAN G， KANDULA S， et al. Multi?resource packing for cluster schedulers [J]. ACM SIGCOMM computer communication review， 2014， 44（4）： 455?466.

[4] TAN H， HAN Z， LI X Y， et al. Online job dispatching and scheduling in edge?clouds [C]// IEEE Conference on Computer Communications. Atlanta， Georgia， USA： IEEE， 2017： 1?9.

[5] MENG J， TAN H， LI X Y， et al. Online deadline?aware task dispatching and scheduling in edge computing [J]. IEEE transactions on parallel and distributed systems， 2020， 31（6）： 1270?1286.

[6] CHOUDHARI T， MOH M， MOH T S. Prioritized task scheduling in fog computing [C]// Proceedings of the ACMSE 2018 Conference. Richmond， Kentucky， USA： ACM， 2018： 1?8.

[7] HAN S. Efficient methods and hardware for deep learning [D]. San Francisco： Stanford University， 2017.

[8] MENG J， TAN H， XU C， et al. Dedas： online task dispatching and scheduling with bandwidth constraint in edge computing [C]// 2019 IEEE Conference on Computer Communications. Paris， France： IEEE， 2019： 2287?2295.

[9] KAN T， CHIANG Y， WEI H. Task offloading and resource allocation algorithm in mobile?edge computing system [C]// Wireless and Optical Communication Conference. [S.l.]： IEEE， 2018： 1?4.

[10] LI F， HU B. Deep JS： job scheduling based on deep reinforcement learning in cloud data center [C]// ICBDC’19： Proceedings of the 4th International Conference on Big Data and Computing. Guangzhou： ACM， 2019： 48?53.

[11] VéSTIAS M P. A survey of convolutional neural networks on edge with reconfigurable computing [J]. Algorithms， 2019， 12（8）： 154.

[12] SUBRAMONEY A， NAZEER K， SCH?NE M， et al. EGRU： event?based GRU for activity?sparse inference and learning [EB/OL]. [2024?07?17]. https：//arxiv.org/pdf/2206.06178v1.

[13] KUMM S T M， HARDIECK M， MOSS D B D， et al. Unrolling ternary neural networks [J]. ACM transactions on reconfigurable technology and systems， 2019， 12（4）： 22.1?22.23.

作者簡(jiǎn)介：陳" ?。?984—），男，江蘇南通人，博士，高級(jí)工程師，研究方向?yàn)橥ㄐ排c信息系統(tǒng)。

王" 欣（1998—），男，山西臨汾人，碩士研究生，研究方向?yàn)檫吘売?jì)算。

曾" 浩（1977—），男，四川瀘州人，博士，教授，研究方向?yàn)橥ㄐ排c信息系統(tǒng)。

覃" 劍（1977—），男，陜西寶雞人，博士，教授，研究方向?yàn)楦咝阅苡?jì)算。

收稿日期：2024?06?05" " " " " "修回日期：2024?07?12

基金項(xiàng)目：十四五國(guó)防預(yù)研基金（629010204）