Workflow Scheduling Algorithm Based on Critical Path Lookahead
-
摘要:
为了进一步提高工作流调度的效率，对异构环境下的工作流调度算法进行研究，提出了一种基于关键路径前瞻算法（critical path lookahead algorithm，CPLA）的工作流调度算法.该算法在任务确定优先级阶段考虑了入口任务到当前任务的最长路径，以及当前任务到出口任务的最长路径；在资源选择阶段考虑了关键路径任务和非关键路径任务对调度结果的影响.使用随机生成的和真实世界的2种不同类型的有向无环图（directed acyclic graph，DAG）工作流来评估CPLA的性能，实验结果表明：CPLA能够有效地缩短调度长度，算法的效率、加速比、调度长度比等性能有所提高，并且算法的时间复杂度低于目前调度效果最好的Lookahead算法.
Abstract:To further improve the efficiency of workflow scheduling, a workflow scheduling algorithm in heterogeneous environment was studied, and a workflow scheduling algorithm based on critical path lookahead algorithm (CPLA) was proposed. In the task priority stage, the longest path of the entry task to the current task was considered, and the longest path of the current task to exit task was also taken into consideration. In the resource selection stage, the impact of tasks of the critical path and tasks of the non critical path on the scheduling results were considered. Two different types of DAGs which were randomly generated and from real-world were used to evaluate the performance of CPLA. The experimental results show that the CPLA can effectively shorten the scheduling length. The performances of this algorithm, such as efficiency, speedup, scheduling length ratio of algorithm are improved, and the time complexity of the algorithm is lower than that of the lookahead algorithm.
-
Keywords:
- static workflow scheduling /
- critical path /
- non critical path /
- speedup
-
随着科技信息的发展，很多领域的科学和工程计算问题都被抽象为工作流模型[1].这些工作流模型一般由一组有前后依赖关系的任务节点组成，可以抽象为有向无环图(directed acyclic graph, DAG).将给定工作流任务作为对象，若干处理器作为完成任务的资源，在满足一定的约束条件下, 对任务和处理器进行分配并安排先后次序，将所需的资源进行最优调度，称为工作流调度问题.调度问题在物流、航空、生物、医疗等各领域都有广泛的应用.工作流调度问题已经被证明是多项式复杂程度的非确定性(non-deterministic polynomial，NP)完全问题，即不能在多项式时间里找到问题的最优解[2].
随着科学工作流问题的计算需求不断增长，分布式异构资源的工作流调度被广泛研究[3-13].分布式异构资源工作流调度问题根据采用方式不同，可分为基于启发式(heuristic-based)和基于引导随机搜查(guided-random-search-based)两大类，前者还可以细分为3类，分别为列表调度启发式(list-scheduling heuristics)、聚类启发式(clustering heuristics)、基于复制的启发式(duplication-based heuristics).这些算法都分为任务优先级确定和资源选择2个阶段.在列表调度启发式[3-5]中，任务依据每个任务被赋予的优先级进行调度，每个被选择的任务将映射到能够满足预先定义目标函数的处理器上.例如，将任务映射到完成时间最早的处理器上进行调度.此外，列表调度算法又分为静态调度和动态调度.在静态调度算法中，任务在调度之前优先级就已确定，因此，在实际调度过程中优先级不发生改变；相反，动态算法[6]在每一次调度之后，会重新计算未调度任务的优先级，然后用新计算的优先级顺序重新进行调度.聚类启发式[7-8]在调度过程初始阶段，按照算法规则将任务分成不同的簇，称为任务簇，然后按照不同的任务簇分配处理器，同一簇的任务在同一个处理器上调度.聚类算法通常是针对无限数量的处理器，因此，不能被实际应用.基于复制的启发式算法[9]假设有无限的处理器可供分配，通过父任务的重复调度来减少处理器间的通信时间，进一步减少调度长度.随机搜索技术中最流行并且应用最广泛的一种算法是遗传算法(genetic algorithm，GA)[10]，虽然遗传算法调度质量很高，但是它的执行时间远长于其他类算法.
由于列表调度启发式算法简单高效，该算法已被广泛研究, 其中最著名的算法是Topcuoglu等[3]在2002年提出的异构分布式环境下的最早完成时间优先(heterogeneous earliest-finish-time，HEFT)调度算法. HEFT算法已成功在Askalon异构分布式系统中应用, 同时Topcuoglu等[3]还提出了基于关键路径任务映射到一个处理器的(critical-path-on-a-processor，CPOP)算法.该算法定义了DAG工作流的关键路径，在处理器选择阶段，分别考虑关键路径任务和非关键路径任务，但是CPOP算法的调度效果并没有HEFT算法的好；因此，HEFT算法被广泛应用. 2010年，Bittencourt等[14]对HEFT算法进行改进，提出了前瞻(lookahead)算法.该算法的调度决策不止依赖于任务本身，还依赖子任务的执行结果. Lookahead算法在调度前先获得子任务的调度信息，然后再综合考虑当前任务和子任务的调度，对这个任务做出最优的资源分配决策，但是这增加了算法的时间复杂度. 2014年，Arabnejad等[15]针对异构分布式系统下的工作流调度进一步提出了预测最早完成时间(predict earliest finish time，PEFT)算法. PEFT算法使用任务的乐观花费表(optimistic cost table，OCT)中的平均值作为任务的优先级，OCT是求子任务到出口任务的最长路径，即PEFT算法在任务确定优先级阶段，考虑了任务本身的调度决策对后继任务的影响，在处理器选择阶段又考虑了任务的前驱任务对任务调度的影响，从DAG的结构来说，考虑得十分全面. PEFT算法的时间复杂度与HEFT算法一样，但是在DAG的并行度比较高的情况下，大量实验表明PEFT算法的调度效果并不理想.除了异构分布式环境中的应用，启发式算法还应用到云环境中，Guo等[16]在云环境下对工作流用资源聚类的方法进行调度. Mohanapriya等[17]针对云环境下的多目标调度问题给出了调度算法的分类.
本文基于现有研究，对异构分布式环境下的工作流调度问题，提出了基于关键路径前瞻算法(critical-path lookahead algorithm，CPLA)的工作流调度算法.该算法在任务确定优先级阶段考虑了入口任务到当前任务的最长路径，以及当前任务到出口任务的最长路径；在处理器选择阶段，对于非关键路径任务，考虑直接前驱任务的影响，找到前驱任务到当前任务的最短路径.对于关键路径任务，不仅考虑了任务前驱到当前任务的最短路径，还考虑到其子任务到出口任务的最长路径，使当前任务的决策有一定的预见性.综合来看，CPLA充分利用了关键路径上子任务对整个调度的影响，在性能与Lookahead算法相近的基础上降低了时间复杂度.
1. DAG调度模型
1.1 问题描述及模型建立
工作流模型可以用一个DAG来表示，记DAG为G={V, E}，任务的集合表示为V={n1, n2, …, nn}，每一个ni代表一个计算任务，|V|=n表示工作流中所有任务节点的个数为n；E为有向边的集合，表示任务间的前后依赖关系，对于任意的边(ni, nj)∈E，任务ni执行后才执行任务nj.在DAG中没有前继的任务称为入口任务，记作nentry，没有后继的任务称为出口任务，记作nexit.处理器的集合记为P={p1, p2, …, pq}，|P|=q表示有q个处理器，每一个任务ni都要在处理器pj上执行且存在执行时间ωij，每一个任务ni的平均执行时间为
$$ {{\bar \omega }_i} = \sum\limits_{j = 1}^q {{\omega _{ij}}/q} $$ (1) 任务间的通信数据使用一个n×n大小的矩阵D来表示，dij表示任务ni和任务nj之间所需要通信的数据总和.处理器之间传送数据的速度使用一个q×q大小的矩阵B来存储.处理器间通信的启动时间存储在一个q维的矢量L中.任务的通信传递时间使用一个n×n大小的矩阵C来表示，cik表示在处理器pm上的任务ni到处理器pn上的任务nk的传递时间，公式为
$$ {c_{ik}} = {L_m} + {d_{ik}}/{b_{mn}} $$ (2) 式中：Lm为处理器pm的启动时间; bmn为处理器pm到处理器pn间的传递速度. ${\bar c_{ik}} $表示在处理器pm上的任务ni到处理器pn上的任务nk的平均传递时间，公式为
$$ {{\bar c}_{ik}} = \bar L + {d_{ik}}/\bar B $$ (3) 式中：${\bar L} $为处理器的平均启动时间；$ {\bar B}$为处理器间的平均传递速度.若任务ni与任务nk在同一处理器上进行传递，则传递时间为0.
1.2 任务调度中的基本定义
下面给出工作流调度中常用的基本定义.
定义1 DAG中从入口任务到出口任务最长的路径称为DAG的关键路径(critical path，CP)，关键路径长度值为|LCP|.若DAG中所有任务的执行时间最小，那这样的关键路径也有最小的执行时间，记这样的关键路径为CPmin.
定义2 关键路径上的任务称为关键路径任务.
定义3 定义pred(ni)为DAG中任务ni的前继任务集合，succ(ni)为DAG中任务ni的后继任务集合.
定义4 任务ni在处理器pj上的最早开始时间记为TES，定义为
$$ {T_{{\rm{ES}}}}\left( {{n_i},{p_j}} \right) = \max \left\{ {{T_j},\mathop {\max }\limits_{{n_m} \in {\rm{pred}}\left( {{n_i}} \right)} \left( {{T_{{\rm{AF}}}}\left( {{n_m}} \right) + {c_{m,i}}} \right)} \right\} $$ (4) 式中：pred(ni)表示任务ni的前继任务集合; Tj表示任务在处理器pj上可以开始的最早时间; TAF(nm)表示任务ni的前继任务nm的实际完成时间; cm, i表示任务nm到任务ni之间的传递时间，内层max表示任务ni的所有前继任务nm到达处理器pj的时间，对于入口任务nentry，到达任何处理器的时间为0，即TES(nentry, pj)=0.
定义5 任务ni在处理器pj上的最早完成时间记为TEF，定义为
$$ {T_{{\rm{EF}}}}\left( {{n_i},{p_j}} \right) = {T_{{\rm{ES}}}}\left( {{n_i},{p_j}} \right) + {w_{i,j}} $$ (5) 式中wi, j表示任务ni在处理器pj上的执行时间.
2. DAG调度的CPLA
2.1 CPLA的具体描述
为提高DAG调度的效率，CPLA的调度过程也分2个阶段.
1) 任务优先级确定阶段
任务优先级确定阶段，顾名思义就是按照一定的规则赋予每个任务优先级，然后按照优先级大小对任务进行排序，形成一个任务队列，最后按照这个队列中的顺序选择任务，并传送给第2阶段处理.队列的构建有2种方式：一种是静态队列，另一种是动态队列.与静态队列相比，动态队列使用入口任务来初始化，每次只存放当前时刻的就绪任务.
CPLA采用动态列队，由入口任务到出口任务的最长路径来确定任务的优先级. DAG中任务ni的向上排序值ru为从任务ni到出口任务的多条路径中平均执行时间和平均通信传递时间总和的最大值，其中也包括这个任务本身的执行时间平均值.一个任务ni的向上权值ru为
$$ {r_{\rm{u}}}\left( {{n_i}} \right) = {{\bar \omega }_i} + \mathop {\max }\limits_{{n_j} \in {\rm{succ}}\left( {{n_i}} \right)} \left\{ {{r_{\rm{u}}}\left( {{n_j}} \right) + {{\bar c}_{ij}}} \right\} $$ (6) 式中：succ(ni)为DAG中任务ni的后继任务集合；$ {{\bar c}_{ij}}$为任务ni与任务nj之间的平均传递时间，对于出口任务nexit, ru(nexit)=0.
DAG中向下权值rd为入口任务到当前任务ni的多条路径中平均执行时间和平均通信传递时间总和的最大值，其中不包括这个任务ni本身的执行时间平均值.一个任务ni的向下权值rd为
$$ {r_{\rm{d}}}\left( {{n_i}} \right) = \mathop {\max }\limits_{{n_j} \in {\rm{pred}}\left( {{n_i}} \right)} \left\{ {{r_{\rm{d}}}\left( {{n_j}} \right) + {{\bar \omega }_j} + {{\bar c}_{j,i}}} \right\} $$ (7) 式中：pred(ni)为任务ni的直接前驱任务集合; ${{\bar \omega }_j} $为任务nj在各个处理器上的平均执行时间; $ {{\bar c}_{j, i}}$为任务nj与任务ni之间的平均传递时间.对于入口任务nentry, rd(nentry)=0.
CPLA采用的是由入口任务到出口任务的最长路径来确定任务的优先级，即计算每个任务的优先级l，其中l=ru+rd.在任意给定时刻，队列里只包含所有的就绪任务.每次调度选择就绪任务中优先级最高的任务，也就是l值最大的任务.
2) 处理器的选择阶段
在处理器选择阶段，任务选择处理器的条件就是选择完成时间最小的处理器.其中时间包括任务在处理器上运行的计算时间和任务与任务之间传递数据的通信时间，处理器内部的通信时间一般可以忽略.首先，计算任务在各个处理器上的执行时间，然后从中找到执行时间最小的处理器分配给该任务执行，重复这个过程直到所有的任务都调度完成.由于同一个处理器上执行的任务会出现一定的空隙，为了能够充分利用时间空隙，提高资源的利用率，一般采用插入策略，插入的位置是在同一个处理器上2个已经调度的任务之间，也可能是在处理器可以开始执行任务到该处理器上第1个任务开始执行之间，并且满足任务能够在这段空闲时间内完成调度，同时还应该维持优先约束.
CPLA针对关键路径任务和非关键路径任务采用2种不同的策略：首先判断任务是否是关键路径任务，如果是关键路径任务，则尝试在每个处理器上运行这个任务，选择其子任务中最早完成时间最小的处理器；如果不是关键路径任务，则选择任务本身最早完成时间最小的处理器进行调度. CPLA使任务的决策有一定的预见性，又降低了算法的时间复杂度，图 1是算法的主要流程.
CPLA的步骤如下.
1:由式(1)(2)计算DAG中每个任务的平均执行时间和每2个任务间的平均通信时间
2:从出口任务开始，根据式(6)计算所有任务的ru值
3:从入口任务开始，根据式(7)计算所有任务的rd值
4:以l=ru+rd的值为任务的优先级, 初始化任务队列M
5:以入口任务优先级的值为关键路径长度LCP，并初始化关键路径任务集MCP={nentry}
6: nk < --nentry
7: if nk不是出口任务
8: 找到任务的后继任务中优先级l等于LCP的任务nj
9: 更新关键路径任务的集合，MCP=MCP∪{nj}
10: end if
11: while队列M里还有未调度的任务
12: 从任务列表中选择优先级最高的任务ni
13: if ni在MCP中
14: 求任务ni的直接后继任务集合Pr
15: 对于处理器集合P中的每一个处理器pj
16: 使用基于插入的调度策略，根据式(4)(5)计算任务ni的Tef
17: if Pr中还有未调度的子任务
18: 从Pr中选出优先级最高的任务nm
19: 对于处理器集合P中的每一个处理器pj
20: 使用基于插入的调度策略计算任务nm的TEF
21: end if
22: end if
23: 将任务ni安排到满足nm的TEF值最小的处理器px上
24: else
25: 对于任务ni，根据式(4)(5)选择最早完成时间TEF最小的处理器pj
26:删除任务ni，判断ni的后继任务是否成为就绪任务，更新任务队列
27: end while
在CPLA中，任务确定优先级阶段考虑了入口任务到当前任务的最长路径，以及当前任务到出口任务的最长路径.在处理器选择阶段，对于非关键路径任务，考虑直接前驱任务的影响，找到前驱任务到任务的最短路径；对于关键路径任务，不仅考虑了任务前驱到任务本身的最短路径，还考虑了其子任务到出口任务的最长路径，使任务的决策有一定的预见性，更有利于后面其子任务的调度.
2.2 算法的时间复杂度
对于DAG，任务数为n，处理器总数为q，任务的平均子任务个数为c，DAG中关键路径任务的平均子任务数为m(m < c).若任务是关键路径任务，算法的复杂度增加为子任务数与处理器个数的乘积，因此，对于关键路径任务，算法的时间复杂度增加的因子为m×q. CPLA采用最早完成时间策略，DAG中有n个任务，那么边的个数为n(n-1)，最早完成时间算法的复杂度为O(n(n-1)×q)，即O(n2q)，因此，CPLA的时间复杂度为O(mn2q2). HEFT算法的时间复杂度为O(n2q)，Lookahead算法的时间复杂度比HEFT算法多了一个因子c×q，复杂度为O(cn2q2)，其中c是平均的子任务数，CPLA的时间复杂度为O(mn2q2)，因为m < c, 所以CPLA的时间复杂度比Lookahead算法的时间复杂度低. CPLA从理论上来说结合了HEFT算法和Lookahead算法的中心思想，其时间复杂度又恰在两者之间，在调度质量和复杂度之间找到了一个平衡.
3. 实验结果与分析
下面给出DAG任务调度算法中常用的比较度量.
定义6 DAG中所有任务实际完成时间的最大值称为调度长度，表示为
$$ M = \mathop {\max }\limits_{{n_i} \in V} {T_{{\rm{AF}}}}\left( {{n_i}} \right) $$ (8) 式中TAF(ni)表示任务ni的实际完成时间.
一般来说，一个DAG工作流的调度长度越小，算法的调度质量越好.
定义7 每个DAG的调度长度与所有关键路径任务在各个处理器上执行时间的最小值之和的比值称为算法的调度长度比(schedule length ratio，SLR)，即
$$ {R_{{\rm{SL}}}} = \frac{M}{{\sum\limits_{{n_i} \in {\rm{C}}{{\rm{P}}_{\min }}} {\mathop {\min }\limits_{{p_j} \in P\left\{ {{w_{i,j}}} \right\}} } }} $$ (9) 式中分母表示所有任务的执行时间最小的关键路径CPmin上的任务在各个处理器上的执行时间最小值之和.因为分母是下界，所以任何算法的SLR值一般都不会小于1，算法的SLR值越低，性能越好.
定义8 DAG中所有任务在同一处理器上顺次执行总执行时间的最小值与算法调度长度的比值称为加速比(speedup.对于ni∈V, pj∈P，加速比的计算公式为
$$ S = \frac{{\mathop {\min }\limits_{{p_j} \in P} \left\{ {\sum\limits_{{n_i} \in V} {{w_{i,j}}} } \right\}}}{M} $$ (10) 式中：分子表示所有任务在每一个处理器上顺次执行的总执行时间最小的处理器所对应的执行时间；分母表示调度长度.加速比一般体现出任务的并行度，比值越大，并行度越高.另外，加速比与处理器的数量有很大关系，计算资源越多，算法调度长度越短，加速比越大.但是对于计算资源大于DAG中最大可并行任务数量的情况下，再增加处理器对缩短算法调度长度是无效的.
定义9 加速比与处理器数量的比值定义为效率(efficiency).假设处理器数量为q，效率的计算公式为
$$ E = \frac{S}{q} $$ (11) 一般算法的效率越大，表明该调度算法的性能越好.
3.1 随机DAG的实验调度分析
使用一个随机DAG生成器[18]，生成器对于DAG的结构有5种参数:1) n表示DAG的任务数. 2) fat表示影响DAG高度和宽度的参数，一般定义DAG的高度(层数)是均值为fat/$\sqrt n $的均匀分布，每层的宽度(任务数)是均值为fat $\sqrt n $的均匀分布. fat值越大，DAG图的并行度越大. 3) density表示DAG中不同层之间边的密度，即优先关系的多少. 4) regularity表示DAG中每层任务总数的差别. 5) jump表示DAG中任务间通信跨越的最大层数，至少大于等于1才表示2个任务之间有优先约束. RCC表示DAG中所有边的平均通信时间之和与所有任务节点的平均执行时间的比值，称为通信计算比. β表示DAG中任务节点在处理器上的执行时间的范围比，β值越大，表示任务在不同处理器上的计算速度差别越大. q表示处理器的个数.
在每次实验中，设置不同的参数值，得到不同的DAG, 参数设置为
n=[30,40,50]；
fat=[0.3, 0.7]；
density=[0.2, 0.8]；
regularity=[0.2, 0.8]；
jump=[1,2]；
RCC=[1,2]；
q=[4,8,12].
在这些参数下一共产生96个随机DAG进行实验.用PEFT、HEFT、Lookahead、CPOP四种调度算法与CPLA进行对比实验.
图 2和图 3分别展示的是处理器个数为3，RCC为1和2的情况下，5种算法的平均调度长度比和平均加速比.由图 2可以看出，CPLA的平均调度长度比最小，CPOP算法的平均调度长度比最大.
![]()
图 2 不同RCC下算法的平均调度长度比Figure 2. Average scheduling length ratio of the algorithm under different RCC由图 3可以看出，CPLA的平均加速比最大，性能最好，Lookahead算法平均加速比次之，HEFT算法和PEFT算法结果相似，CPOP算法结果最差.
图 4表示5种算法分别在4、8、12个处理器下的效率.可以看出，CPLA和Lookahead算法的效率最高，HEFT算法和PEFT算法的效率接近，CPOP算法的效率最低.
![]()
图 4 不同处理器数下算法的效率Figure 4. Efficiency of the algorithm under different processor numbers图 5表示5种算法在任务数量为30、40、50的DAG下的平均调度长度比.可以看出，在任务数为30和40的时候，CPLA的$ {{\bar R}_{{\rm{SL}}}}$最接近1，在任务数为50的时候，Lookahead算法的$ {{\bar R}_{{\rm{SL}}}}$最小，但是在3种情况下，CPLA的$ {{\bar R}_{{\rm{SL}}}}$都比CPOP算法的小.
![]()
图 5 不同任务数下算法的平均调度长度比Figure 5. Average scheduling length ratio of the algorithm under different tasks3.2 真实DAG的实验调度分析
除了随机产生的DAG，本文还采用真实的DAG来进行实验调度分析.真实的DAG是根据真实的问题产生的图结构，一些知名的真实的DAG应用有：Montage(天文学)[19]、Epigenomics (生物学)[20]、LIGO(引力波物理学)、CyberShake(地震波物理学)等.其中Montage工作流结构如图 6所示.
分别用25个任务数的Montage、24个任务数和100个任务数的Epigenomics进行调度试验.
对于25个任务数的Montage任务图，设置RCC=[0.5, 1, 2].图 7表示5种算法在处理器个数为2的计算环境下得到的平均调度长度.图 8表示5种算法在处理器个数为5的计算环境下得到的平均调度长度.从2个图可以看出，CPLA在不同的DAG下得到的平均调度长度都比CPOP算法的平均调度长度小.图 7中在RCC为1的情况下，CPLA的平均调度长度小于其他算法.
![]()
图 7 处理器个数为2，不同RCC下算法的平均调度长度Figure 7. Average makespan under different RCC with two processors![]()
图 8 Montage任务图下，处理器个数为5，不同RCC下算法的平均调度长度Figure 8. Average makespan under different RCC with five processors in Montage graph在24个任务数的Epigenomics任务图下，图 9表示5种算法在处理器个数为5的环境下得到的平均调度长度.可以看出，在3种通信计算比下，CPLA比CPOP算法的平均调度长度小.
![]()
图 9 Epigenomics任务图下，处理器个数为5，不同RCC下算法的平均调度长度Figure 9. Average makespan under different RCC with five processors in Epigenomics graph在100个任务数的Epigenomics任务图下，图 10表示5种算法在处理器个数为10的环境下得到的平均调度长度.可以看出，CPLA的平均调度长度比CPOP算法的小，而且随着RCC增大，CPLA的平均调度长度小于HEFT算法和PEFT算法.图 11表示5种算法在处理器个数为20的环境下得到的平均调度长度.可以看出，CPLA的平均调度长度比CPOP算法的小，且随着RCC增大，CPLA的平均调度长度小于HEFT算法和PEFT算法.
![]()
图 10 处理器个数为10，不同RCC下算法的平均调度长度Figure 10. Average makespan under different RCC with ten processors![]()
图 11 处理器个数为20，不同RCC下算法的平均调度长度Figure 11. Average makespan under different RCC with twenty processors对于任务数为100的Epigenomics任务图，设置RCC=1，图 12表示5种算法在处理器个数分别为5、10、15、20的情况下得到的效率.可以看出，在RCC比较大的情况下，CPLA的效率和Lookahead算法的效率接近，而且CPLA的效率高于HEFT算法和PEFT算法.
![]()
图 12 不同处理器数下5种算法的效率Figure 12. Efficiency of five algorithms under different processor numbers由实验可以看出，CPLA在任务决策中的预见性提高了算法的效率，算法采取关键路径分类任务降低了算法的时间复杂度，提高了算法的平均加速比. CPLA的效率、调度长度、平均加速比优于其他算法.
4. 结论
1) 本文提出了基于关键路径前瞻的工作流调度算法，在关键路径任务进行处理器分配的过程中考虑分配结果对后继任务的影响；对于非关键路径的任务，考虑直接前驱任务的影响，找到前驱任务到当前任务的最短路径，采用最早完成时间策略来选择处理器.
2) 与现有的算法相比，CPLA的时间复杂度比Lookahead算法的时间复杂度低；与其他DAG调度算法相比，CPLA的加速比、效率比较高；CPLA在大多数情况下与其他算法相比调度长度比较小.
3) 如果将CPLA应用到多工作流调度中，是否会影响算法的调度长度，能否在调度过程中更合理地利用已调度任务间的间隙还有待进一步的研究.
-
![]()
图 2 不同RCC下算法的平均调度长度比
Figure 2. Average scheduling length ratio of the algorithm under different RCC
![]()
图 4 不同处理器数下算法的效率
Figure 4. Efficiency of the algorithm under different processor numbers
![]()
图 5 不同任务数下算法的平均调度长度比
Figure 5. Average scheduling length ratio of the algorithm under different tasks
![]()
图 7 处理器个数为2，不同RCC下算法的平均调度长度
Figure 7. Average makespan under different RCC with two processors
![]()
图 8 Montage任务图下，处理器个数为5，不同RCC下算法的平均调度长度
Figure 8. Average makespan under different RCC with five processors in Montage graph
![]()
图 9 Epigenomics任务图下，处理器个数为5，不同RCC下算法的平均调度长度
Figure 9. Average makespan under different RCC with five processors in Epigenomics graph
![]()
图 10 处理器个数为10，不同RCC下算法的平均调度长度
Figure 10. Average makespan under different RCC with ten processors
![]()
图 11 处理器个数为20，不同RCC下算法的平均调度长度
Figure 11. Average makespan under different RCC with twenty processors
-
[1] JUVE G, CHERVENAK A, DEELMAN E, et al. Character izing and profiling scientific workflows[J]. Future Generation Computer Systems, 2013, 29(3):682-692. doi: 10.1016/j.future.2012.08.015
[2] GARY M R, JOHSON D S. Computers and intractability: a guide to the theory of NP-completeness[D]. New York: WH Freeman and Company, 1979.
[3] TOPCUOGLU H, HARIRI S, WU M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3):260-274. doi: 10.1109/71.993206
[4] ILAVARASAN E, THAMBIDURAI P. Low complexity performance effective task scheduling algorithm for heterogeneous computing environments[J]. Journal of Computer Sciences, 2007, 3(2):94-103.
[5] ILAVARASAN E, THAMBIDURAI P, MAHILMANNAN R. High performance task scheduling algorithm for heterogeneous computing system[C]//International Conference on Algorithms and Architectures for Parallel Processing. Berlin: Springer, 2005: 193-203.
[6] KWOK Y, AHMAD I. Dynamic critical-path scheduling:an effective technique for allocating task graphs to multiprocessors[J]. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(5):506-521. doi: 10.1109/71.503776
[7] BOERES C, FILHO J V, REBELLO V E F. A cluster based strategy for scheduling task on heterogeneous processors[C]//Proceedings 16th Symposium on Computer Architecture and High Performance Computing, SBAC-PAD 2004. Piscataway: IEEE, 2004: 214-221.
[8] CIROU B, JEANNOT E. Triplet: a clustering scheduling algorithm for heterogeneous systems[C]//Proceedings International Conference on Parallel Processing Workshops. Piscataway: IEEE, 2001: 231-236.
[9] PARK G, SHIRAZI B, MARQUIS J. A new approach for duplication based scheduling for distributed-memory systems[C]//Proceedings 11th International Parallel Processing Symposium. Piscataway: IEEE, 1997: 157-166.
[10] WANG L, SIEGEL H J, ROYCHOWDHURY V P. A genetic algorithm-based approach for task matching and scheduling in heterogeneous computing environments[C]//Proceedings of Heterogeneous Computing Workshop. Piscataway: IEEE, 1996: 72-85.
[11] 田国忠, 肖创柏, 谢军奇.有期限约束的多DAG共享资源的调度及公平费用优化方法[J].计算机学报, 2014, 37(7):1607-1619. http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201407018.htm TIAN G Z, XIAO C B, XIE J Q. Scheduling and fair cost-optimizing methods for concurrent multiple DAGs with deadline sharing resources[J]. Chinese Journal of Computers, 2014, 37(7):1607-1619. (in Chinese) http://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201407018.htm
[12] 田国忠. 多DAG共享资源调度的若干问题研究[D]. 北京: 北京工业大学, 2014. TIAN G Z. Research several problems of scheduling multiple DAGs sharing resources[D]. Beijing: Beijing University of Technology, 2014. (in Chinese)
[13] ARABNEJAD H, BARBOSA J G. Performance evaluation of list based scheduling on heterogeneous systems[C]//Proceedings of European Conference on Parallel Processing. Berlin: Springer, 2011: 440-449.
[14] BITTENCOUNT L F, SAKELLARIOU R, MADERIRA E R M. DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm[C]//201018th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP). Piscataway: IEEE, 2010: 27-34.
[15] ARABNEJAD H, BARBOSA J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3):682-694. doi: 10.1109/TPDS.2013.57
[16] GUO F, YU L, TIAN S, et al. A workflow task scheduling algorithm based on the resources' fuzzy clustering in cloud computing environment[J]. International Journal of Communication Systems, 2015, 28(6):1053-1067. doi: 10.1002/dac.v28.6
[17] MOHANAPRIYA N, KOUSALYA G, BALAKRISHNAN P. Cloud workflow scheduling algorithms:a survey[J]. International Journal of Advanced Engineer Technology, 2016, 7(3):88-195.
[18] SUTER F. DAG generation program[R/OL]. [2010-10-19]. http://www.loria.fr/suter/dags.html.
[19] Spitzer Science Center. MONTAGE: an astronomical image mosaic engine[R/OL]. [2013-03-31]. http://montage.ipac.caltech.edu/.
[20] USC Molecular Genomics Core. USC epigenome center[R/OL]. [2013-05-16]. http://epigenome.usc.edu/.
-
期刊类型引用(2)
1. 崔璐，毋涛. 基于蚁群的工作流任务分配算法研究. 计算机技术与发展. 2021(05): 102-107 . 
百度学术
2. 江日念，林霞，许锟. 审批流程模型的路径选择策略研究. 计算机技术与发展. 2020(01): 65-69 . 百度学术
其他类型引用(7)
下载:
计量
- 文章访问数: 118
- HTML全文浏览量: 10
- PDF下载量: 34
- 被引次数: 9
