基于資源匹配的邊緣異構集群在線任務調度

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

關鍵詞： 邊緣計算； 異構集群； 任務調度； 資源匹配； 負載均衡； 異構計算

中圖分類號： TN929.5?34； TP393.0" " " " " " " 文獻標識碼： A" " " " " " " " " " " "文章編號： 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" 引" 言

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

此外，傳統的計算核心通常采用CPU，隨著摩爾定律已逼近極限，性能提升也逐漸到達了瓶頸。為應對復雜計算場景，人們引入了GPU、FPGA、ASIC等處理器進行硬件加速，尤其在邊緣側，往往由異構計算節點共同構成邊緣服務器集群。大量異構算力資源的引入一方面能提供互為補充的計算能力，但另一方面更加提高了任務調度算法的復雜性。

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

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

上述相關研究通常聚焦在CPU、內存、通信等方面，忽略了邊緣計算場景下計算資源的異構特點。針對該問題，本文提出了異構資源匹配度指標，建立了算力、需求和匹配度模型，并基于此設計了相應的邊緣側在線任務調度算法。實驗結果表明，本文的調度算法可以綜合考慮任務時延和節點負載均衡，有效提升了邊緣集群的性能。

1" 異構集群任務調度

1.1" 問題定義

假設在某時刻，邊緣異構集群中有n個計算節點i∈{1，2，…，n}，任務調度節點接收到m個計算任務Tj（j∈{1，2，…，m}）。由于獨立任務具有原子性，不可分割，且為了避免遷移開銷，不考慮任務調度后計算節點將任務遷移至其他節點的情況，對于任務Tj來說，式（1）定義了二進制變量[xji]來表示任務Tj是否被調度至計算節點i上進行處理。

用[dj]表示任務Tj的可容忍時延，即超出該時延，無法滿足用戶的需求。本文用[tji]來表示將任務Tj分配在計算節點[i]上時的任務完成時間（包括計算時間和通信時間），則tji需滿足：

根據以上分析，任務調度問題可拆解為任務優先級調度和任務?資源匹配兩個子問題，如圖1所示。子問題1實現對任務集合T的排序，確定任務的先后順序并生成任務隊列；子問題2則是根據計算節點集合R和任務集合T的模型進行資源匹配，使資源滿足任務需求。任務調度就是對這兩個子問題進行優化研究，實現對邊緣計算資源的高效、合理利用。

1.2" 異構資源算力模型

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

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

2" 在線任務調度算法

在線任務調度指的是當一個任務到達時，根據當前計算資源的情況，立即決定該任務應該被調度到哪個計算節點上。在這個場景下只有一個任務等待調度，因此不需要考慮任務優先級排序問題，應該重點關注子問題2即任務資源匹配問題。需要注意的是，由于這個過程是實時在線調度，調度過程本身的開銷不可忽略，并且在邊緣計算場景下計算任務數量和計算節點數量的規模遠遠小于傳統云計算場景下的規模。任務調度算法本身不能太過復雜，不合適采用算法復雜度高、適合解決大規模調度問題的群體智能搜索方法，因此，本文基于啟發式方法，設計了一種基于異構資源匹配的在線任務調度策略。

2.1" 異構資源匹配度

在邊緣計算系統中，異構計算資源種類多樣，算力差別巨大。請求計算資源的任務根據其計算特性的不同，往往有針對不同加速芯片的編程實現，這也造成了任務對于資源的需求各不相同，情況往往比較復雜。因此，本文引入了異構資源匹配度的概念，評估任務和異構資源的匹配程度并融合于經典任務調度算法，可以使任務調度算法更加適應邊緣計算異構資源場景。

異構資源匹配度指標從任務角度和資源角度出發，分析任務對異構資源的需求并計算節點中異構資源的算力性能，評估任務和異構資源的匹配度。根據第1節任務調度模型，定義任務j對于異構資源節點i的匹配度Sji為：

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

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

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

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

通過時延匹配度和負載均衡度匹配共同組成異構資源匹配度的概念，用于評估任務和異構資源的匹配程度，在調度過程中給任務選擇更加匹配的計算節點。

2.2" 算法流程

本文設計的基于異構資源匹配的在線任務調度算法的核心思想是：根據任務對計算資源的需求和計算節點的算力性能進行分析，并引入了異構資源匹配度的概念來評估任務和異構資源的匹配程度，從而實現邊緣計算異構資源場景下在線任務的合理調度。在線任務調度算法流程如圖2所示。當有一個任務到達任務調度節點時，算法首先會對任務和計算節點的數據模型進行初始化；然后遍歷系統中所有邊緣計算節點，計算異構資源匹配度；等待遍歷完成后，算法選擇具有最大資源匹配度的節點，并將任務調度至該節點執行計算。該問題實際上是一個多因素優化問題，需要在資源受限的條件下求解任務調度時延和負載均衡的最優解。由于邊緣計算場景下計算任務數量和計算節點數量的規模有限，因此解空間有限，本文算法可以簡單高效地完成任務調度。

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

在線任務調度算法步驟如下。

輸入：

Tj：當前待調度任務資源需求模型

dj：任務最大容忍時延

dataj：任務數據量大小

i：當前計算節點集合

bwi：計算節點帶寬

pik：計算節點資源利用率

輸出：

Rmax：匹配度最高的計算節點

1.for each node i do

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

3.tji←get Finish Time（Tj，dataj，Ri，bwi） //計算任務完成時間

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

5.Sji=0

6.continue

7.else

8.Eji←1-0.5[tjidj] " " " " " " " " " " " " " " " "http://計算時延匹配度

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

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

11.end if

12.else

13.Sji=0

14.continue

15.end if

16.end for

17.return Rmax←get Max Value（Sji）

3" 實驗與分析

為了對任務調度算法進行仿真和評估，本節對任務調度仿真工具和仿真環境配置進行了研究，并在此基礎上進行了仿真實驗和結果分析。

3.1" 實驗配置

為了讓仿真環境更加貼合邊緣計算中異構計算資源的任務調度場景，針對傳統仿真工具未考慮異構計算資源的問題，本文基于數據中心作業調度仿真框架CloudSimPy[10]進行擴展，設計了異構資源任務調度仿真框架，用于邊緣計算環境中異構資源任務調度算法的仿真與評估，整體架構圖如圖3所示。

異構資源任務調度的仿真流程為：

1） Scripts主程序創建計算節點集群，讀取任務集合及參數信息，加載調度算法，調用Core包各模塊進行仿真；

2） Scheduler根據任務信息和資源信息做出任務調度決策；

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

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

5） Machine根據任務信息分配計算資源和通信資源，執行Task；

6） 循環步驟2）～步驟5），直至任務集合調度完成。

Monitor負責輸出仿真過程中各節點資源的實時監控信息，Scripts負責輸出任務調度過程信息。

邊緣集群包括8個異構計算節點，采用具有代表性、性能和架構各異的芯片，詳細算力參數根據芯片官方手冊或相關文獻得出[11]。計算節點如表1所示，共配置了4個CPU節點、2個CPU+GPU異構節點、2個CPU+FPGA異構節點，這8個計算節點共同構成了當前邊緣計算環境的異構資源。該仿真環境包含了CPU、GPU、FPGA等計算資源，且性能差異較大，滿足本文研究的場景。

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

據此并參考表2中的數據，仿真中采用了5類不同的任務來生成仿真環境下的任務集合數據集，如表3所示。

3.2" 實驗結果與分析

本節主要對設計的在線任務調度算法和批處理任務調度算法進行了仿真和評估，對比算法選擇了典型的隨機算法、RR算法、FirstFit算法和MCT算法，主要關注算法在任務時延和資源負載均衡指標方面的表現，分別對應任務平均響應時間和計算節點異構資源利用率方差。

將邊緣計算任務集合中任務數量分別設置為50、100，任務到達時間在0～10 s內且服從泊松分布。根據任務集合中異構任務的數量占比，分為異構任務多（80%的任務有異構芯片需求）、異構任務少（20%的任務有異構芯片需求）、均衡三種情況，并分別生成對應的任務集合進行實驗，實驗過程中分別對5個不同調度算法的兩個指標進行了測量，包括平均響應時間和節點異構資源負載均衡，實驗結果如圖4和圖5所示。

平均響應時間指的是從提交任務到任務完成花費時間的平均值，該指標是在線任務調度中最關鍵的指標之一。圖4對比了仿真系統分別采用5種不同的在線任務調度算法時，任務平均響應時間的表現情況。當任務數量不同或異構任務占比不同時，可以明顯看出：MCT算法表現最佳，這是因為MCT算法只考慮了單個任務完成所需時間作為參數；本文設計的基于異構資源匹配度的在線調度算法與MCT算法表現相近；而隨機算法、RR算法和FirstFit算法因為并沒有考慮到異構資源的性能差異對任務完成時間造成的影響，因此平均響應時間較長。

節點異構資源負載均衡指的是單個計算節點內異構資源利用率的方差，方差越大，說明計算節點的異構芯片利用率越不均衡，容易存在資源碎片，從而造成浪費；反之，則說明該節點異構芯片利用率處于均衡狀態，資源碎片較少。實驗過程中對多個計算節點的異構資源利用率方差求平均值，并計算整個調度過程中的平均值來作為負載均衡的衡量。

圖5展示了仿真系統分別采用5種不同的在線任務調度算法時，計算節點的負載均衡情況。從圖5a）可以看出，當任務數量為50時，本文算法在三種異構任務占比不同的情況下都取得了最優值，并且當異構任務占比增多時，可以更高效地利用節點異構資源，從而降低方差值。此外，圖5b）顯示了當單位時間內到達的任務數量增加時，本文算法同樣可以保持良好性能。綜合圖5可以看出，當任務數量不同或異構任務占比不同時，采用本文在線調度算法，節點異構資源利用率的方差均可以達到最低，這是因為該算法考慮了異構資源負載均衡作為匹配條件之一。

在邊緣計算場景下，任務對于時延往往比較敏感，因此調度算法本身的時間復雜度十分重要。對于本文算法，假設有一個等待調度的任務和n個異構計算節點，由前述算法1流程可知，每個機器進行一次異構資源匹配度的計算，一共需要n次循環，因此算法的時間復雜度為O（n）。表4展示了傳統算法與本文調度算法在時間復雜度上的對比。除了RR算法外，本文算法在考慮了異構計算資源的情況下，對比其他算法并未額外增加時間復雜度。

綜上可知：本文設計的基于異構資源匹配的在線任務調度算法在平均響應時間方面可以達到次優值，并且與達到最優值的MCT算法較為接近；在節點異構資源均衡方面，該算法明顯優于其他對比算法，且未增加運算復雜度。說明本文算法可以在保持平均響應時間的基礎上，提高任務和資源的匹配程度，減小資源碎片并提升異構資源的利用率。

4" 結" 語

本文針對異構計算資源場景下的在線任務調度問題建立了數學模型，結合時延和負載均衡兩個指標，提出了異構資源匹配度的概念，并基于此設計調度算法。為了適配異構計算資源場景，本文對任務調度仿真工具進行了改進，并在此基礎上進行仿真，對比同類型在線任務調度算法，本文算法在保證任務總體時延的基礎上，有效減少了資源不均衡，提高了節點性能。

本文主要針對的是獨立任務，但是在實際場景中，存在一些計算量龐大的計算任務，單個計算節點無法獨立完成的情況。下一步將針對異構計算資源的依賴任務調度方法進行深入研究，這將涉及到任務分割、執行順序依賴、異構資源實現方法等，是一個更具挑戰性的問題。

參考文獻

[1] 王凌，吳楚格，范文慧.邊緣計算資源分配與任務調度優化綜述[J].系統仿真學報，2021，33（3）：509?520.

[2] 覃劍，石昌偉，張媛，等.邊緣視頻處理的細粒度劃分與重組部署算法[J].電子學報，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.

作者簡介：陳" 俊（1984—），男，江蘇南通人，博士，高級工程師，研究方向為通信與信息系統。

王" 欣（1998—），男，山西臨汾人，碩士研究生，研究方向為邊緣計算。

曾" 浩（1977—），男，四川瀘州人，博士，教授，研究方向為通信與信息系統。

覃" 劍（1977—），男，陜西寶雞人，博士，教授，研究方向為高性能計算。

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

基金項目：十四五國防預研基金（629010204）