CN106919455A - 一种基于有向无环图的主路径填充调度方法 - Google Patents

Abstract

本发明提供一种基于有向无环图的主路径填充调度方法，能够充分利用主路径子任务所在的处理器，减少对其他处理器的占用。所述方法包括：针对每个任务，根据DAG图中子任务的出入度大小选取主路径；将任务划分为并行部分和串行部分，根据任务划分结果，确定任务的最大完成时间和任务的最小完成时间；判断任务的完成截止期限是否大于等于任务的最小完成时间且小于任务的最大完成时间；若是，则计算任务可填充时间，将任务可填充时间分配给每个并行部分，得到每个并行部分可使用的时间冗余；根据得到的每个并行部分可使用的时间冗余，将每个并行部分中的某并行子任务填充到主路径子任务所在的处理器执行。本发明适用于计算机多处理器调度领域。

Description

一种基于有向无环图的主路径填充调度方法

技术领域

本发明涉及计算机调度技术领域，特别是指一种基于有向无环图的主路径填充调度方法。

背景技术

近年来，实时系统受到越来越多的关注，实时系统的基本问题就是要保证系统中的任务满足其时间要求从而保证系统的实时性。对于大量串行和并行共存的具有时序限制的任务调度来说，不仅需要关注调度结果的正确性，还需要考虑任务的执行完成时间、执行截止期限以及任务的并发执行等多种因素。

在并行计算与处理中，针对有向无环图(direct acyclic graph，DAG)来表示的并行任务在多处理机上的调度研究由来已久，如何把复杂应用程序的所有任务调度到多处理器系统，并考虑任务的完成截止期限以及并发执行等，一直是众所周知的难题。

现有技术中，对串行和并行共存的具有时序限制的任务调度来说，还不能有效的选取主路径以及满足每个任务的完成截止期限。

发明内容

本发明要解决的技术问题是提供一种基于有向无环图的主路径填充调度方法，以解决现有技术所存在的不能有效的选取主路径以及满足每个任务的完成截止期限的问题。

为解决上述技术问题，本发明实施例提供一种基于有向无环图的主路径填充调度方法，包括：

针对每个任务，根据DAG图中子任务的出入度大小选取主路径，其中，每个任务包括：至少1个子任务；

按照选取的主路径，将任务划分为并行部分和串行部分；

根据任务划分结果，确定任务的最大完成时间和任务的最小完成时间；

判断任务的完成截止期限是否大于等于任务的最小完成时间且小于任务的最大完成时间；

若是，则计算任务可填充时间，将任务可填充时间分配给每个并行部分，得到每个并行部分可使用的时间冗余；

根据得到的每个并行部分可使用的时间冗余，将每个并行部分中的某并行子任务填充到主路径子任务所在的处理器执行。

进一步地，所述针对每个任务，根据DAG图中子任务的出入度大小选取主路径包括：

针对每个任务，在DAG图中，由起始子任务到终止子任务生成路径集合；

选择路径集合中路径长度最大的路径作为待选的主路径；

计算任务中子任务的出入度；

根据计算得到的任务中子任务的出入度，按照主路径包含出入度大的子任务的原则，从待选的主路径中选择出主路径。

进一步地，所述按照主路径包含出入度大的子任务的原则，从待选的主路径中选择出主路径包括：

若出入度最大的子任务是待选的主路径所共有的子任务，则选择所述子任务。

进一步地，所述按照主路径包含出入度大的子任务的原则，从待选的主路径中选择出主路径包括：

若存在两个或两个以上出入度最大的子任务是并行的，则计算包含并行子任务的路径中所述并行子任务的父亲节点和孩子节点的出入度之和；

选择其中出入度较大的并行子任务作为主路径中的子任务；

依次比较所述待选的主路径中所有的子任务，选出出入度大的子任务并确定最终的主路径。

进一步地，所述按照选取的主路径，将任务划分为并行部分和串行部分包括：

按照选取的主路径，将任务T_i划分为并行部分和串行部分划分后任务T_i表示为：

其中，total表示任务T_i划分为串行部分和并行部分的总数，i代表任务数目，m代表并行部分任务的总数目，n代表串行部分任务的总数目，k表示式中的一个计数角标；

所述任务的最大完成时间表示为：

其中，T_max表示任务的最大完成时间。

进一步地，所述任务的最小完成时间表示为：

其中，T_min表示任务的最小完成时间。

进一步地，所述任务可填充时间表示为：

T_R＝T_D-T_min

其中，T_R表示任务可填充时间，T_D表示任务的完成截止期限，T_min表示任务的最小完成时间。

进一步地，所述将任务可填充时间分配给每个并行部分，得到每个并行部分可使用的时间冗余包括：

根据计算得到的任务可填充时间计算填充因子：

ε＝T_R/P_i

其中，ε表示填充因子，T_R表示任务可填充时间，P_i表示任务中并行部分的执行时间总和；

根据计算得到的填充因子，计算每个并行部分填充调度的执行时间：

其中，表示并行部分填充调度的执行时间；

根据计算得到的每个并行部分填充调度的执行时间，计算每个并行部分可使用的时间冗余。

进一步地，所述每个并行部分可使用的时间冗余表示为：

即：

其中，表示并行部分可使用的时间冗余。

进一步地，所述根据得到的每个并行部分可使用的时间冗余，将每个并行部分中的某并行子任务填充到主路径子任务所在的处理器执行包括：

在填充调度时，若并行部分中的并行子任务被拆分，则填充调度后，被拆分的并行部分中的并行子任务的剩余部分的执行时间为:

其中，表示被拆分的并行部分中的并行子任务的剩余部分的执行时间。

本发明的上述技术方案的有益效果如下：

上述方案中，针对每个任务，根据DAG图中子任务的出入度大小选取主路径，其中，每个任务包括：至少1个子任务；按照选取的主路径，将任务划分为并行部分和串行部分；根据任务划分结果，确定任务的最大完成时间和任务的最小完成时间；判断任务的完成截止期限是否大于等于任务的最小完成时间且小于任务的最大完成时间；若是，则计算任务可填充时间，将任务可填充时间分配给每个并行部分，得到每个并行部分可使用的时间冗余；根据得到的每个并行部分可使用的时间冗余，将每个并行部分中的某并行子任务填充到主路径子任务所在的处理器执行，从而确保每个任务在满足其完成截止期限的基础上，能够调整多处理器的并发执行情况，充分利用主路径子任务所在的处理器，减少对其他处理器的占用，使资源利用率达到最大化，本实施例适用于多处理器系统的实时调度。

附图说明

图1为本发明实施例提供的基于有向无环图的主路径填充调度方法的流程示意图；

图2为本发明实施例提供的任务T1对应的DAG示意图；

图3为本发明实施例提供的依据选取的主路径并行调度示意图；

图4为本发明实施例提供的依据选取的主路径和任务完成截止期限进行填充调度示意图；

图5(a)为本发明实施例提供的任务T2对应的DAG示意图；

图5(b)为本发明实施例提供的任务T3对应的DAG示意图；

图6为本发明实施例提供的多任务并行调度示意图；

图7为本发明实施例提供的多任务基于主路径填充调度示意图。

具体实施方式

为使本发明要解决的技术问题、技术方案和优点更加清楚，下面将结合附图及具体实施例进行详细描述。

本发明针对现有的不能有效的选取主路径以及满足每个任务的完成截止期限的问题，提供一种基于有向无环图的主路径填充调度方法。

参看图1所示，本发明实施例提供的基于有向无环图的主路径填充调度方法，包括：

S101，针对每个任务，根据DAG图中子任务的出入度大小选取主路径，其中，每个任务包括：至少1个子任务；

S102，按照选取的主路径，将任务划分为并行部分和串行部分；

S103，根据任务划分结果，确定任务的最大完成时间和任务的最小完成时间；

S104，判断任务的完成截止期限是否大于等于任务的最小完成时间且小于任务的最大完成时间；

S105，若是，则计算任务可填充时间，将任务可填充时间分配给每个并行部分，得到每个并行部分可使用的时间冗余；

S106，根据得到的每个并行部分可使用的时间冗余，将每个并行部分中的某并行子任务填充到主路径子任务所在的处理器执行。

本发明实施例所述的基于有向无环图的主路径填充调度方法，针对每个任务，根据DAG图中子任务的出入度大小选取主路径，其中，每个任务包括：至少1个子任务；按照选取的主路径，将任务划分为并行部分和串行部分；根据任务划分结果，确定任务的最大完成时间和任务的最小完成时间；判断任务的完成截止期限是否大于等于任务的最小完成时间且小于任务的最大完成时间；若是，则计算任务可填充时间，将任务可填充时间分配给每个并行部分，得到每个并行部分可使用的时间冗余；根据得到的每个并行部分可使用的时间冗余，将每个并行部分中的某并行子任务填充到主路径子任务所在的处理器执行，从而确保每个任务在满足其完成截止期限的基础上，能够调整多处理器的并发执行情况，充分利用主路径子任务所在的处理器，减少对其他处理器的占用，使资源利用率达到最大化，本实施例适用于多处理器系统的实时调度。

在前述基于有向无环图的主路径填充调度方法的具体实施方式中，进一步地，所述针对每个任务，根据DAG图中子任务的出入度大小选取主路径包括：

针对每个任务，在DAG图中，由起始子任务到终止子任务生成路径集合；

选择路径集合中路径长度最大的路径作为待选的主路径；

计算任务中子任务的出入度；

根据计算得到的任务中子任务的出入度，按照主路径包含出入度大的子任务的原则，从待选的主路径中选择出主路径。

本实施例中，所述任务为实时调度任务，每个任务包括：至少1个子任务；所述子任务包括：起始子任务、中间子任务、终止子任务；针对每个任务，在DAG图中，由起始子任务到终止子任务生成路径集合；在连接起始子任务到终止子任务的路径集合中选择最长的路径(可能存在多条路径)作为待选的主路径；计算任务中子任务的出入度；根据计算得到的任务中子任务的出入度，使主路径包含出入度大的子任务，有效的从待选的主路径中选择出唯一确定的主路径。

本实施例中，作为一可选实施例，所述按照主路径包含出入度大的子任务的原则，从待选的主路径中选择出主路径可以包括以下情况：

a、若出入度最大的子任务是待选的主路径所共有的子任务，则选择所述子任务；

b、若存在两个或两个以上出入度最大的子任务是并行的(在DAG图中表现为任务是兄弟节点)，则计算包含并行子任务的路径中所述并行子任务的父亲节点和孩子节点的出入度之和，选择其中出入度较大的并行子任务作为主路径中的子任务；依次比较所述待选的主路径中所有的子任务，选出出入度大的子任务并确定最终的主路径。

本实施例中，作为一可选实施例，所述按照选取的主路径，将任务划分为并行部分和串行部分包括：

按照选取的主路径，将任务T_i划分为并行部分和串行部分划分后任务T_i表示为：

其中，total表示任务T_i划分为串行部分和并行部分的总数，i代表任务数目T_i，m代表并行部分任务的总数目，n代表串行部分任务的总数目，k表示式 中的一个计数角标；通常情况下起始子任务和终止子任务可以被划分为串行，也可以被划分为并行，因此在式中用和表示。

本实施例中，将任务T_i划分为并行部分和串行部分后，计算在当前主路径状态下的任务完成时间。串行任务需要按照顺序依次执行，并行任务可以根据服务器的占用情况以及总体任务的执行需求选择一部分任务并行执行，另外一部分任务填充串行执行，并行任务的最短完成时间为单个任务所需的完成时间的最大值。根据上述分析，可以求出任务T_i的最大完成时间和最小完成时间。

本实施例中，最大完成时间T_max是指只使用一个处理器，所有的并行任务都做填充处理，任务T_i的最大完成时间表示为：

本实施例中，最小完成时间T_min是指所有的并行任务都被并行处理，此时并行子任务的完成时间为单个任务完成时间的最大值，任务T_i的最小完成时间表示为：

本实施例中，根据任务T_i的完成截止期限用T_D表示，若T_D≥T_max,则无论是串行处理还是并行处理，都可以在规定的任务截止时间内完成，若T_D<T_min，则不可能在规定的时间内完成调度。

本实施例中，当T_D满足：T_max>T_D≥T_min时，可以根据任务T_i的完成截止期限T_D选择部分任务并行处理；当T_D满足：T_max>T_D≥T_min时，本实施例提出了一种填充调度方式，调度的目的是使调度完成时间接近任务T_i的完成截止时间T_D的同时，尽可能高效的利用处理器资源，减少对其他处理器的占用，使资源利用率达到最大化。

本实施例中，根据求得的主路径，求出主路径完成时间为τ_i(根据上述分析，τ_i＝T_min)，τ_i对于所给出的任务T_i的完成截止时间T_D会有时间冗余，根据任务的截止完成时间和T_min，可以计算出当前主路径状态下任务完成时间的冗余时间，即：任务可填充时间T_R：

T_R＝T_D-T_min

定义所有并行部分的执行时间总和为P_i，针对任务可填充时间T_R，计算填充因子ε，ε＝T_R/P_i，其中，填充因子ε也可以称为填充比例系数，通过对每个并行部分中的并行任务填充后调度，能够使整个任务的完成时间接近于任务的完成截止时间T_D，每个并行部分填充调度的执行时间为：

其中，表示并行部分填充调度的执行时间；

每个并行部分的可使用的时间冗余为：

即：

其中，表示并行部分可使用的时间冗余。

本实施例中，根据得到的每个并行部分可使用的时间冗余，将每个并行部分中的某并行子任务填充到主路径子任务所在的处理器执行，保证主路径子任务所在的处理器在任务的完成截止期限内完成，充分利用主路径子任务所在的处理器，减少对其他处理器的占用，使资源利用率达到最大化。

本实施例中，在填充调度时，若并行部分中的并行子任务被拆分，则填充调度后，被拆分的并行部分中的并行子任务的剩余部分的执行时间为:

其中，表示被拆分的并行部分中的并行子任务的剩余部分的执行时间，表示向下取整。

为了更好地理解本实施例提供的基于有向无环图的主路径填充调度方法，对本实施例提供的基于有向无环图的主路径填充调度方法进行详细说明，如图2所示的任务T1对应的DAG图，如图2所示，任务T1有{T1₁,T1₂,T1₃,…,T1₁₀}个子任务，任务的执行时间为{2，3，2，2，2，2，2，3，2，2}；任务T1的完成截止时间T_D为16，其中{T11，T13，T14，T17}四个子任务的入度为零，是起始子任务；{T1₉，T1₁₀}的出度为零，是终止子任务。列出从起始子任务到终止子任务的所有任务路径集合：

{Path1：T1₁——>T1₂——>T1₅——>T1₈——>T1₉,

Path2：T1₁——>T1₂——>T1₅——>T1₈——>T1₁₀,

Path3：T1₁——>T1₂——>T1₅——>T1₉,

Path4：T1₁——>T1₂——>T1₆——>T1₈——>T1₉,

Path5：T1₁——>T1₂——>T1₆——>T1₈——>T1₁₀,

Path6：T1₁——>T1₂——>T1₆——>T1₁₀,

Path7：T1₁——>T1₃——>T1₈——>T1₉,

Path8：T1₃——>T1₅——>T1₈——>T1₁₀,

Path9：T1₃——>T1₅——>T1₉,

Path10：T1₄——>T1₆——>T1₈——>T1₉,

Path11：T1₄——>T1₆——>T1₈——>T1₁₀,

Path12：T1₇——>T1₉}

从上述路径集合中挑选包含子任务最多的路径{path1，path2，path4，path5}形成待选的主路径，待选的主路径中包含最大子任务数是5。图2中10个子任务的出入度分别为{1，3，1，1，4，4，1，4，3，2}，待选的主路径集中的4条路径所包含的子任务为{T1₁，T1₂，T1₅，T1₆，T1₈，T1₉，T1₁₀}，对应的出入度为{1，3，4，4，4，3，2}，比较出入度，可以得到T1₅、T1₆和T1₈是出入度最高的子任务，按照之前提到的方法来考察这几个子任务，T1₈是共有节点，所有待选的主路径都包含T1₈，因此将T1₈加入最终选择的主路径中，T1₅、T1₆为并行的兄弟节点，此时要计算包含这两个节点的路径中T1₅、T1₆的父亲节点和孩子节点出入度之和，计算结果为T1₅＝11，T1₆＝10，因此选择子任务T1₅加入最终主路径。至此，已经选择出T1₅和T1₈两个节点，待选的主路径中选择包含这两个节点的路径为path1和path2，只需要比较T1₉和T1₁₀的出入度即可得到结果，T1₉的出入度为3，T1₁₀的出入度为2，因此选择包含T1₉的路径path1：T1₁——>T1₂——>T1₅——>T1₈——>T1₉作为最终的主路径。

接下来，根据所选取的主路径计算任务T1的执行完成时间，将图2所示的DAG图划分为串行部分和并行部分， 根据主路径path1：T1₁——>T1₂——>T1₅——>T1₈——>T1₉进行完全的并行执行，τ_1min＝12；进行完全的串行执行，τ_1max＝22，满足τ_1min≤T_D<τ_1max，所以任务T1适用于使用填充调度，任务可填充时间T_R为16-12＝4，计算可并行部分执行时间总和为即P₁＝2+2+2＝6，填充因子ε＝T_R/P_i，即4/6，可将任务可填充时间分配给每个可并行部分，优选地，可以将任务可填充时间平均分配给每个可并行部分即：

填充调度前的结果如图3所示，依据上述计算结果进行填充调度后的结果如图4所示，根据求得的填充因子ε，将并行任务填充到主路径子任务所在的处理器m₁上执行，串行部分保持不变，从而使处理器m₁在任务完成截止期限T_D内完成，子任务6、7、10被填充到主路径所在的处理器上，减少了子任务6、7、10对其他几个处理器的占用。

上述例子介绍了本实施例的具体实现方法，为更好的说明本实施例相比于单一的并行调度的优越性，接下来考虑另外加入两个任务T2和T3，这两个任务的DAG图如图5(a)、5(b)所示。任务T2只有一个单一的串行任务，任务所需完成时间为15，完成截止期限T_D为16；任务T3有一个串行任务和两个并行任务，并且任务T3，是一个实时调度任务，即任务所需时间为4，完成截止期限也为4。如果这三个任务放在4个处理器上调度，如果按照传统的并行调度，调度结果如图6所示。因为T2和T3的调度是基于任务T1(完整任务)的，因此根据图3所示的T1的并行调度，任务T2只能在处理器m₃或m₄上执行，但是最早开始执行时间为2，最早完成时间为17，超出了任务的截止完成期限，如图6所示。

任务T3的串行部分T3₁可以选择在处理器m₂或m₄上执行，但是在调度完成任务T1和T2后，已经有三个处理器被占用了，所以任务T3的并行部分T3₂的最早开始时间只能在处理器m₄上，任务T3的完成时间为6，超出了实时任务所要求的截止完成时间。因此，对于这样三个任务四个处理器的情况下，并行调度是不能够满足任务的需求的。那么，如果使用本实施例中基于完成截止期限的填充调度，调度结果如图7所示，基于任务T1主路径填充调度的基础上进行调度，由于处理器的占用被降到了最低，其他处理器的空闲时间被拉长，因此在加入任务T2和T3之后，可以看到三个任务均能够在各自规定的任务截止时间内完成。

因此，采用单一的并行方式进行调度可能出现一个任务占用较多处理器资源的情况，使得其他任务的执行超出其任务完成截止期限，并且在执行后期有较多的处理器处于闲置状态，从而使所有任务总的完成时间超出完成截止期限；本实施例提出的调度方式会在满足总的完成截止期限的同时，尽可能减少对其他处理器的占用，使其他任务能有效地进行调度。随着一个数据集内多个任务所包含的并行活动数量较多时，本发明提出的基于主路径的填充调度方式会显示出较好的调度性能，能够满足各任务的截止完成期限。

以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明所述原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。

Claims (10)

1.一种基于有向无环图的主路径填充调度方法，其特征在于，包括：

针对每个任务，根据DAG图中子任务的出入度大小选取主路径，其中，每个任务包括：至少1个子任务；

按照选取的主路径，将任务划分为并行部分和串行部分；

根据任务划分结果，确定任务的最大完成时间和任务的最小完成时间；

判断任务的完成截止期限是否大于等于任务的最小完成时间且小于任务的最大完成时间；

若是，则计算任务可填充时间，将任务可填充时间分配给每个并行部分，得到每个并行部分可使用的时间冗余；

根据得到的每个并行部分可使用的时间冗余，将每个并行部分中的某并行子任务填充到主路径子任务所在的处理器执行。

2.根据权利要求1所述的基于有向无环图的主路径填充调度方法，其特征在于，所述针对每个任务，根据DAG图中子任务的出入度大小选取主路径包括：

针对每个任务，在DAG图中，由起始子任务到终止子任务生成路径集合；

选择路径集合中路径长度最大的路径作为待选的主路径；

计算任务中子任务的出入度；

根据计算得到的任务中子任务的出入度，按照主路径包含出入度大的子任务的原则，从待选的主路径中选择出主路径。

3.根据权利要求2所述的基于有向无环图的主路径填充调度方法，其特征在于，所述按照主路径包含出入度大的子任务的原则，从待选的主路径中选择出主路径包括：

若出入度最大的子任务是待选的主路径所共有的子任务，则选择所述子任务。

4.根据权利要求3所述的基于有向无环图的主路径填充调度方法，其特征在于，所述按照主路径包含出入度大的子任务的原则，从待选的主路径中选择出主路径包括：

若存在两个或两个以上出入度最大的子任务是并行的，则计算包含并行子任务的路径中所述并行子任务的父亲节点和孩子节点的出入度之和；

选择其中出入度较大的并行子任务作为主路径中的子任务；

依次比较所述待选的主路径中所有的子任务，选出出入度大的子任务并确定最终的主路径。

5.根据权利要求1所述的基于有向无环图的主路径填充调度方法，其特征在于，所述按照选取的主路径，将任务划分为并行部分和串行部分包括：

按照选取的主路径，将任务T_i划分为并行部分和串行部分划分后任务T_i表示为：

其中，total表示任务T_i划分为串行部分和并行部分的总数，i代表任务数目，m代表并行部分任务的总数目，n代表串行部分任务的总数目，k表示式 中的一个计数角标；

所述任务的最大完成时间表示为：

$T_{max}={\mathrm{\&Sigma;}}_1^{total}({\mathrm{\&Sigma;}}_{k=1}^m{P}_i^{total}+{\mathrm{\&Sigma;C}}_i^{total})$

其中，T_max表示任务的最大完成时间。

6.根据权利要求5所述的基于有向无环图的主路径填充调度方法，其特征在于，所述任务的最小完成时间表示为：

$T_{min}={\mathrm{\&Sigma;}}_1^{total}({\mathrm{maxP}}_i^{total}+{\mathrm{\&Sigma;C}}_i^{total})$

其中，T_min表示任务的最小完成时间。

7.根据权利要求1所述的基于有向无环图的主路径填充调度方法，其特征在于，所述任务可填充时间表示为：

T_R＝T_D-T_min

其中，T_R表示任务可填充时间，T_D表示任务的完成截止期限，T_min表示任务的最小完成时间。

8.根据权利要求7所述的基于有向无环图的主路径填充调度方法，其特征在于，所述将任务可填充时间分配给每个并行部分，得到每个并行部分可使用的时间冗余包括：

根据计算得到的任务可填充时间计算填充因子：

ε＝T_R/P_i

其中，ε表示填充因子，T_R表示任务可填充时间，P_i表示任务中并行部分的执行时间总和；

根据计算得到的填充因子，计算每个并行部分填充调度的执行时间：

$t_i^{total}=P_i^{total}\&times;(\mathrm{\&epsiv;}+1)$

其中，表示并行部分填充调度的执行时间；

根据计算得到的每个并行部分填充调度的执行时间，计算每个并行部分可使用的时间冗余。

9.根据权利要求8所述的基于有向无环图的主路径填充调度方法，其特征在于，所述每个并行部分可使用的时间冗余表示为：

即：

其中，表示并行部分可使用的时间冗余。

10.根据权利要求8所述的基于有向无环图的主路径填充调度方法，其特征在于，所述根据得到的每个并行部分可使用的时间冗余，将每个并行部分中的某并行子任务填充到主路径子任务所在的处理器执行包括：

在填充调度时，若并行部分中的并行子任务被拆分，则填充调度后，被拆分的并行部分中的并行子任务的剩余部分的执行时间为:

其中，表示被拆分的并行部分中的并行子任务的剩余部分的执行时间。