一種新的異構多核平臺下多類型DAG調度方法

摘 要：異構多核處理器在異構環境中受限于處理器種類，只能在特定處理器上執行。現有調度方法通常使用多類型DAG（directed acyclic graph）任務模型進行模擬，但調度方法往往忽略不同核上的通信開銷，或未考慮處理器與節點的對應關系，導致調度時間開銷較大，處理器資源未充分利用，任務效率低。針對上述問題，提出了PNIF（processor-node impact factor）算法。該算法引入了兩個對節點優先級具有重大影響的比例因子，將它們加入到節點優先級的計算中從而確定任務執行順序。實驗結果表明，PNIF比PEFT、HEFT、CPOP在調度長度上分別平均提升5.902%、19.402%、25.831%，有效縮短了整體調度長度，提升了處理器資源利用率。

關鍵詞： 異構多核處理器； 多類型DAG任務； 任務調度； 影響因子； PNIF算法

中圖分類號： TP391 文獻標志碼： A 文章編號： 1001-3695（2025）02-026-0514-05

doi：10.19734/j.issn.1001-3695.2024.05.0237

Novel scheduling method for multi-type DAG on heterogeneous multi-core platforms

Zuo Junjie， Xiao Feng^’， Huang Shujuan， Shen Chao， Hao Pengtao， Chen Lei

（School of Computer Science amp; Engineering， Xi’an Technological University， Xi’an 710021， China）

Abstract：In a heterogeneous environment，heterogeneous multi-core processors are limited to processor types and can only exe-cute on specific processors.The existing scheduling methods usually use the DAG task model to simulate，but they often ignore the communication overhead on different cores，or do not consider the corresponding relationship between processors and nodes，which leads to large scheduling time overhead，underutilization of processor resources，and low task efficiency.This paper proposed PNIF（processor-node impact factor）algorithm to solve the above problems.The algorithm introduced two scale factors which had a significant impact on the priority of the node，and added them to the calculation of the node priority to determine the task execution order.Experimental results show that compared with PEFT，HEFT and CPOP，PNIF increases the schedule length by 5.902%，19.402% and 25.831% on average respectively，which effectively shortens the overall schedule length and improves the processor resource utilization.

Key words：heterogeneous multi-core processors; multi-type DAG tasks; task scheduling; factor of impact; PNIF algorithm

0 引言

隨著人工智能^［1］、云計算^［2］、自動駕駛^［3］等技術的發展，異構多核處理器因具有不同處理器特有的執行能力可以完成特定任務，使其在嵌入式設備上具有廣泛的應用。然而，嵌入式系統軟件的發展遠遠跟不上硬件發展速度，在異構多核環境下，如何充分發揮異構多核處理器的性能、如何對異構多核處理器之間的任務進行調度、如何讓任務之間進行數據交換并降低通信開銷^［4］，目前仍然是焦點問題^［5］，許多專家學者一致認為解決上述問題的關鍵點就是任務的調度算法^［6］。因為良好的任務調度算法可以降低異構多核處理器的能耗、提高處理器的利用率^［7］、減少總任務的完成時間、提高系統的整體性能^［8，9］。

當前異構計算平臺下的調度算法，通常使用有向無環圖（directed acyclic graph，DAG）任務模型。通過構建DAG任務圖，可以有效地規劃任務的執行順序和并行執行策略^{［10，11］}。而隨著對異構計算平臺研究的逐步推進，考慮到節點與處理器的對應關系，單一類型的DAG任務模型已經無法滿足用戶需求，多類型DAG任務模型目前成為充分發揮異構平臺下不同類型處理器性能的關鍵^［12］。

然而，現有異構計算平臺下的多類型DAG調度算法幾乎都未考慮各節點之間的通信開銷^［11］。但在實際的任務調度過程中，不同處理器之間的通信是一定存在的。因此，本文針對異構計算平臺下帶通信開銷的多類型DAG任務進行研究，提出了一種新的PNIF（processor-node impact factor）調度算法，該算法將考慮異構平臺下各處理器和各節點的種類及其數量之間的內在關系，以便得到更合理的任務調度順序，在縮短整體調度長度的同時，使處理器的負載更為均衡，系統利用率更高。

1 相關工作

為應對不斷上升的用戶需求，并行異構硬件體系結構已然在嵌入式實時領域中占據了主導地位。用戶任務通常以有向無環圖來表示，而最壞響應時間（WCRT）和最壞執行時間（WCET）分別表示系統在最差情況下執行完所有任務的總時間和單個任務在最壞情況下的執行時間，這些都反映了系統在任務執行過程中的響應時間，從而成為了評估DAG任務調度性能的重要指標。

Jaffe^［13］最早提出了DAG任務模型響應時間上界的概念，響應時間上界是指系統對請求作出響應的最大時間限制，但響應時間上界是一個過于悲觀的估計，具有非自我可持續性等問題。

為了解決這一問題，Topcuoglu等人^［14］使用最壞執行時間來代替WCRT（最壞執行時間是節點在處理器上可能執行的最大時間），提出了HEFT和CPOP，這兩種算法是使用廣泛的列表調度算法，HEFT使用任務的平均計算成本和平均通信成本計算任務的向上排名rank_u并將其作為優先級。任務的rank_u代表了當前任務到出口任務的期望路徑長度，從輸出任務開始通過自下而上的遞歸方式計算，rank_u值越大，任務的優先級越高。在處理器選擇階段，HEFT使用基于插入的策略選擇具有最高優先級的任務并將其分配到具有最早完成時間的處理器上。CPOP則是將向上排名rank_u與向下排名rank_d相加，根據相加得到的值進行排名，和值越大則任務優先級越高，處理器分配階段則與HEFT算法相同。

隨后，為了獲得更小的任務完成時間，許多專家在HEFT算法的基礎上提出了許多新的算法。Ilavarasan等人^［15］提出了PETS算法，該算法根據任務的級別對任務進行分組，同一分組中的任務可并行執行，執行的順序通過任務的優先級確定。Bittencourt等人^［16］提出的Lookahead算法在HEFT算法的基礎上加入了前瞻性策略，在任務分配時不僅考慮當前任務完成時間，還對后續任務的完成時間進行預測，綜合考慮獲得更優的決策，但是Lookahead算法復雜度較高。Arabnejad等人^［17］提出的PEFT算法提出了一種樂觀因子，通過樂觀因子建立樂觀成本表，預測任務的最早完成時間，以此將任務合理地分配在對應的處理器上，但計算方法較為復雜。

在通信開銷忽略不計以及DAG任務圖為計算密集型的情況下，部分專家仍堅持使用WCRT（最壞響應時間）進行研究，因為這樣可以獲得更為精確的響應時間上界。Han等人^［18］提出了兩種新的上界分析方法，提高了響應時間估計的準確性。然而，這兩種方法的時間精度仍然是悲觀的，因為它們過度考慮了不同路徑中相同類型節點的干擾。常爽爽等人^［19］提出了一種新的多類型DAG任務轉換DTF算法，在DAG重構基礎上提出一個新的最壞響應時間分析方法，分析DAG任務執行的最壞響應時間，但是該算法在判斷任務可調度性方面精確度較低，同時采用路徑作為任務調度順序的決定性因素，計算開銷較大。Xiao等人^［20］通過拆分DAG從而構造新的節點執行路徑，提出了一種新的上界響應分析方法，但整體復雜度較高。Chen等人^［21］提出了一種新的響應時間分析方法，通過劃分原子節點以充分利用處理器的空閑時間，但預處理需要的時間過多。

上述算法要么未考慮現有異構環境下節點與處理器的對應關系，要么未考慮節點間的通信開銷。因此，本文針對異構環境下的多類型DAG任務模型，提出了一種新的調度算法。該算法不再忽視節點間的通信開銷，同時根據處理器與節點的對應關系進行優先級的判定從而獲得更合理的調度順序。

2 系統模型與相關定義

2.1 處理器模型

假設異構多核平臺有N種不同類型的處理器，所有內核都可以并行執行且它們之間可進行數據通信，內核執行節點的時間單位均相同。用H={H₁，H₂，…，H_N}，H_n（n∈［1，N］）表示不同類型處理器。每種處理器內核數量不完全相同，m_k表示第n種類型處理器的內核數量，即m_k=｜H_k｜。

2.2 任務模型

本文采用多類型DAG作為任務模型，其中DAG圖中的節點為任務節點，節點有方向的邊表示任務之間的依賴關系。異構多核系統調度的任務模型可以抽象為一個四元組G={V，E，M，C}。其中，V表示DAG圖的節點集合V={V₁，V₂，…，V_m}，V_i表示任務圖中第i個節點，m=｜V｜代表初始DAG的任務數量。E表示DAG圖的邊的集合，用二維矩陣表示，e_i，j=k（e_i，j∈E）表示節點（V_i，V_j）之間存在通信值為k的有向邊。類型函數M：V→H代表DAG圖中節點與處理器內核的對應關系，每個節點都有一種類型的處理器與之相對應，例如M（V_i）=n，（n∈［1，N］）表示節點V_i只能在類型為n的處理器內核集合H_n上執行。權值函數C：V×C表示節點的最壞執行時間（WCET），C（V_i）表示節點V_i在其對應處理器內核H_n上可執行時間的最大值。如圖1所示，其中白色節點對應為H₁類型的處理器，深色節點對應為H₂類型處理器，m₁=H₁=2，m₂=H₂=1。

定義1 若存在e_i，j=1（e_i，j∈E），那么稱V_i為V_j的前驅節點，V_j為V_i的后繼節點，即V_j只能在V_i執行后才能執行。pre（V_i）和suc（V_i）分別表示V_i節點的前驅節點集合和后繼節點集合。ans（V_i）和des（V_i）表示節點V_i的祖先節點集合和子孫節點集合。

定義2 將沒有前驅的節點稱為入口節點V_enter，沒有后繼的節點稱為出口節點V_exit，為了不失一般性，設每個圖都有且只有一個入口節點和出口節點。當存在多個入口節點（出口節點）時，可以在圖中加入一個執行時間為0且通信邊權值為0的入口節點（出口節點）。

如果V_i和V_j被調度在不同的處理器核上，則邊（V_i，V_j）的通信開銷為|e_i，j|，用來表示任務之間通信開銷大小。在同一處理器核上調度的父任務與子任務之間通信開銷為0。

Trans（V_i，V_j）=0V_i→H_k and V_j→H_k

|e_i，j|others（1）

3 PNIF算法

由于不同類型處理器的數量不一定相同、不同任務節點的數量也不一定相同，同時一種處理器只能處理與自己種類相對應的任務節點，所以單純地依靠任務節點本身的WCRT進行任務排序得到的調度順序有一定的局限性。PNIF算法將不同種類的各處理器數量與系統中的處理器整體數量的比例關系、不同種類的節點數量與整體節點數量的比例關系兩者結合起來加入優先級的判定，可以獲得更合理的優先級順序。該算法分為優先級判定和處理器分配兩個階段。

3.1 優先級判定

對于多類型DAG模型，保持處理器與節點的對應關系是任務分配時的關鍵一步。因此，在本文算法中，首先對節點與所對應處理器類型進行標記：

H_i=mark（V_i）（2）

優先級判定能夠直接影響到節點的執行順序，從而影響整體任務的完成時間，考慮到多類型DAG模型中不同類型節點與不同類型處理器的對應關系，本文算法將每一類型處理器與總的處理器的比值和每一種類的節點與總的節點的比值一起加入優先級的計算以得到更合理的任務優先級。

任務通過向上遞歸計算各自優先級并按優先級大小進行排序：

rank_u（V_i）=T₁×C_i+maxv_j∈succ（v_i）（rank_u（V_j）+T₂×|e_i，j|）（3）

其中：T₁表示當前計算節點種類的個數與DAG中所有節點數量的比值;T₂表示當前計算節點對應的處理器的個數與所有處理器數量的比值。T₁與T₂能體現出多類型DAG模型中不同處理器與不同節點的內在關聯，使得到的任務優先級順序更合理，同時能使各處理器的負載更為均衡。表1是通過式（3）得出的圖1示例圖中各節點的rank_u值。

3.2 處理器分配

處理器分配階段采用基于插入的最優分配策略將節點分配到對應的處理器上。此策略的目的是為了在不破壞優先級判定階段所得到的任務隊列順序的基礎上，將節點分配在使其完成時間最小的處理器上。首先，遞歸地計算出任務在對應的某個處理器上的最早開始時間EST（V_i，H_j=mark（V_i））和最早完成時間EFT（V_i，H_j=mark（V_i））。對于最早完成時間，入口節點V_enter的計算公式為

EST（V_enter，H_j=mark（V_i））=0（4）

對于除入口節點以外的其他節點，計算公式為

EST（V_i，H_j=mark（V_i））=maxavail［j］，maxV_m∈pred（V_i）（AFT（V_m）+e_m，i）（5）

點的最早完成時間計算公式為

EFT（V_i，H_j=mark（V_i））=e_i，j+EST（V_i，H_j=mark（V_i））（6）

其中：avail［j］是處理器H_j完成上一個任務的最早時間，即可能選中的某個處理器最早的空閑時間；式（5）的目的是搜尋除入口節點外的節點在對應處理器上可開始執行的最小值；式（6）最早完成時間即最早開始時間與通信開銷的和;AFT（V_m）即是節點V_i的所有前驅節點V_m分配在對應處理器上完成執行之后的實際最早完成時間，即節點V_m最終選定的EFT（V_m，H_j=mark（V_m））中的最小值。在計算出當前節點在對應處理器上所有最早完成時間后，選取最小值，將節點分配在使其最早完成時間最小的處理器上。

算法 處理器-節點影響因子算法（PNIF算法）

輸入：DAG圖G={V，E，M，C};異構多核處理器內核。

輸出：所有節點調度結果。

a） initialize all nodes of DAG //初始化DAG節點

b） for each V_i∈G

c） if there are multiple nodes that degree is 0

d）

create a node V_enter（V_exit） with C（V）=0

e）

suc（V_entery）=V_i or pre（V_exit）=V_i

f） end if

g） calculate the rank_u（V_i） of each node from V_exit to V_enter

h） put the nodes into the list in decreasing order of rank_u value /*優先級計算階段*/

i） while （list！=NULL） do

j） take out the first node V_i in the list

k）

calculate EFT（V_i，H_j=mark（V_i）） on the all corresponding processors

l） assign V_i to the processor m_i that minimizes EFT（V_i，H_j=mark（V_i）） of V_i //處理器分配階段

m） end while

n） return所有節點調度結果

PNIF算法的流程說明如下：

算法步驟a）～f）對算法輸入的DAG任務圖規范處理，保證入口節點與出口節點的唯一性。步驟g）h）通過式（3）計算各節點的rank_u值并按遞減的順序放入隊列list中。步驟i）～m）將列表list中的節點按順序彈出，計算當前節點的EFT（V_i，H_j=mark（V_i）），將其放在使其EFT（V_i，H_j=mark（V_i））最小的處理器直到list為空，最后返回調度結果（步驟n））。時間復雜度為O（|V²|），空間復雜度為O（|V|）。

3.3 處理器模擬調度

圖2展示了圖1中DAG任務圖分別在PNIF算法與其他三種對比算法下的調度過程。其中，坐標軸中的每一小格代表WCRT中的一個時間單位，白色方框對應圖1中的白色節點，深色方框對應圖1中的深色節點。可以看出，PNIF算法的調度長度為17個時間單位，相對于PEFT和HEFT算法短2個時間單位、相對于CPOP算法短3個時間單位。本文算法相比于其他三種算法，在平衡處理器通信開銷、合理分配處理器內核、縮短整體調度長度等方面有較大優勢。

3.4 最壞響應時間分析

本文PNIF算法通過對類關鍵路徑的尋找從而改變了DAG任務模型各節點的執行順序，與現有算法相比，本文在節點的優先級判斷時，將各處理器與各節點的數量關系相結合并加入到此階段，從而獲得了更合理的執行順序，降低了任務的最壞響應時間。本文的最壞響應時間為

WCRT=max{AFT（V_i）}（7）

式（7）拆分為

WCRT=max{AFT（V_i）}=∑exitn=enterC（V_n）+E（8）

其中：C（V_enter）為入口節點的的最壞執行時間;C（V_exit）為出口節點的最壞執行時間。設各節點間可能存在的通信開銷的總和為E。

定理 DAG任務的最壞響應時間上界為R（G′），則

R（G′）≤∑exitn=enterC（V_n）+E（9）

證明 由WCRT的計算方式可知，在執行順序確定之后，DAG任務圖的最壞響應時間取決于任務的最壞執行時間和任務之間的通信開銷，由于多類型DAG任務節點的實際執行時間不會大于最壞執行時間，且任務的通信開銷是不變的，即C′（V_n）≤C（V_n）。設此時新的最壞響應時間為WCRT′，則

WCRT′≤WCRT（10）

綜上所述，在使用了PNIF算法之后，DAG任務的完成時間永遠不超過本文提出的最壞響應時間，證畢。

本文PNIF算法通過改變不同種類任務節點的調度順序，并使用基于插入的策略，在獲得更合理的調度順序的同時，充分利用了處理器可能存在的空閑時間，從而降低了任務的調度時間，獲得更為精確的任務最壞響應時間上界。

4 實驗分析

本文采用隨機生成的DAG任務圖，采用PEFT^［17］、HEFT^［14］、CPOP^［14］三種算法分別優化，與PNIF算法進行對比仿真實驗。以下是相關參數及其含義。

n：DAG任務數量，在［10，50］選取。

K：處理器類型。數量在［2，6］隨機選取，每種處理器的內核個數C_k在［2，8］隨機選取。

fat：同層DAG內節點數量上限，在n×{0.2，0.4，0.8}之中選取。

CCR：任務傳輸量與任務計算量之間的比值，在{0.1，0.5，0.8，1，2，5}之間選取。

Pr：兩個節點存在邊的概率。

U：任務的總利用率。通過UUniFast方法^［22］對所有任務節點的任務利用率進行隨機分配，U=∑V_i∈Gu（V_i），獲取所有任務節點的最壞響應時間，u（V_i）為節點V_i的利用率。任務總利用率U從［0.5，5］隨機選取，并且DAG任務所有節點的最壞執行時間之和為vol（G）=U×T，其中截止時間D≤T。

此外，根據Makespan來衡量各個算法的調度性能。

Makespan=max{AFT（V_i）}（11）

其中：AFT（V_i）表示節點V_i的最晚完成時間。

通過實驗仿真獲取各算法不同情況下的Makespan，并使用以下指標對結果進行比較分析：

a）平均執行時間（AMakespan）。為了避免偶然性，取多組數據平均值，從而獲取任務的平均執行時間。通過比較不同算法獲取的平均執行時間判斷算法的性能。

AMakespan=∑G_i∈setMakespan（G_i）|set|（12）

b）接受率（acceptance ratio，AR）。指定最壞響應時間上界判定為可調度的任務數與生成的總任務數之間的比率。接受率越高，表明該算法的最壞響應時越精確。

AR=∑G_i∈setcount（Makespan（G_i）lt;D_i）|set|（13）

其中：set為DAG任務集;Makespan（G_i）為第i個任務圖執行完成時間;D_i為當前任務圖G_i的截止日期;|set|表示當前任務集中的數據量。

c）加速比（speedup）。任務順序執行時間與Makespan的比值，可獲得當前算法對于一個任務調度的加速情況。

speedup=vol（G）Makespan（14）

其中：vol（G）表示任務順序執行的時間開銷。為防止偶然性，取多組數據平均值。

d）松弛度（slack）。slack是一個關于任務調度算法魯棒性的量度，其反映的是一個算法調度產生的任務最壞響應時間的不確定程度。slack的定義如式（15）所示。

slack=∑ni=1Makespan-enter（V_i）-exit（V_i）n（15）

其中：n為任務節點的數量;enter（V_i）表示入口節點V_enter到任務節點V_i（不包含任務V_i）最長路徑的長度;exit（v_i）表示任務節點v_i到終止節點v_exit最長路徑的長度。

本文通過改變處理器類型K的數量和DAG任務V的數量兩個參數來對比PNIF與PEFT、HEFT、CPOP三種算法的各個性能指標。

圖3通過多個性能指標展示了不同算法隨處理器類型數K的變化趨勢。具體來看：圖3（a）揭示了平均完成時間隨K變化的情況。實驗數據表明，PNIF在平均完成時間上相較于PEFT有6.529%的降幅。圖3（b）展現了接受率隨K變化的曲線。從中可以看出，隨著處理器類型的增多，各算法展示出更優的任務調度能力。圖3（c）描繪了speedup隨K變化的比較。實驗結果顯示，在不同處理器環境下，PNIF算法的speedup始終超越現有算法，與PEFT相比，提升了4.683%。圖3（d）對比了slack隨K變化的情況。隨著處理器類型數量的增加，PNIF保持了穩定的平衡狀態，并在穩定性方面高于現有算法，比PEFT提高了4.189%。

圖4細致地呈現了不同算法在任務數V變化下的性能指標趨勢。具體分析如下：圖4（a）反映了平均完成時間隨任務數V的變化情況。實驗數據揭示，PNIF在平均完成時間上比PEFT減少了5.275%。圖4（b）展示了接受率隨任務數V的演變。結果表明，隨著任務數量的增加，各算法的接受率逐步提高。圖4（c）描繪了speedup隨任務數V的變化對比。從中可以看出，PNIF的speedup超越了PEFT，增幅達到了5.962%，且在任務數量增加的情況下，PNIF能夠穩定釋放處理器性能。圖4（d）對比了slack隨任務數V的變化情況。PNIF的穩定性一直保持在良好水平，并且優于現有算法，與PEFT相比，穩定性提升了6.942%。

表2為PNIF與PEFT、HEFT、CPOP三種算法的各種對比指標結果匯總，表中每個數值均表示PNIF當前指標對于當前算法性能提升度。

通過上述數據對比可以看出，PNIF在相同情況下各個參數指標均優于對比的三種算法。PNIF相比其他算法能夠獲得優勢是因為PNIF在任務的優先級計算階段考慮了處理器與節點的內在聯系，將節點與處理器的對應關系、各自數量加入優先級計算，使得任務在執行順序方面有著極大優化，從而更合理地選擇將要執行的處理器。

5 結束語

本文研究了異構多核平臺下具有通信開銷的DAG任務調度問題，將不同處理器、不同節點之間的內在聯系融入到節點的優先級計算當中，在獲得更為合理的調度順序的同時，縮小整體的調度時間。實驗結果表明，該算法具有良好的調度性能，與現有算法相比，在各方面性能都獲得了提升，能夠充分發揮異構多核處理器的性能。未來筆者會將提出算法拓展到對多個多類型DAG任務的處理上。參考文獻：

［1］Reza M F.Machine learning enabled solutions for design and optimization challenges in networks-on-chip based multi/many-core architectures［J］.ACM Journal on Emerging Technologies in Computing Systems，2023，19（3）：1-26.

［2］陳紅華，崔翛龍，王耀杰.基于多種云環境的任務調度算法綜述［J］.計算機應用研究，2023，40（10）：2889-2895.（Chen Honghua，Cui Xiaolong，Wang Yaojie.Summary of task scheduling algorithms based on multiple cloud environments［J］.Application Research of Computers，2023，40（10）：2889-2895.）

［3］Zheng Yuchao，Li Yujie，Yang Shuo，et al.Global-PBNet：a novel point cloud registration for autonomous driving［J］.IEEE Trans on Intelligent Transportation Systems，2022，23（11）：22312-22319.

［4］Abdi A，Salimi-Badr A.ENF-S：an evolutionary-neuro-fuzzy multi-objective task scheduler for heterogeneous multi-core processors［J］.IEEE Trans on Sustainable Computing，2023，8（3）：479-491.

［5］周強.多核異構系統核間通信概要設計［J］.中國集成電路，2020，29（Z1）：59-64.（Zhou Qiang.General design of inter-processor communication in multi-processor heterogeneous system［J］.China Integer Circuit，2020，29（Z1）：59-64.）

［6］Salami B，Noori H，Naghibzadeh M.Online energy-efficient fair sche-duling for heterogeneous multi-cores considering shared resource con-tention［J］.The Journal of Supercomputing，2022，78：7729-7748.

［7］安建峰，游紅俊，趙偉勛，等.星載異構計算環境下的能耗優化任務調度［J］.上海航天（中英文），2021，38（4）：38-44.（An Jianfeng，You Hongjun，Zhao Weixun，et al.Real-time task scheduling for space-oriented computing on heterogeneous system［J］.Aerospace Shanghai（Chinese amp; English），2021，38（4）：38-44.）

［8］Wu Chuge，Wang Ling，Wang Jingjing，et al.A path relinking enhanced estimation of distribution algorithm for direct acyclic graph task scheduling problem［J］.Knowledge-Based Systems，2021，228：107255.

［9］Allaqband S F，Nazish M，Allaqband S F，et al.An efficient machine learning based CPU scheduler for heterogeneous multicore processors［J/OL］.International Journal of Information Technology.（2024-02-05）.https：//doi.org/10.1007/s41870-024-01936-5.

［10］Fan Zhichao，Hu Wei，Guo Hong，et al.An efficient scheduling algorithm for interdependent tasks in heterogeneous multi-core systems［C］//Proc of IEEE International Conference on Systems，Man，and Cybernetics.Piscataway，NJ：IEEE Press，2021：2354-2359.

［11］Rajak R，Kumar S，Prakash S，et al.A novel technique to optimize quality of service for directed acyclic graph（DAG）scheduling in cloud computing environment using heuristic approach［J］.The Journal of Supercomputing，2023，79：1956-1979.

［12］陳術山.基于異構多核處理器的任務調度策略研究［D］.西安：西安工業大學，2023.（Chen Shushan.Research on task scheduling strategy based on heterogeneous multi-core processors［D］.Xi’an：Xi’an Technological University，2023.）

［13］Jaffe J M.Bounds on the scheduling of typed task systems［J］.SIAM Journal on Computing，1980，9（3）：541551.

［14］Topcuoglu H，Hariri S，Wu Minyou.Performance-effective and low-complexity task scheduling for heterogeneous computing［J］.IEEE Trans on Parallel and Distributed Systems，2002，13（3）：260-274.

［15］Ilavarasan E，Thambidurai P，Mahilmannan R.Performance effective task scheduling algorithm for heterogeneous computing system［C］//Proc of the 4th International Symposium on Parallel and Distributed Computing.Piscataway，NJ：IEEE Press，2005：28-38.

［16］Bittencourt L F，Sakellariou R，Madeira E R M.DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm［C］//Proc of the 18th Euromicro Conference on Parallel，Distributed and Network-based Processing.Piscataway，NJ：IEEE Press，2010：27-34.

［17］Arabnejad H，Barbosa J G.List scheduling algorithm for heterogeneous systems by an optimistic cost table［J］.IEEE Trans on Parallel and Distributed Systems，2013，25（3）：682-694.

［18］Han Meiling，Guan Nan，Sun Jinghao，et al.Response time bounds for typed DAG parallel tasks on heterogeneous multi-cores［J］.IEEE Trans on Parallel and Distributed Systems，2019，30（11）：2567-2581.

［19］常爽爽，趙栩鋒，劉震宇，等.基于異構多核的多類型DAG任務的響應時間分析［J］.計算機學報，2020，43（6）：1052-1068.（Chang Shuangshuang，Zhao Xufeng，Liu Zhenyu，et al.Response time analysis of typed DAG tasks on heterogeneous multi-cores［J］.Chinese Journal of Computers，2020，43（6）：1052-1068.）

［20］Xiao Feng，Chen Shushan，Han Xingxing，et al.A new direct acyclic graph task scheduling method for heterogeneous multi-core processors［J］.Computers and Electrical Engineering，2022，104：108464.

［21］Chen Shushan，Feng Xiao，Huang Shujuan，et al.Worst-case response time analysis of multitype DAG tasks based on reconstruction［J］.IEEE Access，2022，10：93140-93154.

［22］Bini E，Buttazzo G C.Measuring the performance of schedulability tests［J］.Real-Time Systems，2005，30（1-2）：129-154.