异构多核全局限制性可抢占并行任务可调度分析

韩美灵 孙施宁 邓庆绪

1（南京邮电大学现代邮政学院 南京 210023）

2（东北大学计算机科学与工程学院 沈阳 110819）

随着嵌入式技术的发展，云计算、边缘计算等复杂计算场景对芯片的性能要求越来越高.为了满足该应用需求，异构多核在现代计算机系统得到迅速发展.然而，向大规模异构平台迁移非常困难.软件层面的原因主要是大规模的、必要的程序并行导致软件调度的复杂度，即使在同构平台下这依然是大量学者致力研究的一个热点问题.

本文首次针对有向无环图（directed acyclic graph,DAG）并行任务模型在异构平台上进行全局固定优先级限制性可抢占的可调度性分析，所提到的异构平台由多个不同类型的处理器组成（每个类别的处理器个数大于等于1）.由于异构融合的体系结构，多种不同类型的处理器集成在同一硬件，且并行软件中某些程序片段只能在特定的处理器执行.因此，DAG 任务的某些结点可以绑定到特定的一类处理器上执行.而绑定处理器的操作，在一些主流的并行处理程序和操作系统都有对应的指令，例如：在OpenMP中可以通过proc_bind 实现线程的绑定[1]；在OpenCL中，通过clCreatCommand 可以针对特定设备创建一组命令[2]；在CUDA 中，可以通过cudaSetDevise 实现指令到目标设备的绑定[3].而对任务的如此处理可以避免任务在不同速率的处理器上迁移，减少实现难度和不必要的迁移开销.下文中，我们称绑定处理器的DAG 任务为分类DAG 任务.

在经典的调度策略中，一般忽略了任务抢占和迁移的开销.然而，可抢占调度中频繁发生的抢占所造成的开销往往比不可抢占调度高很多，需要高度重视.尤其在异构多核体系结构中，GPU 中执行的任务片段是不可抢占的，因此一些实时系统的任务存在不可抢占域（即任务执行的某个片段不允许被抢占）.因此，限制性可抢占的研究对于实时系统的任务执行是至关重要的.

关于分类DAG 任务集的调度问题，难点主要存在2 方面：1）DAG 任务内部不同结点的互相影响；2）不同DAG 任务结点间的互相影响.尤其是限制性可抢占导致优先级翻转，即低优先级任务会对高优先级任务结点的执行造成阻塞.因此，分类DAG 的某个结点的执行会受到自身其他结点的干涉、高优先级任务的干涉以及低优先级任务的阻塞.其中，自身结点的干涉已经在早期工作[4]中解决.本文重点解决高优先级任务的干涉、低优先级任务的阻塞的分析问题以及分类DAG 的最差响应时间（worst case response time,WCRT）分析，主要创新点包括3 个层面：

1）由于分类导致DAG 任务的关键路径（得到WCRT 的路径）不确定[4]，从而增加高优先级任务干涉分析的难度.结合经典的同构DAG 理论和分类DAG的特点，本文提出了分类DAG 高优先级分析方法.

2）解决了分类DAG 限制性可抢占导致的优先级翻转问题.本文将同构DAG 的低优先级任务分析方法和分类DAG 相结合，提出了分类DAG 的低优先级任务阻塞的分析方法.

3）采用文献[4]的路径抽象方法并结合高、低优先级任务的分析，提出了分类DAG 任务集的WCRT分析方法.由于高、低优先级任务干涉计算的引入，本文对文献[4]路径抽象规则进行了创新.

1 相关工作

在嵌入式实时系统中，某些任务的执行只能在规定的地方被抢占.考虑到完全可抢占和完全不可抢占的优缺点，限制性可抢占的研究非常重要.近年来关于这方面的研究也较突出.如：文献[5]的工作针对多核全局最早截止期优先限制性可抢占任务做出了分析；文献[6-7]对非并行任务在全局调度策略下进行了响应时间分析；文献[8]针对多核并行任务的限制性可抢占问题进行了分析，并根据抢占策略的不同提出了对应的分析方法并进行了比较；文献[9]针对DAG 的限制性可抢占问题进行了研究，特别是针对低优先级任务的阻塞在效率和精确度的不同上提出了不同的分析策略.然而，限制性可抢占的研究工作还未考虑到资源的限制性.随着异构体系结构的发展，资源限制性是必须要考虑和解决的问题.

资源限制性问题的研究曾经非常热门，也取得了一些研究成果，基于当时的条件这些成果考虑的任务模型相对简单.例如文献[10-13]考虑的问题是2 种处理器集合分配给2 个任务，并且一个处理器集合是另一个集合的子集等，相关研究总结在综述类文献[14-15].可以发现，现有研究的问题和本文提出的分类DAG 任务的可调度性问题存在差异.针对分类DAG 任务的可调度性研究，可查阅的文献较少，Han 等人在文献[4]中提出单个分类DAG 的响应时间分析，该文分析了单DAG 分类任务可调度性，并提出了基于路径抽象的方法进行可调度性分析.基于此研究以及并行任务分析和响应时间分析的经典理论[16-18]，Han 等人提出了基于联合策略的可调度性分析[19]和全局固定优先级可调度性分析[20].文献[21]提出的工作和本文的任务模型接近，该工作是基于分解策略提出的点到点（即计算路径中每个点的WCRT）的调度分析方法，然而该方法并未考虑资源限制的问题.就单个分类DAG 任务而言，文献[4]进行了算法对比，对比实验结果显示文献[21]算法比文献[4]算法明显消极.

本文的主要工作是基于文献[4]的理论基础，提出基于全局固定优先级的限制性可抢占调度策略的分类DAG 任务的可调度性分析方法.分类导致DAG任务的关键路径不确定，从而增加高、低优先级任务的分析难度.本文将DAG 分析的理论（基于路径的分析）和分类DAG 任务相结合，成功解决了该难题.最后，基于文献[4]的路径抽象算法，更新路径抽象规则，进行任务集的可调度性判定.

2 任务模型

2.1 任务集模型的建立

本文对由N个分类DAG 任务组成的任务集G={G1,G2,…,GN}进行可调度性分析，该任务集执行的系统由不同种类的核组成.S是核类别的集合，对于每种类型s∈S具有Ms（Ms≥1）个核用于调度.分类DAG 任务Gi=(Vi,Ei,C,γi,Ti,Di)，该元组中各个符号的定义为：

1）Vi表示Gi所有结点的集合，结点∈Vi,1 ≤j≤ni，ni为Gi的结点数；

2）Ei表示Gi所有边的集合，结点(u,v)∈Ei,v,u∈Vi；

3）C表示Gi每个结点最差执行时间（worst case execution time,WCET）的函数，表示结点的WCET；

4）γi表示Gi每个结点类型的集合，表示结点的类型；

5）Ti表示Gi相邻2 个实例的最小释放时间间隔；

6）Di表示Gi的相对截止期，即Gi在时间点ri释放一个任务实例，必须在ri+Di内完成该任务实例的执行.

例1.异构DAG 并行任务模型如图1 所示，任务执行在具有2 种类别的处理器平台，白色圈表示类别1，灰色圈表示类别2，结点旁的数值表示任务的WCET.

2.2 任务调度策略

本文中任务采用全局固定优先级限制性可抢占策略进行调度.任务按照优先级顺序排列，即如果i＜j，则Gi的优先级比Gj高.限制性可抢占是指任务的结点一旦开始执行，其执行不会被高优先级任务抢占.

本文将提出一种过量估计方法分析每个任务的WCRT 上界，从而保证任务执行的安全性.其中，任务Gi的WCRT上界表示为Ri.

Fig.1 Illustration of typed DAG taskG1图 1 分类DAG 任务G1的示意图

3 调度算法分析

本节将针对任务集G={G1,G2,…,GN}进行可调度性分析，并假设Gk是被分析任务，k=1,2,…,N.

3.1 整体分析

DAG 任务WCRT 上界分析方法多基于关键路径.同构平台下，最长路径即为关键路径[18].然而，这一结论已经不适用于分类DAG[4]，最长路径分析方法得到的WCRT 上界并不安全，增大了分类DAG 的分析难度.分类DAG 任务进行可调度性分析需要解决2 个问题：1）如何确定关键路径；2）已知关键路径，如何进行响应时间分析.为了确保分析方法的安全可靠，解决问题1）最简单的方法是枚举所有路径，后面会介绍如何解决枚举问题.针对问题2），本文基于路径进行解决.首先，假设Gk的关键路径是 πk，πk=

路径 πk的执行受到3 种不同类型的干扰：第1 种，任务内干涉Intra(πk)；第2 种，其他高优先级任务的干涉；第3 种，低优先级任务的阻塞.

由文献[4]的结论可知，路径 πk受到的任务内干涉定义为与 πk结点并行且实际干涉 πk上结点执行的同类结点工作量之和与对应的处理器个数的比值，即

其中ivs(πk,s)在文献[4]中定义为路径 πk实际受到的任务内干涉.

根据文献[9]可知，路径 πk受到的任务间干涉为路径上所有类别的高优先级任务的工作量加上低优先级任务的阻塞量之和与处理器个数总和的比值，即

其中，Ws(πk)表示高优先级任务产生的工作量之和的上界，Bs(πk)表示低优先级任务产生的工作量之和的上界.根据式（1）（2），可以得到如下结论：

证明.根据文献[9，18]，引理可证. 证毕.

关键问题是如何计算Inter(πk).Inter(πk)包括2 个部分，即高优先级任务的干涉和低优先级任务的阻塞，下面将对这2 个部分产生的工作量上界进行分析.

3.2 高优先级干涉量分析

对于高优先级任务的干涉量计算，首先要确定在某个时间窗口里高优先级任务能够产生的每个类别的工作量上界.在时间长度为x的窗口内，高优先级任务Gi产生的工作量上界表示为Wi(x)，产生类别为s的 工作量上界表示为计算过程详见引理2.

引理2.在长度为x的时间窗口内，高优先级任务Gi能够产生的类别为s的 工作量上界为

证明.引理2 能够得到证明基于2 个层面的假设：

1）当carry-in 实例（该实例在窗口之前释放，在窗口内完成）和carry-out 实例（该实例在窗口内释放，截止期在窗口外）的s类 别的工作量平均分布在所有s类核上时（如图2 所示），可以得到s类别的工作量上界.

2）假设carry-out 实例全部带入，可以得到高优先级任务的工作量上界，该假设基于假设1）.

首先，证明假设1）的正确性.该假设忽略任务的内部结构，单纯考虑长度为x的时间窗口内能够产生的工作量的最大情况.采用反证法，如果vols(Gi)的工作量分布在个 核且＜Ms，根据式（4），该设想显然不能增加窗口内的工作量，因此假设1）成立.

假设2）的证明依然采用反证法，假设carry-out带入的减少即窗口向左滑动ε=δ×vols(Gi)/Ms的长度，0 ＜δ ＜1.窗口向左滑动，会导致左边carry-in 实例长度的增加，即carry-in 实例在窗口内增加 ε的长度.而carry-in 和carry-out 实例s类的工作量是均匀分布在所有核上，所以最终的工作量总和不会发生改变，即假设2）成立.接下来证明式（4）计算的正确性.

Fig.2 worst-case scenario to maximum workload in x ofGi图 2 G i在x 窗口内产生最大工作量的最坏情况

图2 中，x的时间窗口的组成包括：长度为vols(Gi)/Ms的carry-out 实例、body 实例（释放和截止期都在窗口内的实例）个数的周期长度以及carry-in实例长度.而body 实例数量的上界为

x窗口还有carry-in 的组 成部分.而carry-in 的长度可由 α计算.根据图2，carry-in 长度不大于vols(Gi)/Ms.

综上，引理2 得证. 证毕.

根据引理2，在长度为x的时间窗口内，所有高优先级任务Gi产生的s类别的工作量上界为

3.3 低优先级阻塞分析

限制性可抢占导致优先级翻转的问题，即低优先级任务会阻塞高优先级任务的执行.当路径 πk上的某个结点可以执行时，即所有前继结点完成执行，而处理器被低优先级任务占用，从而造成对该结点的阻塞.被低优先级任务占用的处理器个数为1～Ms（少于Ms个是因为处理器被高优先级任务或者前继结点占用），最坏情况要结合的情况进行讨论.

如果i=1即该结点是源结点，最多有Ms个低优先级任务的结点阻塞其执行.如果1 ＜i≤ni，分成2 种情况进行讨论：

Fig.4 Scenario for ≠s图 4 ≠s时的情况

综上，被分析路径上的某个结点阻塞量的计算总结见引理3.

证明.根据式（6）（7），引理3 得证.

证毕.

4 分析过程

基于文献[4]提出的路径抽象算法，进行响应时间分析.

由于其他任务干涉的增加，导致文献[4]算法中元组替换的规则不再适用，需要增加新的替换规则满足增加的其他任务干涉的分析，具体见引理4.

证明.替换规则2）和3）已经在文献[4]中证明.本文只需证明规则1）的必要性.采用反证法，如果规则1）不成立，则以下2 种情况之一成立：

最终，本文提出的分析方法综合为算法1，来判定任务集的可调度性.

算法1.任务集可调度性分析算法.

算法1 针对任务集中的每个任务进行路径抽象，计算其WCRT 上界.算法1 的行③～⑫是针对每个任务Gk，从源结点开始搜索至结束结点，针对每个结点基于其前继结点的元组进行该结点的元组计算，计算出新的元组进行元组合并和替换操作，直至结束结点.结束结点所有元组中最大的R即为Gk的WCRT上界（行⑬～⑯）.如果Rk＞Dk说明该任务不可调度，直接结束计算返回整个任务集不可被调度；否则，继续分析下一个任务.如果最后1 个任务被分析完，且满足截止期的要求则整个任务集可被调度（行⑰～㉑）.

基于文献[4]，算法1 对DAG 任务每个结点的响应时间分析时增加了其他任务的干涉计算.在算法1过程中增加了新的合并和替换规则以保证最终计算的安全性.

定理1.任务集G是否可以被调度，可以由算法1 来判定.

证明.综合理论和算法1 的伪代码分析，定理1得证. 证毕.

5 实 验

本文采用仿真实验，分别从算法的准确性和效率层面进行算法的验证.对任务集的可调度性产生影响的参数包括：任务集利用率、处理器个数、任务集内任务个数、结点个数、类别数以及每个任务的并行度.首先，对这些参数设置一组默认参数，然后基于该默认参数进行对应参数实验变化的验证实验.异构平台相关的实验数据基于OpenAMP[22]项目支持的硬件平台作为基础数据，对类别数和每种类别核数量的范围进行适当地增大，观察这2 组参数对算法性能的影响.而任务集的默认参数则结合实际情况和其他DAG 任务集的相关参数进行设置.默认参数设置为：

1）异构平台上核类别的数量在[2,15]随机生成，每个类别核的数量Ms在[2,10]随机生成；每个类别s的利用率在[1,Ms/3]的范围内随机生成；

2）任务集中，任务的数量在[2,20]的范围内随机生成；

3）用UUnifast 方法[23]为每个任务的s类别分配利用率；

4）对于每一个任务，周期在[100,1 000]之内随机生成，默认每个任务的相对截止期等于周期；

5）每次随机选取1 000 个任务集分析平均性能.

对单个任务的参数进行设置，主要依据文献[4]，具体参数设置为：

1）每个DAG 任务的任务结构采用文献[24]提出的方法生成.任务的结点数在[15,30]的范围内随机生成；任意2 个结点之间是否生成边，需要随机选定；假设选定为增加该边，需进一步判定，即增加该边后并行度Pr的值满足要求，则增加边，否则不增加；Pr值在[0,1]之间随机选择，注意Pr值越大说明并行度越低，Pr值为1 则所有结点为串行.

2）采用UUnifast 方法将已分配的利用率分配给每个结点，注意利用率是按类别分配的，结点的WCET 值等于分配的利用率与周期的乘积.

算法的正确性采用接受率进行验证，接受率定义为可以被调度的任务集占所有被测试的任务集的比率.图5（a）～（f）展示的是各个参数下的接受率.其中，图5（a）～（d）是整个任务集参数对接受率的影响，图5（e）～（f）是单个任务中重要参数对接受率的影响.图5（a）中，因为利用率增大，而每个类别的处理器个数不变，使得接受率逐渐下降；图5（b）中，由于利用率固定，每个类别的处理器个数增加，从而导致接受率逐渐提升；图5（c）表明，其他参数不变的情况下，任务集中任务个数越多任务越难以调度；图5（d）表明，类别越多，相同利用率下分给每个类别的利用率就会减少，而类别的增加也会导致处理器个数增加，从而使得接受率提升；图5（e）表明，单个任务内部结点个数对接受率的影响不显著；图5（f）表明，单个任务内部并行度越高（Pr值越低）接受率越高，这是因为并行度大则并行执行的可能性增大，从而提高接受率.综上分析，实验数据符合各参数的性质和对实际任务可调度性的影响.

Fig.5 Acceptance ratio of tasks under different parameters图 5 各种参数下的任务接受率

图6（a）～（f）是对应接受率实验的各个参数下的效率实验.其中，效率趋势中的每个点是所有1 000 个参加测试的任务集的平均分析时间.注意，该时间随着分析设备硬件性能的不同会有所不同，其变化趋势可以表明与相关参数的关联性.同样地，图6（a）～（d）为与任务集相关的参数，而图6（e）（f）是和单个任务相关的参数.图6（a）（b）（d）中时间效率的变化趋势分别和图5（a）（b）（d）类似，这是因为接受率低，说明不可调度的任务集增多，在第1 次出现不可调度任务时停止对任务集的分析从而出现平均分析时间下降的现象.图6（c）的实验结果为时间效率先升高后降低.图6（c）升高趋势的原因是当任务集接受率差不多时，任务集中任务个数增多，导致平均分析时间变长；图6（c）降低趋势的原因是由于接受率降低太多.图6（e）中曲线变化表明，时间效率对任务内的结点个数是敏感的，当任务内的结点数增多时，时间效率呈增长趋势，且增长速度非常大.图6（f）中时间效率变化趋势类似于图6（c），即先增后降，当任务集都可调度时任务分析时间随并行度下降而升高，当并行度降低到一定程度时接受率下降过多，导致任务集大量开始不可调度，从而导致平均分析时间下降.

Fig.6 Efficiency under different parameters图 6 各种参数下的效率

实验结果表明，本文提出的算法具有很好的接受率且任务的平均分析时间在嵌入式实时系统离线分析时间的可接受范围内，各个参数实验数据均符合实验预期.

6 结 论

本文针对异构平台上任务执行进行资源限制即规定任务只能执行在某一类处理器上这一特殊模型，进行了基于全局固定优先级限制性可抢占调度策略的可调度性分析.首先，提出了整体的分析思路；然后，针对高优先级任务的干涉和低优先级任务的阻塞进行了分析；最后，结合最新的异构模型提出了一个整体的分析方法.实验结果表明，本文提出的算法性能良好，能够在有效时间内完成任务的分析，且任务的可调度性和各个参数的关系符合实验预期.

作者贡献声明：韩美灵提出了算法思路并撰写论文；孙施宁负责实现算法并设计了相关实验方案；邓庆绪提出研究思路并指导修改论文.