一種新的異構(gòu)多核平臺(tái)下多類型DAG調(diào)度方法

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

關(guān)鍵詞： 異構(gòu)多核處理器； 多類型DAG任務(wù)； 任務(wù)調(diào)度； 影響因子； PNIF算法

中圖分類號(hào)： TP391 文獻(xiàn)標(biāo)志碼： A 文章編號(hào)： 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］、云計(jì)算^［2］、自動(dòng)駕駛^［3］等技術(shù)的發(fā)展，異構(gòu)多核處理器因具有不同處理器特有的執(zhí)行能力可以完成特定任務(wù)，使其在嵌入式設(shè)備上具有廣泛的應(yīng)用。然而，嵌入式系統(tǒng)軟件的發(fā)展遠(yuǎn)遠(yuǎn)跟不上硬件發(fā)展速度，在異構(gòu)多核環(huán)境下，如何充分發(fā)揮異構(gòu)多核處理器的性能、如何對異構(gòu)多核處理器之間的任務(wù)進(jìn)行調(diào)度、如何讓任務(wù)之間進(jìn)行數(shù)據(jù)交換并降低通信開銷^［4］，目前仍然是焦點(diǎn)問題^［5］，許多專家學(xué)者一致認(rèn)為解決上述問題的關(guān)鍵點(diǎn)就是任務(wù)的調(diào)度算法^［6］。因?yàn)榱己玫娜蝿?wù)調(diào)度算法可以降低異構(gòu)多核處理器的能耗、提高處理器的利用率^［7］、減少總?cè)蝿?wù)的完成時(shí)間、提高系統(tǒng)的整體性能^{［8，9］}。

當(dāng)前異構(gòu)計(jì)算平臺(tái)下的調(diào)度算法，通常使用有向無環(huán)圖（directed acyclic graph，DAG）任務(wù)模型。通過構(gòu)建DAG任務(wù)圖，可以有效地規(guī)劃任務(wù)的執(zhí)行順序和并行執(zhí)行策略^{［10，11］}。而隨著對異構(gòu)計(jì)算平臺(tái)研究的逐步推進(jìn)，考慮到節(jié)點(diǎn)與處理器的對應(yīng)關(guān)系，單一類型的DAG任務(wù)模型已經(jīng)無法滿足用戶需求，多類型DAG任務(wù)模型目前成為充分發(fā)揮異構(gòu)平臺(tái)下不同類型處理器性能的關(guān)鍵^［12］。

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

1 相關(guān)工作

為應(yīng)對不斷上升的用戶需求，并行異構(gòu)硬件體系結(jié)構(gòu)已然在嵌入式實(shí)時(shí)領(lǐng)域中占據(jù)了主導(dǎo)地位。用戶任務(wù)通常以有向無環(huán)圖來表示，而最壞響應(yīng)時(shí)間（WCRT）和最壞執(zhí)行時(shí)間（WCET）分別表示系統(tǒng)在最差情況下執(zhí)行完所有任務(wù)的總時(shí)間和單個(gè)任務(wù)在最壞情況下的執(zhí)行時(shí)間，這些都反映了系統(tǒng)在任務(wù)執(zhí)行過程中的響應(yīng)時(shí)間，從而成為了評估DAG任務(wù)調(diào)度性能的重要指標(biāo)。

Jaffe^［13］最早提出了DAG任務(wù)模型響應(yīng)時(shí)間上界的概念，響應(yīng)時(shí)間上界是指系統(tǒng)對請求作出響應(yīng)的最大時(shí)間限制，但響應(yīng)時(shí)間上界是一個(gè)過于悲觀的估計(jì)，具有非自我可持續(xù)性等問題。

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

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

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

上述算法要么未考慮現(xiàn)有異構(gòu)環(huán)境下節(jié)點(diǎn)與處理器的對應(yīng)關(guān)系，要么未考慮節(jié)點(diǎn)間的通信開銷。因此，本文針對異構(gòu)環(huán)境下的多類型DAG任務(wù)模型，提出了一種新的調(diào)度算法。該算法不再忽視節(jié)點(diǎn)間的通信開銷，同時(shí)根據(jù)處理器與節(jié)點(diǎn)的對應(yīng)關(guān)系進(jìn)行優(yōu)先級的判定從而獲得更合理的調(diào)度順序。

2 系統(tǒng)模型與相關(guān)定義

2.1 處理器模型

假設(shè)異構(gòu)多核平臺(tái)有N種不同類型的處理器，所有內(nèi)核都可以并行執(zhí)行且它們之間可進(jìn)行數(shù)據(jù)通信，內(nèi)核執(zhí)行節(jié)點(diǎn)的時(shí)間單位均相同。用H={H₁，H₂，…，H_N}，H_n（n∈［1，N］）表示不同類型處理器。每種處理器內(nèi)核數(shù)量不完全相同，m_k表示第n種類型處理器的內(nèi)核數(shù)量，即m_k=｜H_k｜。

2.2 任務(wù)模型

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

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

定義2 將沒有前驅(qū)的節(jié)點(diǎn)稱為入口節(jié)點(diǎn)V_enter，沒有后繼的節(jié)點(diǎn)稱為出口節(jié)點(diǎn)V_exit，為了不失一般性，設(shè)每個(gè)圖都有且只有一個(gè)入口節(jié)點(diǎn)和出口節(jié)點(diǎn)。當(dāng)存在多個(gè)入口節(jié)點(diǎn)（出口節(jié)點(diǎn)）時(shí)，可以在圖中加入一個(gè)執(zhí)行時(shí)間為0且通信邊權(quán)值為0的入口節(jié)點(diǎn)（出口節(jié)點(diǎn)）。

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

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

|e_i，j|others（1）

3 PNIF算法

由于不同類型處理器的數(shù)量不一定相同、不同任務(wù)節(jié)點(diǎn)的數(shù)量也不一定相同，同時(shí)一種處理器只能處理與自己種類相對應(yīng)的任務(wù)節(jié)點(diǎn)，所以單純地依靠任務(wù)節(jié)點(diǎn)本身的WCRT進(jìn)行任務(wù)排序得到的調(diào)度順序有一定的局限性。PNIF算法將不同種類的各處理器數(shù)量與系統(tǒng)中的處理器整體數(shù)量的比例關(guān)系、不同種類的節(jié)點(diǎn)數(shù)量與整體節(jié)點(diǎn)數(shù)量的比例關(guān)系兩者結(jié)合起來加入優(yōu)先級的判定，可以獲得更合理的優(yōu)先級順序。該算法分為優(yōu)先級判定和處理器分配兩個(gè)階段。

3.1 優(yōu)先級判定

對于多類型DAG模型，保持處理器與節(jié)點(diǎn)的對應(yīng)關(guān)系是任務(wù)分配時(shí)的關(guān)鍵一步。因此，在本文算法中，首先對節(jié)點(diǎn)與所對應(yīng)處理器類型進(jìn)行標(biāo)記：

H_i=mark（V_i）（2）

優(yōu)先級判定能夠直接影響到節(jié)點(diǎn)的執(zhí)行順序，從而影響整體任務(wù)的完成時(shí)間，考慮到多類型DAG模型中不同類型節(jié)點(diǎn)與不同類型處理器的對應(yīng)關(guān)系，本文算法將每一類型處理器與總的處理器的比值和每一種類的節(jié)點(diǎn)與總的節(jié)點(diǎn)的比值一起加入優(yōu)先級的計(jì)算以得到更合理的任務(wù)優(yōu)先級。

任務(wù)通過向上遞歸計(jì)算各自優(yōu)先級并按優(yōu)先級大小進(jìn)行排序：

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

其中：T₁表示當(dāng)前計(jì)算節(jié)點(diǎn)種類的個(gè)數(shù)與DAG中所有節(jié)點(diǎn)數(shù)量的比值;T₂表示當(dāng)前計(jì)算節(jié)點(diǎn)對應(yīng)的處理器的個(gè)數(shù)與所有處理器數(shù)量的比值。T₁與T₂能體現(xiàn)出多類型DAG模型中不同處理器與不同節(jié)點(diǎn)的內(nèi)在關(guān)聯(lián)，使得到的任務(wù)優(yōu)先級順序更合理，同時(shí)能使各處理器的負(fù)載更為均衡。表1是通過式（3）得出的圖1示例圖中各節(jié)點(diǎn)的rank_u值。

3.2 處理器分配

處理器分配階段采用基于插入的最優(yōu)分配策略將節(jié)點(diǎn)分配到對應(yīng)的處理器上。此策略的目的是為了在不破壞優(yōu)先級判定階段所得到的任務(wù)隊(duì)列順序的基礎(chǔ)上，將節(jié)點(diǎn)分配在使其完成時(shí)間最小的處理器上。首先，遞歸地計(jì)算出任務(wù)在對應(yīng)的某個(gè)處理器上的最早開始時(shí)間EST（V_i，H_j=mark（V_i））和最早完成時(shí)間EFT（V_i，H_j=mark（V_i））。對于最早完成時(shí)間，入口節(jié)點(diǎn)V_enter的計(jì)算公式為

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

對于除入口節(jié)點(diǎn)以外的其他節(jié)點(diǎn)，計(jì)算公式為

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

點(diǎn)的最早完成時(shí)間計(jì)算公式為

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

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

算法 處理器-節(jié)點(diǎn)影響因子算法（PNIF算法）

輸入：DAG圖G={V，E，M，C};異構(gòu)多核處理器內(nèi)核。

輸出：所有節(jié)點(diǎn)調(diào)度結(jié)果。

a） initialize all nodes of DAG //初始化DAG節(jié)點(diǎn)

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 /*優(yōu)先級計(jì)算階段*/

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所有節(jié)點(diǎn)調(diào)度結(jié)果

PNIF算法的流程說明如下：

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

3.3 處理器模擬調(diào)度

圖2展示了圖1中DAG任務(wù)圖分別在PNIF算法與其他三種對比算法下的調(diào)度過程。其中，坐標(biāo)軸中的每一小格代表WCRT中的一個(gè)時(shí)間單位，白色方框?qū)?yīng)圖1中的白色節(jié)點(diǎn)，深色方框?qū)?yīng)圖1中的深色節(jié)點(diǎn)?？梢钥闯觯琍NIF算法的調(diào)度長度為17個(gè)時(shí)間單位，相對于PEFT和HEFT算法短2個(gè)時(shí)間單位、相對于CPOP算法短3個(gè)時(shí)間單位。本文算法相比于其他三種算法，在平衡處理器通信開銷、合理分配處理器內(nèi)核、縮短整體調(diào)度長度等方面有較大優(yōu)勢。

3.4 最壞響應(yīng)時(shí)間分析

本文PNIF算法通過對類關(guān)鍵路徑的尋找從而改變了DAG任務(wù)模型各節(jié)點(diǎn)的執(zhí)行順序，與現(xiàn)有算法相比，本文在節(jié)點(diǎn)的優(yōu)先級判斷時(shí)，將各處理器與各節(jié)點(diǎn)的數(shù)量關(guān)系相結(jié)合并加入到此階段，從而獲得了更合理的執(zhí)行順序，降低了任務(wù)的最壞響應(yīng)時(shí)間。本文的最壞響應(yīng)時(shí)間為

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

式（7）拆分為

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

其中：C（V_enter）為入口節(jié)點(diǎn)的的最壞執(zhí)行時(shí)間;C（V_exit）為出口節(jié)點(diǎn)的最壞執(zhí)行時(shí)間。設(shè)各節(jié)點(diǎn)間可能存在的通信開銷的總和為E。

定理 DAG任務(wù)的最壞響應(yīng)時(shí)間上界為R（G′），則

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

證明 由WCRT的計(jì)算方式可知，在執(zhí)行順序確定之后，DAG任務(wù)圖的最壞響應(yīng)時(shí)間取決于任務(wù)的最壞執(zhí)行時(shí)間和任務(wù)之間的通信開銷，由于多類型DAG任務(wù)節(jié)點(diǎn)的實(shí)際執(zhí)行時(shí)間不會(huì)大于最壞執(zhí)行時(shí)間，且任務(wù)的通信開銷是不變的，即C′（V_n）≤C（V_n）。設(shè)此時(shí)新的最壞響應(yīng)時(shí)間為WCRT′，則

WCRT′≤WCRT（10）

綜上所述，在使用了PNIF算法之后，DAG任務(wù)的完成時(shí)間永遠(yuǎn)不超過本文提出的最壞響應(yīng)時(shí)間，證畢。

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

4 實(shí)驗(yàn)分析

本文采用隨機(jī)生成的DAG任務(wù)圖，采用PEFT^［17］、HEFT^［14］、CPOP^［14］三種算法分別優(yōu)化，與PNIF算法進(jìn)行對比仿真實(shí)驗(yàn)。以下是相關(guān)參數(shù)及其含義。

n：DAG任務(wù)數(shù)量，在［10，50］選取。

K：處理器類型。數(shù)量在［2，6］隨機(jī)選取，每種處理器的內(nèi)核個(gè)數(shù)C_k在［2，8］隨機(jī)選取。

fat：同層DAG內(nèi)節(jié)點(diǎn)數(shù)量上限，在n×{0.2，0.4，0.8}之中選取。

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

Pr：兩個(gè)節(jié)點(diǎn)存在邊的概率。

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

此外，根據(jù)Makespan來衡量各個(gè)算法的調(diào)度性能。

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

其中：AFT（V_i）表示節(jié)點(diǎn)V_i的最晚完成時(shí)間。

通過實(shí)驗(yàn)仿真獲取各算法不同情況下的Makespan，并使用以下指標(biāo)對結(jié)果進(jìn)行比較分析：

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

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

b）接受率（acceptance ratio，AR）。指定最壞響應(yīng)時(shí)間上界判定為可調(diào)度的任務(wù)數(shù)與生成的總?cè)蝿?wù)數(shù)之間的比率。接受率越高，表明該算法的最壞響應(yīng)時(shí)越精確。

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

其中：set為DAG任務(wù)集;Makespan（G_i）為第i個(gè)任務(wù)圖執(zhí)行完成時(shí)間;D_i為當(dāng)前任務(wù)圖G_i的截止日期;|set|表示當(dāng)前任務(wù)集中的數(shù)據(jù)量。

c）加速比（speedup）。任務(wù)順序執(zhí)行時(shí)間與Makespan的比值，可獲得當(dāng)前算法對于一個(gè)任務(wù)調(diào)度的加速情況。

speedup=vol（G）Makespan（14）

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

d）松弛度（slack）。slack是一個(gè)關(guān)于任務(wù)調(diào)度算法魯棒性的量度，其反映的是一個(gè)算法調(diào)度產(chǎn)生的任務(wù)最壞響應(yīng)時(shí)間的不確定程度。slack的定義如式（15）所示。

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

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

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

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

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

表2為PNIF與PEFT、HEFT、CPOP三種算法的各種對比指標(biāo)結(jié)果匯總，表中每個(gè)數(shù)值均表示PNIF當(dāng)前指標(biāo)對于當(dāng)前算法性能提升度。

通過上述數(shù)據(jù)對比可以看出，PNIF在相同情況下各個(gè)參數(shù)指標(biāo)均優(yōu)于對比的三種算法。PNIF相比其他算法能夠獲得優(yōu)勢是因?yàn)镻NIF在任務(wù)的優(yōu)先級計(jì)算階段考慮了處理器與節(jié)點(diǎn)的內(nèi)在聯(lián)系，將節(jié)點(diǎn)與處理器的對應(yīng)關(guān)系、各自數(shù)量加入優(yōu)先級計(jì)算，使得任務(wù)在執(zhí)行順序方面有著極大優(yōu)化，從而更合理地選擇將要執(zhí)行的處理器。

5 結(jié)束語

本文研究了異構(gòu)多核平臺(tái)下具有通信開銷的DAG任務(wù)調(diào)度問題，將不同處理器、不同節(jié)點(diǎn)之間的內(nèi)在聯(lián)系融入到節(jié)點(diǎn)的優(yōu)先級計(jì)算當(dāng)中，在獲得更為合理的調(diào)度順序的同時(shí)，縮小整體的調(diào)度時(shí)間。實(shí)驗(yàn)結(jié)果表明，該算法具有良好的調(diào)度性能，與現(xiàn)有算法相比，在各方面性能都獲得了提升，能夠充分發(fā)揮異構(gòu)多核處理器的性能。未來筆者會(huì)將提出算法拓展到對多個(gè)多類型DAG任務(wù)的處理上。參考文獻(xiàn)：

［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］陳紅華，崔翛龍，王耀杰.基于多種云環(huán)境的任務(wù)調(diào)度算法綜述［J］.計(jì)算機(jī)應(yīng)用研究，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］周強(qiáng).多核異構(gòu)系統(tǒng)核間通信概要設(shè)計(jì)［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］安建峰，游紅俊，趙偉勛，等.星載異構(gòu)計(jì)算環(huán)境下的能耗優(yōu)化任務(wù)調(diào)度［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］陳術(shù)山.基于異構(gòu)多核處理器的任務(wù)調(diào)度策略研究［D］.西安：西安工業(yè)大學(xué)，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］常爽爽，趙栩鋒，劉震宇，等.基于異構(gòu)多核的多類型DAG任務(wù)的響應(yīng)時(shí)間分析［J］.計(jì)算機(jī)學(xué)報(bào)，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，F(xiàn)eng 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.