摘 要:
对分布式并行系统中有向无回路图的静态任务调度问题，以使调度长度最短为主要目标、减少资源数目为次要目标，提出了一种基于任务复制的分簇与调度算法──动态关键前驱算法DCP。DCP算法将任务复制、分簇与优先级列表方法结合起来，采用一种新的选择策略来定义待复制的重要祖先集。改进了粒度的定义，并基于该定义证明了对任意的DAG，算法的性能优于当前国外学者提出的两种先进算法。计算了经典的EZ算例，得到了比过去认为的最优解更好的解，并证明了新的解为最优解。通过与其它六个相关算法在八个算例上的比较，可看出DCP算法的优度一直是最好的，且在若干算例上得到了更优的解。还讨论了无任务复制时树型DAG的2-优度的算法。
关键词: 近似算法，任务复制，分簇，调度长度，任务粒度
1 引言
分布式同构系统中调度并行任务以最小化其完工时间的问题是任务调度问题中一个重要而经典的问题。即使资源充分多且任务允许被复制，此类问题仍是NP完全的[1]；它是研究异构环境下的任务调度问题的基础，且对于解决其他的单模项目调度问题具有参考价值，因而得到了广泛的研究。调度方法以启发式算法最具代表性[1-10]，又分为基于任务复制的调度[1-7] 、基于优先级列表的调度[8,9] 和基于簇的调度[10]三类。基于任务复制的调度算法（task-duplication-based，TDB）通常要优于基于优先级列表和基于簇的调度算法[1,11]。TDB调度算法的理论基础是采用以空间换时间的策略，通过冗余地分配任务到多个资源以减少通信开销，从而减少总的调度长度，因此与不复制任务的算法相比可生成更小的makespan。如何准确地确定应被复制的重要活动是获得较短调度的关键，TDB算法之间的主要区别也正在于其选择复制活动的策略不同。MJD算法是其中理论上最优的算法，对任意的DAG调度结果最多为最优调度的1 ' ε+倍（0' 1 ε<≤，取值与DAG的粒度相关）。
MJD算法的主要思想是拓朴顺序计算每个活动v的开始时间下界ev及其对应簇Cv，初始时簇Cv中只含活动v，然后考虑跨簇的活动中数据到达时间c大于ev且到达时间最晚的活动，若加入该活动可减少ev，则复制到v所在簇中。跨簇Cv的活动是指不在Cv中但有子活动在Cv中的活动。上述过程当m>c 时停止计算，m为不考虑跨簇的活动，将簇内活动的e值作为该活动的释放时间，根据释放时间的先后按贪心调度得到的活动v的开始时间m。得到每个活动ev和对应簇Cv后，最后反拓扑顺序访问G中的活动并构造调度。在ev的计算过程中，数据到达时间c的计算未到活动v，而是进入簇Cv中的第一个活动，这可能造成m>c而过早停止加入活动，而有些应加入簇的活动未加入，错失更小调度的机会。另外ev的值是基于对v的簇得到的，在计算ev的过程中，其祖先活动均使用其e值作为活动的开始时间，但MJD未考虑该祖先得到e值的对应簇的信息，导致对活动的实际最早可开始时间的估计不够准确。
基于以上分析，本文提出了一种基于任务复制的动态关键前驱(Dynamic Critical Predecessor, DCP) 调度算法，其首要目标为使调度长度最短，次要目标为不增加调度长度的前提下，尽量减少占用的资源。DCP算法对任意的DAG 得到了优于MJD 的性能保证：基于改进的粒度定义，对任意的DAG 可得到最多为最优解的1 + ε 倍的解，其中0 < ε ≤ 1且ε ≤ ε '。 文末通过实验说明，DCP 算法在给定算例上的求解结果一直是最优的，且在有些算例上得到了比前人更好的结果。
2 问题描述
一组有序任务组成的项目通常用加权的有向无回路图(Directed Acyclic Graph, DAG)表示，即一个包含顶点集和边集且没有回路的有向图，一般顶点表示任务，边表示任务间的通信约束。在项目调度问题中，任务也称为活动。若活动i 与活动j 间有一优先关系约束，则活动i 称为j 的前驱活动(pred)或父活动，活动 j 称为活动i 的后继活动(succ)或子活动。无父活动的活动称为开始活动或进入活动，无子活动的活动称为结束活动或退出活动。簇(clustering)是指在同一资源上执行的活动子集的映射。若同一活动可以映射至多个簇，则称其为基于复制的簇。
问题可形式化地描述为：记加权有向无回路图G(V ,E,μ ,λ )， 顶点集V = {0,1, ..., n}表示项目包含的活动集， 顶点的权iμ表示活动i 的执行时间，0 为开始活动，n 为结束活动（不失一般性，当不止一个开始活动时，可加入执行时间为0、无输入边、有到每一开始活动的通信时间为0 的输出边的哑元活动；当不止一个结束活动时，也可以类似的方法加入一哑元活动）；边集E={eij:i, j∈V;i→j}表示活动间的执行顺序限制， EV×V ，活动i 已完成，且活动i 完成时传输给活动j 的数据到达活动j 所在资源，活动j 才能开始；λij 为边i→j 的权。当活动i、j 在不同资源上执行时传输时延dij =λij ，否则dij =0。
记R={Ri:i=0,1,...,r1,r}为资源集，r 为一大的正数( r≥|V| )。记iRk 表示活动在处执行，簇为被资源所加工的活动的集合，E C 为在资源上加工的约束活动对的集合。( , 即活动i j 均在资源Rk 上执行( Rk∈R,iRk ∧ jRk )。令sti 表示活动i的开工时间，ct 表示活动的完工时间。
则在满足以下条件的前提下，要求给出和i iCk (0≤k≤r) sti (0≤i≤n) 的值，使得ctn尽可能的小：
即求结束活动完工时间最小的调度，受约束于：（1）开始活动的开始时间为0，其他时间大于等于0，活动的执行具有原子性；（2）同一项目的相邻两活动，后继活动只有在前驱活动已完成且所需要的数据已到达时才能开始；（3）同一资源上加工的活动执行时间不能重叠。
3 任务复制与分簇算法
动态关键前驱调度 (DCP) 算法主要做了以下改进：首先，在计算数据最早到达时间时不是计算到入簇的第一个活动的时间，而是计算v的最早可能开始时间（Earliest Possible Start Time）Sv。其次，放宽加入活动的条件，即只要加入该活动不会使v的最早开始时间Sv增加，则可以加入簇Cv。最后，在计算Sv时，其祖先活动含相关的分簇历史信息，在考虑跨簇的活动时，不仅考虑以活动为粒度，也考虑以簇为粒度，这样一方面可加快计算过程，一方面也更准确。
3.1 计算Sv的值
首先拓扑顺序访问G中的活动v，并计算其最早可能开始时间SV∈v。对活动v，设其祖先的S值及其对应簇均已求出，欲求Sv及对应簇Cv, 只需找到一个包含v及其部分祖先的簇就足够了, 因为如果包含的活动不是v的祖先，则从该簇中移除该活动，不会使Sv增加，只可能使其减少。
设Cv是一个含活动v及其部分祖先{1的簇，{1为跨簇C,2,...,}wwwl,2,...,}uuukv的活动。{1和的最早开始时间及{1对应的簇{已经求出。下面求 v的最早可能开始时间S,2,...,}wwwl{1,2,...,}uuuk,2,...,}uuuk,,...,}12CCCuuukv，将活动{1和的S值作为相应活动的释放时间，按就绪活动释放时间的先后顺序用贪心调度法GREEDY_SCHEDULE进行调度，得到v的最早可能开始时间S,2,...,}wwwl{1,2,...,}uuukv，并记下造成Sv不能再下降的关键活动u，称u为簇Cv的关键前驱cpred(Cv)。
然后寻找使Sv尽可能小的簇Cv：从只含活动v的簇开始，每次向簇中并入v的部分祖先集，并检查Sv是否减小。部分祖先集的选择，是考虑Cv的关键前驱u，若u为簇内的活动则停止计算，否则若u为其后继的唯一父活动，则并入对应簇Cu；否则并入u，若失败，再考虑并入对应簇Cu。若Sv开始增大，则停止计算,检查若最后一次加入的是活动，则合入该活动的对应簇，从而得到最早可能开始时间Sv及其对应簇Cv。算法1为Sv的计算过程，其中C. s表示簇中v的最早可能开始时间, C.cpred表示簇C的关键前驱，v.s表示活动v的最早可能开始时间，v.C表示活动v的对应簇，w表示最后并入簇Cv的活动。
EZ算例是DAG任务调度的经典算例[4]，如图1(a)所示，图1(b)为每个活动的S值及其对应簇，图1(c)为活动5的S值及其对应簇的计算过程。
3.2 构造调度
得到每个活动的最早可能开始时间SvV∈v及对应簇Cv后，反拓扑顺序访问DAG中的活动并构造调度。初始时，结束活动为标识活动；然后重复以下操作直到没有标识活动为止： (1) 取出并标识一个活动v并考虑其对应簇Cv，若在G中找不到一个簇包含Cv的所有活动和边，则Cv加入簇集，否则利用已有的簇，修改边的关联活动和关联簇；(2) 取消对v的标识并标识所有跨C()G?v簇的活动。然后，算法DCP对中的每个簇，匹配到不同的资源上，它们之间用跨簇的边集关联，然后按活动的最早可能开始时间S非降序排列进行调度，得到最终调度的结果。
EZ的最优解一直被认为是8.5[4]。而采用DCP算法找到了更优的解。图1(d)为对EZ算例的调度结果，调度长度为8，使用了3个资源。EZ算例与其他TDB算法的求解结果见图2，其中EZ、DSC、TDS算法的求解结果参见文献[4]，可见DCP算法生成了最好的调度，可以证明8为EZ算例的最优解。事实1. EZ算例的最优解为8.
证明: 由于活动仅当其前驱活动均已完成时才可能执行，所以在DCP的调度结果中，活动T0,T1T2,T3,T4均已在绝对最早可能开始时间被调度。
由于T0->T1->T6为EZ算例在不考虑边的权重时的最长路径，所以T6的最早开始时间不小于6，完工时间不小于7。
若T6与T1不在同一个簇中，则完工时间不小于8，故优化调度中，T6一定与T1在同一个簇中。
考虑活动T5，只有两种可能，（1）与T1、T6在一个簇中，则T5的最早可能开始时间为6，T6的最早可能完工时间为8。（2）与T1、T6不在一个簇中，则T5的最早可能开始时间为5.5，T6的最早可能完工时间为8.5。
可见8为EZ算例的最优解。证毕.
4 算法性能分析
本节从理论上分析DCP算法的性能，提出了一个改进的粒度定义，并基于该定义证明DCP算法对任意的DAG可得到优于MJD的性能。对任意的DAG， MJD算法可生成最多为最优解1 ' ε+倍的解(0' 1 ε<≤)[1]，而DCP算法可生成最多为最优解1ε+倍的解（01ε<≤，εε≤）。然后讨论了无任务复制时求解Out-tree和In-tree的1ε+优度的相似算法。
4.1 任意粒度的DAG
对PY和MJD算法，粒度是分析算法性能的一个重要参数。粒度的定义如下，设有一DAG图(,,,)GVEμλ，对活动vV∈，定义则v的粒度为12min{}MJDgvgvgv =，DAG图G的粒度为()min{()|}MJDMJDgGgvvV =∈。
本文修改了粒度的定义，使之更简洁：首先，只考虑前驱及输入的边，不考虑后继及输出的边；其次，取前驱及相应的输入边的比值中的最小值，而不是取最小前驱与最大输入边的比值。对活动，定义v的粒度为vV∈()min{,(,)}uuvgvuv Eμλ= ∈ ，DAG图G的粒度为()min{()|}gGgvv V =∈。对图1(a)中的EZ算例，；若修改T0的计算时间为4，则()()0.2MJDgGgG==(')0.75MJDgG=， 。 (')0.2gG=引理1. 对任意的DAGGVEμλ，存在01ε<≤满足()(1)/gGεε=.
证明: 在DAGGVEμλ中，,μλ均为有理数，由粒度gG的定义，gG由有理数运算得到，由有理数四则运算的封闭性，()gG也为一有理数，故一定可以写为一个分数，设()agGb=，其中，且，则。
引理2. 设v为一标识的活动，且其对应簇Cv 映射到同一资源， 则存在0 1 ε<≤满足()(1)/gGεε=?，使(1)()vopt stst v ε≤+。其中()optstv为v在最优调度时的开始时间.
证明: 由引理4，存在01ε<≤满足()(1)/gGεε=。下面证明(1)vopt stst v ε≤+，以标识活动v的深度为递推值，进行数学归纳证明：
① 若v为开始活动，0voptststv==，定理为真；② 设命题对v的祖先中的标识活动均成立，设另一个簇的标识活动u为活动vwC∈和簇Cv的关键活动。
则u为w的所有前驱中数据到达最晚的前驱，所以wuuustst w μλ=++.
由于祖先活动u为一标识活动，由假设，命题对v的祖先中的标识活动均成立，(1)()uoptststε≤+ u定理1. 算法DCP对任意的DAG图(,,,)GVEμλ，存在01ε<≤满足()(1)/gGεε=，且调度结果最多为最优调度的1ε+倍.
证明: 由引理1，一定存在01ε<≤满足()(1)/gGεε=。
设optM为G的最优调度结果。故对G中所有的无后继的点v，max(())optoptvMstvμ≥ + 。因每个无后继的点均为标识点，由引理2，可得：
由定理1，()(1)optmakespanGMε≤+，由文献[1]中的定理2, ()(1')optmakespanGMε≤+。
即对给定的图GVEμλ，定理1证明了调度的makespan最多为最优调度结果的1ε+倍，而MJD中证明了G的makespan最多为G的最优调度的1 ' ε+倍。因'εε≤，故定理1给出的优度证明优于MJD算法给出的优度证明。
因此命题成立。证毕.
4.2 无任务复制的算法讨论
本小节讨论在不允许复制的情况下DAG图的特点，并证明存在一个多项式时间的算法，对Out-tree和In-tree的DAG，调度结果最多为最优调度的1ε+倍且01ε<≤。
定义1 (补图G′). 对于任意给定的一个DAG图G，定义其补图G′, G和G′的唯一不同在于G′中每条边的方向与G中的对应边（u,w）的方向正好相反，为（w, u）。
引理3. 在不允许复制的情况下，任意给定一个DAG图G及其补图G′, 设S′为G′的一个调度，则可得到对G的一个调度S：S中每个活动的匹配资源与S′一致，定义S中每个活动v的开始时间为则G的调度S为一合理的调度，且与其补图G′的调度S′具有相同的makespan.
证明: 首先证明G的调度S为一合理的调度。设G′开始活动为v1，结束活动为vn，在调度S′中的开始时间与结束时间为st1′、ct1′、stn′和ctn′。对任意的，设其在G′的调度S′中的开始时间和结束时间分别为stwV∈w′和ctw′。
由于In-tree中的每个活动最多只有一个子活动，由DCP算法，实际上没有活动被复制。故在不允许复制的情况下，算法DCP对In-tree的DAG可生成1ε+优度的解。
② 对任意的Out-tree的G，其补图为In-tree，对补图G′进行调度得到解S′，并定义原图G的调度为()(')(')v v stSmakespanSctS=，由引理3，S为一合理的调度，且与其补图G′的调度S′具有相同的makespan。
在不允许复制的情况下，原图与补图的最优解的makespan是相同的。由①，存在0 1 ε<≤，使算法DCP对In-tree的G′可生成1ε+优度的解，所以上面构造的对Out-tree的G生成的解也最多为最优调度的1ε+倍。因此命题成立。证毕.
5 试验结果与分析
将DCP算法与相关的六个TDB算法在八个算例上进行比较，计算结果见表1。其中算例来源及其它TDB算法的计算结果参见文献[2]。|R|是指DCP算法调度占用的资源数目。从调度长度上看，DCP算法的计算结果始终是七个TDB算法中最好的，且有三个算例得到了更好的解。
图4为七个算法的加速比比较，其中加粗的为DCP算法的加速比曲线。加速比为串行时间与并行时间的比值，加速比越高的算法执行结果越好。从图中可看出DCP算法的加速比始终是最高的。
以上实验说明DCP算法在理论与实验上是一致的，均得到了很好的结果。分析DCP算法与其他TDB算法的特点，可看出：（1）均使用了任务复制技术，从而简化问题的求解，并可得到比不复制任务的算法更好的解。（2）有些算法使用的静态优先级列表，有些使用的是动态优先级列表，一般而言，动态优先级列表能更准确地抓住当前情况下的关键簇或关键活动，求解结果优于静态优先级列表，但复杂度高于静态优先级列表。只要是多项式时间的算法，牺牲一定的复杂度以得到更好的优度是值得的，故DCP算法采用了动态优先级列表，并且采用简单贪婪策略，用二分搜索、插入更新动态就绪列表，保证动态列表的构造时间很小。(3) 对于复制与合并的粒度，如果仅以活动为粒度，则丢失了祖先活动的分簇信息，且由于粒度较细使算法运行的时间较长；若仅以簇为粒度，虽然运算速度快，但可能因粒度过粗造成错过更佳方案的机会。其他算法多以活动为单位进行复制和合并，DCP算法既考虑以活动为单位，也考虑以簇为单位进行复制与合并，这使DCP算法的复杂度下降，且计算更有效。(4)计算Sv的过程中，DCP总是选择不劣于当前解的邻域作为下一个解，且邻域总是考虑合并关键前驱或其对应簇，即最有希望改进当前解的邻域，从而有效地控制了计算Sv的复杂度。(5) DCP算法在最后构造调度时，首先考虑是否有簇包含当前簇，这样在不增加调度长度的前提下，可以有效减少占用的资源数目。
6 结论
本文基于对任务复制的算法的分析，提出了以调度长度最小的主要目标、减少资源数目为次要目标的动态关键前驱调度算法DCP。DCP将任务复制、分簇与优先级列表三种方法结合起来，对待复制的重要活动集给出了一种新的选择策略，以跨簇活动的最早可能开始时间为相应活动的释放时间进行贪心调度，然后选择导致当前活动最早可能开始时间不能再减少的关键活动或关键活动的对应簇为待复制的重要活动集。理论上，证明了DCP算法对任意的DAG得到了优于PY和MJD算法的性能保证。通过与相关工作的比较可以看出，DCP算法的求解结果一直是最优的，且在有些算例上得到了比前人更好的结果。因此，DCP算法在理论与实验上是一致的，均取得了很好的结果，对于高性能应用的调度是一个较优的选择。文章还对无任务复制时调度In-tree和Out-tree的1ε+优度的算法进行了讨论，对无任务复制时的调度问题有一定的参考价值。
