0 引言

在大数据时代，数据的密集计算往往不能依靠单一的处理器完成，需要依赖于分布式环境下的异构计算系统(Heterogeneous Computing System,HCS)。异构计算系统被定义为一个由高速网络联通的多处理器计算平台，可以执行并行和分布式的密集计算^[1]。所谓计算机系统的异构性，是指其计算资源之间存在计算能力的差异，并且各计算资源之间进行数据传输时，其通信传输速度也存在差异性。云计算平台就是一个典型的异构计算系统。一个有效的任务调度算法可以提高整个异构计算系统的效率，目标是为了得到最短的完成时间(makespan)^[2]。具体来说，算法需要在满足任务间先后续关系的情况下，决定每个任务的执行顺序，并将其分配到合适的处理器上去执行。

对于如何合理进行任务调度的问题，诸多学者进行了研究，比较典型的任务调度算法有Topcuoglu等^[3]提出的HEFT(Heterogeneous Earliest Finish Time)算法，该算法被认为是最经典的任务调度算法，具有很好的通用性和稳定性，通常被作为最基本的参照算法进行实验对比；但是由于算法本身对于异构的差异性考虑不够，所以对待复杂异构环境下的任务调度结果往往并不理想。Munir等^[4]提出的SDBATS(Standard Deviation-Based Algorithm for Task Scheduling)算法是一个新颖的任务调度算法，首次提出使用标准方差(standard deviation)代替均值的方法进行任务调度优先级Rank值的计算，提高了对计算差异过大的异构调度的算法适应性；但是算法本身过于忽略通信开销的优先权值，容易引起计算开销和通信开销的不公平性，并且算法采用对每个处理器都进行入口任务的副本策略，这一策略有时并不合理，不但不会提高调度效率，甚至会造成延迟调度时间的情况。Arabnejad等^[5]提出的PEFT(Predict Earliest Finish Time)算法是新近提出的优秀调度算法，给出一个预测性的OCT(Optimistic Cost Table)作为优先权值，计算所有子节点在不同处理器上的计算开销与通信开销之和的最小值，并将此值代入处理器选择阶段中。但是由于PEFT算法过于关注子节点在串行时的开销，对于子节点并行度较高的情况和通信开销较大的任务模型，并不能给出理想的调度结果。本课题组在文献^[6]中提出了HSIP(Heterogeneous Scheduling algorithm with Improved task Priority)，更好地考虑了异构差异度较大环境下的合理调度问题，但HSIP算法在对于计算开销与通信开销之间的权值数量级平衡问题以及对于处理器的分配策略还不够理想，存在进一步改良的可能。

综上所述，本文提出HSFT(Heterogeneous scheduling algorithm with immediate Successor Finish Time)算法，在异构差异度较大的情况下，平衡计算开销与通信开销之间的数量级公平性，采用更为合理的优先权值计算方法，并提出直接后继节点完成时间(Successor Finish Time,SFT)用于处理器分配策略。实验证明，HSFT比HEFT、SDBATS、PEFT等算法有更好的调度长度(makespan)、调度长度比(schedule length ratio)与效率值(efficiency)，并且没有增加算法的时间复杂度。

1 相关工作

近年来，众多的调度算法被提出用于解决在异构计算系统下的任务调度问题。通常可以将这些调度算法根据解决的问题模型分为两个大类，即动态调度(dynamic scheduling)和静态调度(static scheduling)。在动态调度的问题模型中，每个任务的计算开销和通信开销以及任务之间的连接关系都是未知的。在一个新任务到来时，算法才能得到具体的相关参数，给出一个实时的调度策略。动态调度算法只对新到达的任务和正在准备执行的任务进行判断，决定先后执行的策略。比较典型的动态调度算法有Dynamic Mapping Heuristics^[7]和Dynamic scheduling method^[8]。

对于静态调度的问题模型来说，每个任务的计算和通信开销以及整个任务间的连接关系都是已知的。算法可以在编译时间内，根据上述已知的参数给出一个理想的调度结果。通常也将静态调度算法分为两大类：导向随机搜索机制算法(guided random search-based algorithm)和启发式算法(heuristic-based algorithm)。比较典型的导向随机搜索机制算法有GA Multiprocessor Task Scheduling^[9]和Problem-Space Genetic Algorithm (PSGA)^[10]。这类算法都是通过多次的迭代来求得最优解，但是与启发式算法相比会增加过多的复杂度与处理器开销。启发式算法可以分为三种类型：聚类(clustering)、副本(duplication)和表(list)。聚类算法通常适合在同构计算环境下的调度，对于异构环境的调度效果有限。副本算法通常会得到较好的调度结果，但同样也会产生更高的算法复杂度。此外，副本会引起更多的处理器占用问题，这不仅会增加额外的处理器能耗开销，更会耽误其他任务对于资源的共享，影响整体的优化调度。表调度算法相对来说有着更好的调度性能、更低的算法复杂度，是静态调度中最为流行的调度算法。典型的表调度启发式调度算法有HEFT^[3]、SDBATS^[4]、PEFT^[5]、HSIP^[6]、LDCP(Longest Dynamic Critical Path)^[11]和PETS(low complexity Performance Effective Task Scheduling)^[12]等。

2 异构环境下的任务调度模型

本文研究的问题模型为在由多处理器集合P组成的异构计算系统中对单一应用程序(application)进行静态调度。调度算法目的为对单一应用程序在P中进行处理后，得到最小的执行时间。该模型与HEFT、SDBATS、PEFT等算法的问题模型一致。应用程序通常会描述为一个有向无环图(Directed Acyclic Graph,DAG)，G=(V,E)。其中V= {v₁,v₂,…,v_n}表示任务节点的集合，E={e₁,e₂,…,e_m}表示边的集合。一个简单的DAG模型用例如图 1，与前述算法中的例图具有相同的结构，并且其参数选取与文献^[5]完全一致。

每个节点v_i∈V表示一个具体的执行任务，每条边e_(i,j)∈E表示在任务先后续关系下的两个任务之间的通信开销，即任务v_i必须执行完成后才可以将数据传给v_j来执行。

在一个给出的DAG程序中，一个没有任何父节点的任务被称为入口节点(entry task)，一个没有任何子节点的任务被称为出口节点(exit task)。如果一个DAG中存在多个入口节点或出口节点，那么需要增加一个虚节点(即该节点的计算开销和通信开销均取值为0) ，来保证DAG在调度时具有唯一的入口或出口节点。计算开销矩阵W=V×P，其中V表示任务节点集合，P表示处理器集合。w_i,j表示任务v_i在处理器p_j上的执行时间。任务v_i的平均计算开销w_i，如式(1) 所示：

$\overline{{{w}_{i}}}={\left( \sum\limits_{j\in P}{{{w}_{i,j}}} \right)}/{P}\;$

(1)

c_i,j作为边e_(i,j)上的权值用来表示任务v_i和任务v_j之间的通信开销，当任务v_i和v_j分配到同一处理器上执行时，两者间通信开销为0，因为模型忽略同一处理器内部的通信开销，并且认为各处理器之间是完全联通的拓扑结构，在各处理器上进行任务的执行和通信传输是可以同时进行而没有冲突的。接下来给出几个在DAG调度问题中常见的定义。

定义1 调度长度(makespan)表示DAG中最后一个任务的完成时间，如式(2) 所示：

$makespan=\max \left\{ AFT\left( {{v}_{exit}} \right) \right\}$

(2)

其中AFT(v_exit)表示出口节点的实时完成时间。

定义2 最快开始时间(Earliest Start Time,EST)。EST(v_i,p_j)表示节点v_i在处理器p_j上可以开始执行的最早时间，具体定义如式(3) 所示：

$\begin{align} & EST\left( {{v}_{i}},{{p}_{i}} \right)=\max \\ & \left\{ {{T}_{Avl}}\left( {{\text{p}}_{\text{j}}} \right),\underset{{{v}_{m}}\in pred\left( {{v}_{i}} \right)}{\mathop{\max }}\,\left\{ AFT\left( {{v}_{m}} \right)+{{c}_{m,j}} \right\} \right\} \\ \end{align}$

(3)

其中：T_Avl(p_j)表示处理器p_j可以开始运行任务的最早时间，pred(v_i)表示任务v_i的所有直接前驱节点，即任务v_i在处理器p_j上最快开始运行时间，为处理器可以运行时间与前驱节点传输数据完成时间两者之间的较大值，当前驱节点v_m和v_i在同一处理器运行时，c_m,j=0。对于入口节点，不考虑处理器启动时间的情况下，最快开始时间EST(v_entry,p_j)=0。

定义3 最快完成时间(Earliest Finish Time,EFT)。EFT(v_i,p_j)表示任务vi在处理器p_j上的最快完成时间，如式(4) 所示：

$EFT\left( {{v}_{i}},{{p}_{j}} \right)=EST\left( {{v}_{i}},{{p}_{j}} \right)+{{w}_{i,j}}$

(4)

同样的，对于入口任务，其最快完成时间$EFT\left( {{v}_{entry}},{{p}_{j}} \right)={{w}_{{{v}_{entry}},j}}$。

定义4 出度通信开销权值(Out-degree Communication Cost Weight，occw)。表示任务v_i所有出度节点的通信开销之和，出度(out degree)即为该节点拥有的直接后继节点个数。具体如式(5) 所示：

$\left\{ \begin{align} & occw\left( {{v}_{i}} \right)=\sum\limits_{{{v}_{j}}\in succ\left( {{v}_{i}} \right)}{{{c}_{i,j}}} \\ & occw\left( {{v}_{exit}} \right)=0 \\ \end{align} \right.$

(5)

出度通信开销权值对于调度结果会产生很大的影响，当一个occw值过大的任务节点没有被优先调度时，往往导致其直接后继节点需要更长时间的等待。

综上所述，DAG调度算法的目标即为决定DAG中每个任务的执行顺序并将其分配到一个具体处理器上执行，以得到一个最小的调度长度(makespan)。当所有任务被执行完毕时，式(2) 中出口节点的实时完成时间即为调度长度。

3 HSFT

本文提出基于直接后继节点完成时间的异构调度算法——HSFT，算法由计算任务调度优先级阶段和处理器分配阶段两个阶段组成。

3.1 任务调度优先级阶段

在任务调度优先级阶段，通过从出口节点开始向上迭代来计算每个节点的优先权值rank_u，然后对其进行降序排列决定调度顺序。每个节点的rank_u计算如式(6) 所示:

$\left\{ \begin{align} & ran{{k}_{u}}\left( {{v}_{i}} \right)=\underset{{{v}_{j}}\in succ\left( {{v}_{i}} \right)}{\mathop{\max }}\,\left\{ \overline{{{w}_{i}}}\times {{\sigma }_{i}}+\frac{occw\left( {{v}_{i}} \right)}{outd\left( {{v}_{i}} \right)}+ran{{k}_{u}}\left( {{v}_{j}} \right) \right\} \\ & ran{{k}_{u}}\left( {{v}_{exit}} \right)=\overline{{{w}_{exit}}}\times {{\sigma }_{exit}} \\ \end{align} \right.$

(6)

其中：succ(v_i)表示任务v_i的所有直接后继节点，σ_i表示任务v_i计算开销的标准方差，outd(v_i)表示任务v_i的出度值，即直接后继节点的个数。采用标准方差可以更好地体现出同一任务在不同处理器上的计算差异，即计算异构差异越大，标准方差值越大，该算法的调度优先级就越高。使用标准方差与均值相乘作为计算权值可以更好地保证与通信开销在数量级上的公平性。同样的，使用出度通信开销权值occw除以出度求得平均直接后继节点通信开销作为通信开销权值，与单纯使用出度通信开销作为通信权值来比可以更公平地做到通信密集情况下的计算差异度与通信传输之间的均衡，可以使调度优先权值rank_u具有更好的计算开销和通信开销之间的平衡，使调度算法在不同的异构差异环境下具有更好的稳定性。

3.2 处理器分配阶段

在处理器分配阶段中，将已经决定好调度顺序的任务依次选择最合适的处理器进行执行，HSFT提出了3个具体的策略来顺序执行，详细介绍如下。

3.2.1 入口任务选择副本策略

传统的任务副本算法通常会减少调度长度，并增加实际运行时的容错性和稳定性，但是也会因为额外的副本增加处理器的负载而影响其他任务的调度，降低处理器的效率^[13-14]。入口任务由于是整个调度算法中执行的第一个任务，即在各处理器均为空载的情况下，采用本算法提出的入口任务选择副本策略，可以在不引起处理器过载的情况下，进一步提高整个程序的调度效率，其他任务不需要等待入口副本的执行而影响自身的运行时间。这种策略对于入口任务直接后继节点传输时间远大于处理器执行入口任务时间的情况极为有效，并且当判断执行入口副本并不会减少调度时间的情况时，也不会执行副本引起延迟。对于入口副本是否执行的具体判断策略如下：

1) 只对入口任务进行如下的副本执行判断机制；

2) 首先选择对入口任务产生最小EFT的处理器p_j执行入口任务；

3) 对于其余处理器p_i(p_i∈P)，如果有入口任务的直接后继节点(immediate successor)v_n分配p_i执行时，进行如式(7) 的循环判断，如果满足式(7) 则进行p_i处理器上的入口任务复制，否则直接在p_i上执行v_n。

${{W}_{{{V}_{entry,i}}}}＜{{W}_{{{V}_{entry,j}}}}+{{C}_{{{V}_{entry,{{v}_{n}}}}}}$

(7)

当以下两个条件中任意一个满足时，上述循环判断终止：

条件a 所有处理器均已分配任务执行，意味每个处理器p_i的入口副本选择策略已经判断完成；

条件b 所有v_n均已分配处理器执行完毕，意味着不需要入口任务进行传输数据。

3.2.2 插入机制优化策略

插入机制(Insertion-Based strategy)最初由HEFT算法提出，后续的众多调度算法都有采用，但均没有对判定条件进行合理的数学描述并且在存在多个满足插入条件的空闲时间缝隙(Idle Time Slot,ITS)，即任务完成与下一任务开始之间的处理器空闲时，HEFT等算法都只是选择第一个出现的ITS而不是最快完成的。本文对插入机制进行优化并详细描述如下：

1) 在每次分配任务执行后，更新每个处理器上的ITS队列。

2) 当任务v_i进行处理器分配时，首先搜寻所有ITS，找出可以满足条件c并同时满足条件d的所有ITS。

3) 如果存在唯一一个同时满足条件c和d的ITS，则直接进行插入操作。

4) 如果存在多个同时满足条件c和d的ITS，则选取产生最小EFT的ITS进行插入执行任务v_i；

5) 当不存在任何同时满足条件c和d的ITS时，不执行插入机制，对任务v_i进行下文的SFT分配策略。

上述策略判断条件描述如下：

条件c w_i,j≤ITS，即在该ITS所在处理器p_j上执行任务v_i时间小于存在的ITS空闲时间长度；

条件d v_i在该ITS所在处理器p_j上的EFT小于或等于该ITS的下限时间点，即可以满足任务先后续关系。

3.2.3 直接后继节点完成时间分配策略

对于所有决定了调度优先级的任务进行具体的处理器分配时，当经过上文提到的入口副本选择和插入机制优化策略后，仍未分配处理器的任务v_i遵照直接后继节点完成时间SFT(immediate Successors Finish Time)分配策略。相比传统算法^{[3-4, 6]}只考虑最快EFT进行处理器分配，本文算法策略考虑直接后继节点的完成时间对于整个调度结果的影响，避免了单纯考虑任务自身最快完成时间EFT进行选择处理器时可能引起后续通信数据传输时间过长的不合理问题。首先给出SFT计算公式，如式(8) ：

$SFT\left( {{v}_{i}},{{p}_{k}} \right)=\underset{{{v}_{j}}\in succ\left( {{v}_{i}} \right)}{\mathop{\max }}\,\left\{ \underset{{{p}_{w}}\in P}{\mathop{\min }}\,\left[ w\left( {{v}_{j}},{{p}_{w}} \right)+{{c}_{i,j}} \right] \right\}$

(8)

当任务v_i与直接后继节点v_j在同一处理器上执行，即p_w=p_k时，c_i,j=0，对于出口节点,SFT(v_i,p_k)为0。任务v_i进行处理器分配时，选择满足EFT(v_i,p_k)+SFT(v_i,p_k)的和为最小值的处理器p_k执行。

3.3 HSFT详细伪代码

HSFT详细伪代码如下。

输入:DAG任务联通矩阵与计算开销矩阵，任务集V,处理器集合P。

输出:调度结果,调度完成时间。

1)   从出口节点开始向上按照式(6) 计算每个任务的rank_u值

2)   将所有任务通过rank_u值降序排列形成调度队列

3)   While 调度队列存在任务时 do

4)   选择调度队列最上面的任务v_i

5)   If 该任务为入口任务

6)   执行本文3.2.1 节的入口任务选择副本策略

7)   Else(任务v_i 不是入口任务)

8)   if 满足本文3.2.2节的插入机制优化策略条件

9)   对任务v_i进行插入ITS处理器分配

10)   else

11)   for 每个处理器p_k∈P do

12)   按照式(4) 和(8) 计算任务v_i的EFT和SFT

13)   end

14)   分配v_i到产生最小EFT+SFT的处理器p_k上执行

15)   End if

16)   End if

17)   更新调度队列

18)   End while

3.4 算例分析

由图 1的DAG例图求得的各算法调度结果如图 2，对于该算例的调度结果，本文算法HSFT为117，PEFT算法调度结果为122，SDBATS调度结果为126，HEFT调度结果为133。由此可以看出，在与PEFT算法的文献^[5]使用同样结构和参数的DAG模型下，HSFT仍然可以得到最为优秀的调度结果。值得一提的是，HSFT对于处理器p₁进行了入口任务副本选择策略，选择处理器p₂来执行入口任务，并且对其他处理器进行了判断。

图 2(a)中的p₁处理器上的D₁即为入口任务的副本，对于处理器p₃，由于判断在该处理器上执行入口任务副本并不会比在p₂上执行完入口任务后再把数据传输到p₃得到更好的调度结果，因此算法没有对其进行入口任务副本。这一点与图 2(c)中的SDBATS算法对于所有处理器都进行了入口任务副本产生了明显的区别，HSFT也因此得到了更好的调度结果。

HSFT得到的各节点的rank_u值降序排列如表 1，即以此权值的大小决定任务的调度优先级。各算法的节点调度优先顺序与最终调度长度如表 2。另一个使得HSFT优于其他算法调度结果的原因是对于任务3得到了相对于任务4更优先的调度顺序。这是由于本文3.1节改良的优先级计算公式，使得计算开销差异较大或平均出度通信开销较大的任务都可以得到更为公平的调度顺序。

对于V个任务和P个处理器，HSFT和比较算法HEFT、SDBATS及PEFT有着同样的时间复杂度O(v²,p)。具体分析如下：当计算rank_u值时其时间复杂度为O(v²*p)，在分配处理器阶段计算EFT的复杂度为O(v*P)，计算SFT的复杂度为O(v²*p)，因此整个算法时间复杂度为O(v²*p+v*P+v²*p)，即为O(v²,p)。

4 实验与结果分析

本章给出在随机生成DAG实验中，HSFT和上述各个比较算法的具体实验结果。首先介绍几个衡量实验性能的比较参数。最常见的衡量DAG调度结果的参数就是式(2) 介绍的调度长度makespan，但是由于DAG任务节点数与属性不同，有必要给出一个参考标准，使用调度长度与理论调度完成时间的比值，即为调度长度比(Schedule Length Ratio,SLR)，如式(9) 所示：

$SLR=makespan/\left( \sum\limits_{{{v}_{i}}\in C{{P}_{MIN}}}{\underset{{{p}_{j}}\in P}{\mathop{\min }}\,\left( {{w}_{i,j}} \right)} \right)$

(9)

式(9) 的分母为所有关键路径节点在各自最快完成的处理器上执行时间累加值，完全忽略在不同处理器间通信所产生的传输时间，即调度的理想下限时间。因此在实验比较中，效果更好的调度算法会得到更小的SLR值，但SLR永远不会小于1。

加速比为串行调度时间与并行调度时间之比，见式(10) ，即为当所有任务在同一处理器顺序完成的时间最小值除以算法的调度时间：

$Speedup=\left( \underset{{{_{{{p}_{j}}}}_{\in P}}}{\mathop{\min }}\,\left\{ \sum\limits_{{{v}_{i}}\in V}{{{w}_{i,j}}} \right\} \right)/makespan$

(10)

效率值(Efficiency) 定义为加速比除以参与运行的处理器个数。理论上，随着处理器的个数增加，加速比会越来越大，因此采用效率值作为评估参数可以更合理地判断算法的效率，越好的算法其调度效率值越高。

本文使用本课题组研发的DAG生成仿真程序^[15]，生成用于随机DAG实验中的测试用例。采用和文献^[5]同样的随机生成DAG参数，具体包括：任务节点数v(number of tasks)、形状参数fat(shape parameter)、匀称参数regularity(symmetry parameter)、边密度参数density(number of edge factor)、跳跃跨度jump(the degree of leaping)、通信计算比CCR(Communication to Computation Ratio)以及异构计算差异参数η(Range percentage of computation cost)。

改变fat值可以生成各种不同形状的DAG任务图，使用${\sqrt{v}}/{fat}\;$来计算DAG的层数，每层的节点宽度由$\sqrt{v}\times fat$求得。即当fat值越大时，DAG每层的节点并行度越高；反之，DAG的层数越多，每层节点数越少，任务的并行度越低。

density值用来定义两层DAG节点之间边的数量，低的取值意味着整个DAG生成的边越少，反之取高的值会产生更多的边。边密度参数确定了各层节点间的连通性，即影响出度通信开销权值和对通信密集型任务的判断。

regularity值用来定义每层节点的均匀度，取值越小会造成各层节点的数量差异过大，即不均匀。反之则会让各层之间的节点数量相近，整体得到一个均匀的DAG结构。

jump值表示一个节点向下联通的跳跃度，即从当前节点所在层向下的跨度，当jump取1时，每个节点正常连接下一层节点，取2即可以跨过1层而连接下2层的节点。

CCR用于决定DAG任务的通信开销与计算开销之间的比例关系，通常来说，该值由所有通信开销矩阵的有效联通边的均值与计算开销矩阵所有有效值的均值相比得到，CCR值较大表示DAG为一个通信密集型程序；反之，CCR值较小，即为计算密集型DAG。

异构计算差异参数η反映了异构计算环境下处理器之间的速度差异。通常在一个[0,2*W_dag]的范围内，随机选取每个任务v_i计算开销的初始值w_i，其中W_dag是最初给定的整个DAG计算开销初始值。每个任务v_i在每个处理器p_j上的计算开销w_i,j则在式(11) 的范围内选取：

${{w}_{i}}\times \left( 1-\eta /2 \right)\le {{w}_{i,j}}\le {{w}_{i}}\times \left( 1+\left( 1-\eta /2 \right) \right)$

(11)

本文实验各DAG生成参数取值范围为：v={10,20,30,40,50,60,70,80,90,100,200,300,400,500}；CCR={0.1,0.5,0.8,1,2,5,10}；η={0.1,0.2,0.5,1,2}； jump={1,2,4}；regularity={0.2,0.8}； fat={0.1,0.4,0.8}；density={0.2,0.8}；处理器个数Processors={4,8,16,32}。上述参数组合共生成70 560个DAG模型，对于每个DAG模型再随机生成10个具体DAG，因此共有705 600个随机DAG用于实验测试。具体实验结果如图 3~6：图 3给出了不同任务数v下的各算法调度结果的平均SLR；图 4给出不同通信计算比CCR下的各算法调度结果的平均SLR；图 5给出不同异构参数η下的各算法调度结果的平均SLR；图 6给出了不同处理器数下各算法调度的平均效率值。本文对所有实验结果进行了标准偏差的实验误差估计，其误差范围大致在3%到6%之间。

图 3可以看出，在任务数逐渐增大的情况下，本文算法在SLR上要比其他算法都小，对比PEFT算法，在10任务时优势接近11%，在500任务时优势也达到6%左右。图 4和图 5可以看出，在CCR和异构参数不断增加的情况下，本文算法的SLR均小于其他算法，并且随着参数取值的增加，算法的优势逐渐明显。在最高的CCR取值时，优势达到8%左右；在最高的异构参数取值为2的情况下，优势也接近5%。虽然本文算法目标是异构差异度较大情况下的调度优化，但通过图 5实验结果可以看到，算法在异构差异较小的情况下相对其他算法也有一定的优势。从图 6可以看出在不同处理器数目下，本文算法效率值也高于其他算法，优势最高可以达到9%左右。PEFT算法由于通过预测机制，优先考虑子节点在串行权值较大情况下的调度优先性，所以在比较窄的DAG中占有一定优势，但是在并行度比较大的DAG中，这个优势就并不明显，尤其在计算开销差异较大和子节点通信并行度较高的情况下，PEFT算法往往不占优势，甚至并不优于HEFT算法。值得一提的是，为了更好地与PEFT算法进行比较实验，本文的随机DAG生成参数选取与PEFT文献完全一样。对于fat值，PEFT算法文献选取参数没有超过1，意味着生成的DAG是过于串行的，这有利于该算法的调度结果，而事实上这样的随机参数选取范围不尽合理。SDBATS算法在大部分情况下得到的调度结果优于HEFT，但是由于算法本身缺少插入机制，以及过于注重计算开销差异，导致在通信开销较大情况下并没有优势。HEFT算法作为最经典的调度算法，其调度的效果相对比较稳定。

总之，在各种参数的DAG模型下，HSFT的SLR和效率值都要好于其他比较算法，尤其在异构度大的情况下，HSFT的优势更加明显，这是因为本文算法更注重计算开销的差异性以及计算开销与通信开销两者间的平衡，并且采用更合理的SFT处理器选择策略。

5 结语

本文提出了一种异构环境下的DAG调度算法——HSFT，在考虑充分平衡计算与通信差异对优先级影响的基础上，以直接后继节点的完成时间作为处理器选择的衡量标准，算法在异构差异度较大的DAG调度中具有明显的优势。在各种参数的随机DAG实验下，HSFT的调度长度、调度比SLR和效率值都要好于现有的PEFT、SDBATS及HEFT算法；同时，HSFT具有和本文其他比较算法相同的时间复杂度O(v²,p)。