徐洪智 李仁发 曾理宁

1(湖南大学信息科学与工程学院 长沙 410082) 2(吉首大学软件学院 湖南张家界 427000) (xuhongzhi9@163.com)

近年来，嵌入式系统，特别是信息物理融合系统(cyber-physical system, CPS)[1]已在智能交通、智能电网、智能家居、医疗保健、航空航天、大型建筑状态监控等众多领域得到广泛应用[2-4].这些系统普遍具有异构特征，它们利用高速网络将不同的处理器单元互联执行并行应用程序.从系统设计的角度看，并行程序由具有先后约束关系的任务构成，通常被表示成有向无环图(directed acyclic graph, DAG)，程序运行时将各任务按一定的逻辑次序分配到相应的处理器执行.以往基于异构系统调度DAG的研究基本都是为了缩短调度长度，而对于很多嵌入式系统而言，可靠性是系统的一项重要质量指标，尤其在安全关键的实时系统设计中极其重要，可靠性目标必须被满足.可靠性是系统正确运行的概率，由于系统硬件自身原因、外部电磁干扰等，系统在运行时可能会发生错误，影响系统的可靠性[5-7].为提高系统可靠性，一般通过资源冗余的方式容忍系统运行过程中发生的错误，如将任务复制到不同的处理器上执行或当任务发生错误后重新执行[8].

对于很多嵌入式系统而言，系统资源往往是有限的，如有许多系统可能工作于能量受限的环境，能耗过高将会影响电池或系统的寿命[9-10].一般地，当我们应用资源冗余的方式提高系统可靠性时会消耗更多的系统资源，而过多限制资源的使用则会降低系统的可靠性.因此，在系统设计时需要权衡可靠性与资源消耗的问题，在满足系统可靠性目标的前提下尽量节省系统资源.基于这些分析，本文主要研究异构系统执行并行任务，在给定系统可靠性目标的情况下如何尽量节省系统资源，主要贡献包括4方面：

1) 将应用系统的可靠性目标转换为单个任务的可靠性目标，分别给出了任务非复制和任务复制情况下单个任务可靠性目标的计算方法；

2) 设计了一个任务非复制的可靠性约束下资源最小化算法，当给出的系统可靠性目标不大于系统可达到的最大可靠性时，该算法能将任务分配到合适的处理器并使可靠性达到目标要求；

3) 由于任务非复制算法不能满足系统更高可靠性要求，设计了2个可靠性目标约束下最小化资源的启发式算法；

4) 分别应用随机任务和实际任务对算法进行模拟仿真，验证了本文算法的有效性.

1 相关工作

基于异构系统的并行任务调度，经典的算法如异构最早完成时间(heterogeneous earliest finish time, HEFT)算法[11]、关键路径(critical-path-on-a-processor, CPOP)算法[11]等，基于这些算法人们提出了一些新的算法，如双螺旋结构遗传算法(double-helix structure genetic algorithm, DHSGA)[12]等，这类算法的目的是尽量缩短调度长度.另有一些学者研究了调度过程中系统资源利用的问题，如Qiu等人[13]研究了异构系统任务分配时在满足软/硬时间约束下的资源最小化问题.Huang等人[14]研究了异构系统调度随机到达的任务时能量资源利用的问题，提出一种基于拉格朗日理论的功率分配和负载均衡策略.Xie等人[15]基于异构系统调度先后约束关系的任务，在满足任务截止期限的情况下最小化系统能耗.这些研究没有考虑系统的可靠性问题.

目前，有许多学者研究了系统能量资源消耗与可靠性问题.如针对单处理器系统，Zhu等人[6]基于抢占最早截止期限优先(earliest deadline first, EDF)策略分别研究了实时周期性任务静态和动态可靠性感知功耗管理(reliability-aware power management, RA-PM)问题，证明了静态RA-PM是NP难问题.同时Zhu还在文献[7]中假设任务松弛时间不小于任务最坏计算时间的情况下，利用松弛时间调低任务的执行电压实现节能.为了使长任务能够利用松弛时间，他们引入了程序检查点(checkpoint)技术，将长任务分解为小的任务段，然后利用松弛时间节能并保证任务的可靠性.Lin等人[16]在保证系统可靠性的同时通过调节处理器的速度和关闭处理器节省能耗.Li等人[17]基于帧的实时任务集在保证系统可靠性的前提下使能耗最小化.Zhao等人[18]基于单处理器系统调度有约束关系的任务，在给定能量预算的前提下使系统的可靠性最大化.文献[19]针对有截止期限要求的DAG任务，应用共享恢复(shared recovery)技术保证系统的可靠性并降低能耗.

近年来，由于多处理器系统在各个领域的广泛应用，有很多学者研究了异构系统调度DAG任务的可靠性与资源消耗的问题，如MaxRe算法[20]和RR[21]算法分别应用任务复制的方法保证系统的可靠性.Zhang等人[22]基于异构多处理器系统调度DAG，提出能量约束下的可靠性最大化算法，该算法包括任务优先级的确定、频率选择和处理器分配3个阶段，用以权衡系统的可靠性与能耗.Yi等人[23]针对异构多处理器系统可靠性保证与时间约束下的任务调度问题，首先在多项式时间内求解简单路径和树结构(simple-path and tree-structured)任务图问题，进而应用整数线性规划求解DAG调度问题，然后提出DAG_Heu算法求近似最优解.Xie等人[24]基于异构计算系统提出满足可靠性目标并最小化系统代价的算法，但该文没有应用任务复制技术进一步提高系统的可靠性.文献[25]基于能量收集系统(energy harvesting)供电的多核嵌入式系统，综合考虑任务执行时间、瞬时错误和永久错误，利用调度窗口能量预算对任务进行调度.文献[26]基于多核平台调度周期任务，通过调整每个任务复制的数量和执行频率满足系统可靠性要求并尽量节能.本文研究异构系统执行DAG任务，考虑处理器资源和网络资源消耗，在满足系统可靠性目标的前提下尽量节省系统资源.

2 系统模型与问题定义

2.1 应用程序模型

本文研究并行应用程序运行于异构多处理器系统，处理器节点用集合PN={pn1，pn2,…,pnm}表示，其中m为处理器节点数.假定每个处理器节点的处理能力不同，这些处理器节点通过网络进行连接.将运行于处理器节点上的应用程序表示为有向无环图DAGG=(T,C)[11]，现对T,C描述如下：

T表示G中的任务(DAG中的顶点)，任务ti∈T，其中1≤i≤n.因为任务执行过程中具有先后约束关系，用C表示任务间的先后约束关系及通信时间(DAG中的边)，ci,j∈C表示任务ti与任务tj之间存在先后约束关系，任务tj必须在任务ti执行完之后才能执行，ci,j的值表示任务tj与任务ti不在同一个处理器上执行时的通信时间.若任务tj与任务ti在同一个处理器上执行，则ci,j=0.

一个经典的DAG如图1所示[11,15,24,28]，c1,2∈C表示任务t2必须在任务t1之后执行；c1,2=18表示任务t2与任务t1不在同一个处理器上执行时，从任务t1所在的处理器传输数据到任务t2所在的处理器需要的时间为18；如果任务t2与任务t1在同一个处理器上执行，则传输数据的时间为0.定义parent(ti)表示任务ti的直接前驱任务集，child(ti)表示任务ti的直接后继任务集，将没有前驱任务的任务称为tentry，将没有后继任务的任务称为texit.如果G中有多个tentry或texit，我们可以构造不需要实际执行的虚拟任务表示tentry或texit.因为处理器异构，任务ti在每个处理器上的最坏执行时间(worst-case execution time, WCET)可能不同，定义一个n行m列的矩阵W=(wi,j)表示G中的任务在各个处理器上的执行时间，wi,j表示任务ti在处理器pnj上执行时的WCET.图1中的任务在3个处理器上的WCET如表1所示，任务t1在3个处理器上执行的最坏时间分别为14，16和9个单位时间.

Fig. 1 Example of a DAG with ten tasks图1 10个任务的DAG图

Taskpn1pn2pn3t114169t2131918t3111319t413817t5121310t613169t771511t851114t9181220t1021716

2.2 资源消耗模型

根据文献[24,27]，系统资源消耗与任务执行时间成比例关系，如果一个任务的执行时间为et，则消耗的资源为rcr×et，其中rcr为单位时间的资源消耗率.因为不同处理器的资源消耗率可能不同，因此，定义集合RCRP={rcrp1,rcrp2,…,rcrpm}表示系统中各处理器单位时间的资源消耗率，其中rcrpi表示处理器pni单位时间的资源消耗率.根据资源消耗关系，如果G中的任务ti在处理器pnj上执行，消耗的处理器资源可表示为

Costpro(ti,pnj)=rcrpj×wi,j.

(1)

考虑到G中具有先后约束关系的任务可能在不同的处理器上执行，任务之间存在通信，同样，设通信过程中消耗的资源与通信时间成比例关系，因此定义处理器之间单位时间的通信消耗率为rcrc.若将任务ti分配给处理器pnj，消耗的通信资源与ti的父任务tx是否在pnj上执行有关，可表示为

(2)

根据式(1)(2)可知，将任务ti分配给处理器pnj，消耗的处理器资源与通信资源之和为

Cost(ti,pnj)=Costpro(ti,pnj)+
Costcom(ti,pnj).

(3)

2.3 错误模型

系统运行过程中出现的错误一般分为瞬时错误和永久错误，而瞬时错误更加常见[5-7,16,22,24,26]，所以类似于这些研究，本文只考虑瞬时错误.系统的可靠性是系统正确运行的概率，如果系统运行时出现的瞬时错误服从泊松分布，处理器执行任务时的可靠性表示为R(t)=e-λ t，其中λ是处理器执行单位时间的平均错误率.由于处理器系统异构，不同的处理器的λ值可能不同，因此，定义λj表示处理器pnj执行单位时间的平均错误率，这时G中的任务ti在处理器pnj上执行，其可靠性表示为

R(ti,pnj)=e-λj×wi,j.

(4)

2.4 系统资源消耗与可靠性计算

本文主要研究任务非复制和复制2种情况下满足系统可靠性目标并最小化资源消耗的问题.现对系统资源消耗与可靠性的计算方法分析如下.

根据2.2节和2.3节所述，如果将任务ti分配到处理器pnj上执行，其可靠性为R(ti,pnj)，发生错误的概率为1-R(ti,pnj).如果将任务ti及其复制版本分配到多个处理器上执行并将这些处理器组成一个集合Replica(ti)，这时任务ti的可靠性及消耗的资源可分别表示为

(5)

和

(6)

类似于文献[22,24]，本文假定网络传输是可靠的，即不考虑网络通信过程中的错误.当G中所有的任务分配并执行完后，系统的可靠性及消耗的资源总量可分别表示为

(7)

和

(8)

2.5 问题定义

给定一个异构多处理器系统和DAG任务G，本文定义的问题是：如果给出系统的可靠性目标为Rgoal(G)，怎样将G中的任务分配到合适的处理器使系统可靠性R(G) ≥Rgoal(G)，并且使系统资源Cost(G)尽可能小，该问题形式化描述如下：

其中，n为G中的任务数.

3 调度分析

3.1 任务优先级

调度过程中必须保证任务执行的先后次序，前驱任务先执行，后继任务后执行，为了满足这个条件，本文使用Rank的概念生成任务的拓扑次序[11,15,22,24,28]，Rank定义如下：

(9)

Table 2 Rank Value of the Tasks in Fig.1表2 图1各个任务的Rank值

3.2 任务最早完成时间

一个任务的最早完成时间依赖于其开始时间，在DAG调度中，如果将任务ti分配到处理器pnj，则任务ti必须等所有的前驱任务parent(ti)执行完并将相关数据传送到所在的处理器才能开始执行.因此，任务ti的最早开始时间(earliest start time,EST)和最早完成时间(earliest finish time,EFT)可分别表示为

(10)

和

EFT(tx,pny)=EST(tx,pny)+wx,y.

(11)

3.3 任务可靠性目标的确定

在满足任务的先后约束关系之后，调度过程中还要保证系统的可靠性目标被满足.直观地看，系统的可靠性由G中的n个任务的可靠性决定，所以类似于文献[20-21,24].当进行任务调度时，先确定单个任务的可靠性目标，然后再将任务分配到满足可靠性要求的处理器.如果给出的可靠性目标Rgoal(G)小于或等于任务非复制情况下系统可达到的最大可靠性，则不需要进行任务复制，否则需要进行任务复制才能使系统达到可靠性目标要求.以下分任务非复制和复制的情况进行讨论.

3.3.1 非复制情况下任务的可靠性目标

我们先分析系统可达到的最高可靠性.如果将任务ti分配到可靠性最高的处理器上执行，则其可靠性为

(12)

当G中所有的任务都选择可靠性最高的处理器执行，系统的可靠性将最高，可表示为

(13)

如果不进行任务复制，当给出的系统可靠性目标要求Rgoal(G) ≤Rmax_nonrep(G)时，本文将系统的可靠性目标转换为单个任务的可靠性目标.

对于G中的任务，虽然处理器异构，但任务本身的计算量也存在差异，计算量大的任务在各个处理器上的执行时间会相对较长，计算量小的任务在各个处理器上的执行时间会短一些.从式(4)可知，单个任务的可靠性与执行时间有关，执行时间越长可靠性将越低.所以本文用任务的平均最坏执行时间为参考预确定任务的可靠性目标.因此，定义总参考时间(total reference time,TRT)为

(14)

由于不进行任务复制，给任务ti预确定的可靠性目标不能大于Rmax_nonrep(ti)，否则将找不到合适的处理器执行任务ti.所以，我们先算出系统可靠性目标与系统最大可靠性的比值GRM，用GRM做参考计算任务ti预确定的可靠性目标.GRM表示为

(15)

因为给出的可靠性目标Rgoal(G)≤Rmax_nonrep(G)，所以GRM(G)≤1.现在任务ti的可靠性目标可预确定为

(16)

因为GRM(G)≤1，所以RG RM(ti)≤Rmax_nonrep(ti).如果任务被分配之前已按Rank值拓扑排序，任务执行的序号为1,2,…,n，设在调度过程中已经分配完的任务为{t1,t2,…,ti-1}，没有被分配的任务为{ti+1,ti+2,…,tn}，当前准备分配的任务为ti，这时给任务ti预确定的可靠性目标为

(17)

当把G中的任意一个任务ti分配到处理器时，只要ti的可靠性大于等于式(17)中的Rpgoal(ti)，即可使系统的可靠性达到目标要求.

定理1. 在非复制的情况下，当给出的可靠性目标Rgoal(G)≤Rmax_nonrep(G)时，应用式(16)(17)对任务的可靠性目标进行预确定，在调度时每个任务总能分配到合适的处理器并且使系统满足可靠性目标要求.

证明. 应用数学归纳法进行证明.

1) 当分配第1个任务，即i=1时，根据式(17)，第1个任务的可靠性目标为

(18)

所以能找到合适的处理分配第1个任务，当将第1个任务分配到处理器后，其实际可靠性为

(19)

余下的任务按式(16)预确定可靠性，则系统的可靠性为

(20)

所以当i=1时，定理1成立.

2) 假设分配完第k个任务后，定理1仍然成立，即

(21)

3) 如果第k+1个任务时按式(17)分配，则第k+1个任务预确定的可靠性目标为

(22)

根据式(21)可知

(23)

将式(23)带入式(22)，得

(24)

所以能找到合适的处理器分配第k+1个任务，当第k+1个任务分配到处理器后，第k+1个任务的实际可靠性为

(25)

这时系统的可靠性为

(26)

根据以上步骤，可知定理1成立.

证毕.

3.3.2 复制情况下任务的可靠性目标

如果给出的系统可靠性目标大于Rmax_nonrep(G)，则需要应用任务复制技术才能达到系统可靠性目标要求.进行任务复制可提高单个任务的可靠性从而提高整个系统的可靠性，但在调度过程中仍然需要确定每个任务的可靠性目标才能确定复制哪些任务.因为式(17)中的单个任务的可靠性目标是基于式(15)的GRM(G)≤1设计的，如果给出的Rgoal(G)>Rmax_nonrep(G)，式(17)计算任务可靠性目标的方法将不再适应.因此，对于任务复制的情况，需要重新给每个任务分配可靠性目标，受式(4)结果的影响，平均执行时间长的任务预确定的可靠性目标应该相对低一些.所以本文直接根据任务ti的平均最坏执行时间在TRT(G)中所占的份额确定任务ti的可靠性目标，因此，给任务ti预确定的可靠性目标Rreplica(ti)计算为

(27)

在进行任务调度时，当前任务ti的可靠性目标为

(28)

4 资源最小化算法

4.1 资源最小化非复制算法

根据3.1节中任务Rank值的计算方法，首先可以算出G中各任务的优先级，然后根据优先级次序将任务分配到合适的处理器上执行.对于任意一个任务ti，先根据3.3节中介绍的方法算出该任务的可靠性目标，然后将它分配到满足可靠性目标要求并且资源消耗最小的处理器上执行.因此，设计一个可靠性约束下的资源最小化算法(minimizing resource consumption with reliability goal, MRC).

算法1. MRC算法.

输入：PN={pn1，pn2,…,pnm}，G，Rgoal(G)；

输出：R(G)，Cost(G).

① 遍历G，计算Rank；

② 将任务根据Rank非增排列至队列ReadyQ；

③ whileReadyQ≠∅

④ti=ReadyQ.out()；

⑤ 根据式(17)计算Rpgoal(ti)；

⑥cost=∞；*cost为临时变量*

⑦ for each processorpnj∈PNdo

⑧ ifR(ti,pnj)≥Rpgoal(ti) then

⑨res=Cost(ti,pnj)；*式(3)*

⑩ ifcost>resthen

算法1首先遍历G计算Rank，并将任务按Rank非增排列至队列ReadyQ.行③～while循环为任务调度过程，将每个任务分配到合适的处理器.对于任意一个任务ti，首先计算可靠性目标(行⑤)，然后遍历处理器(行⑦～)，寻找满足可靠性要求且资源消耗最小的处理器pnj，然后将ti分配给pnj(行).行～分别计算系统的实际可靠性和消耗的资源总量.

算法1的时间复杂度主要由行③⑦⑨决定.其中，行③遍历G中所有任务，时间复杂度为O(n)；行⑦遍历所有处理器，时间复杂度为O(m)；行⑨需要访问任务ti和所有前驱任务之间的通信边，时间复杂度为O(ei)，其中ei为任务ti的前驱任务数.所以算法1在调度过程中的时间复杂度为O(n×m×ei)=O(m×e)，其中e为DAG中的边数.如果DAG为稠密图，一个任务的前驱任务数接近于任务总数，则算法1的时间复杂度为O(n2×m).所以，算法1的时间复杂度与经典算法HEFT[11]的时间复杂度相同.

4.2 MRC算法(算法1)示例

应用文献[24]中的参数，将图1中3个处理器的参数设置如表3，单位时间通信资源消耗率rcrc=1，可算出系统最大可靠性为0.974 335，如果将可靠性目标设为0.95，应用MRC进行调度，结果如表4所示.

Table 3 Parameters of Three Processors表3 3个处理器参数表

Table 4 Processor Assignments for Tasks Using MRC表4 MRC调度结果

从表4可知，算法1的调度长度为96，系统可靠性为0.958 773 9，超过可靠性目标要求，消耗的资源为791，优于文献 [24]中的结果.因为算法1只能将单个任务调度到一个处理器上执行，如果给出的系统可靠性目标超过Rmax_nonrep(G)，即使将每个任务都分配到可靠性最高的处理器仍然不能使系统达到可靠性目标要求.因此，4.3节我们应用任务复制技术提高系统的可靠性.

4.3 基于复制的调度算法

因为本文主要关注系统设计阶段，所以运用严格的调度技术[29]，即一个任务只有等它的前驱任务及其所有复制都执行完后才可以开始执行，所以先将任务ti的前驱任务的最早完成时间(earliest finish time of predecessors,EFTP)表示为

(29)

式(29)表示任务ti的所有前驱任务的所有复制的最迟完成时间，这时任务ti的一个复制在处理器pnj上的最早开始时间可表示为

(30)

在调度过程中，首先根据式(27)(28)算出任务ti的可靠性目标，然后应用基于复制的调度技术从处理器集合中选择多个处理器执行任务ti并且使资源消耗最小化，设计一个可靠性约束下资源最小化的复制调度算法(minimizing resource consump-tion with reliability goal using replication technique, MRCR).

算法2. MRCR算法.

输入：PN={pn1，pn2,…,pnm}，G，Rgoal(G)；

输出：R(G)，Cost(G).

① 遍历G，计算Rank；

② 将任务根据Rank非增排列至队列ReadyQ；

③ whileReadyQ≠∅

④ti=ReadyQ.out()；

⑤ 根据式(28)计算Rpgoal(ti)；

⑥ 调用算法SelectProc计算Replica(ti)；

⑦ 将任务ti分配到Replica(ti)中的所有处理器；

⑧ end while

⑨ 根据式(7)计算R(G)；

⑩ 根据式(8)计算Cost(G).

算法2首先计算各任务的Rank值，然后将任务按Rank非增排列至队列ReadyQ.在进行调度时，先计算任务ti的可靠性目标，然后调用算法SelectProc计算任务ti分配的处理器集合并将任务ti及其副本分配到这些处理器.

算法SelectProc从处理器集合中选择多个处理器执行任务ti，在满足可靠性目标的前提下使资源消耗最小化，该问题类似于0-1背包问题，描述如下：

其中xj∈{0,1}.

该问题可应用回溯法寻找最优解，在此不再详述.当处理器器的数目较多时，时间复杂度很大，设计2个启发式算法确定任务ti分配的处理器集合，这2个算法分别如算法3和算法4所示.

算法3. SelectProc1算法.

输入：PN={pn1，pn2,…,pnm}，Rpgoal(ti)；

输出：Replica(ti).

①k=1；

② 将处理器按执行任务ti的可靠性降序排列至RelDown；

③pof=1-R(ti,RelDownk)；

④ whilepof>1-Rpgoal(ti) do

⑤ 将RelDownk加入Replica(ti)；

⑥ if (k++)>mthen

⑦ return；

⑧ end if

⑨pof=pof×(1-R(ti,RelDownk))；

⑩ end while

Rpgoal(ti)且资源消耗最小的处理器

RelDownj；

算法3加入一个处理器到Replica(ti)的基本思想是：如果余下的任何一个处理器加入Replica(ti)都不能满足可靠性要求，则优先选择可靠性高的处理器加入Replica(ti).如果有一些处理器能够达到可靠性要求，则优先选择资源消耗小的处理器加入Replica(ti).算法3中行①初始化变量k;行②将各处理器按执行任务ti的可靠性进行降序排列至RelDown序列;行④～⑩while循环表示如果将任务ti复制到当前处理器RelDownk仍不能满足可靠性要求，则将处理器RelDownk加入Replica(ti);行⑥～⑧表示如果将任务ti复制到所有的处理器仍不能满足可靠性要求，则返回;行～表示将满足可靠性要求且资源消耗最小的处理加入Replica(ti).

算法3先要计算任务ti在各处理器上执行的可靠性，对处理器进行排序，时间复杂度为O(mlbm)；然后while循环(行④～⑩)和for循环(行～)总共要遍历所有处理器一次，而for循环要选择资源消耗最少的处理器，因此，行④～的时间复杂度为O(m×ei)，其中ei为任务ti的直接前驱数.可知，算法3的时间复杂度为O(m×ei+mlbm).

如果算法2调用算法3，因为每个任务都要选择处理器，所以算法2的时间复杂度为O(n×(m×ei+mlbm))，即O(m×e+n×mlbm)，其中e为DAG中的边数.

算法4. SelectProc2算法.

输入：PN={pn1，pn2,…,pn|PN|}，Rpgoal(ti)；

输出：Replica(ti).

①k=1；

② 将各处理器按执行任务ti消耗的资源升序排列至CostUp；

③ 将CostUpk加入Replica(ti),调用式(5)计算R(ti)；

④ whileR(ti)

⑤ if (k++)>mthen

⑥ return；

⑦ end if

⑧ 将CostUpk加入Replica(ti),调用式(5)计算R(ti)；

⑨ end while

算法4的基本思想是依次将资源消耗最小的处理器加入Replica(ti)集合，直到满足可靠性要求为止.算法4中行①初始化变量;行②将各处理器按执行任务ti消耗的资源按升序排列至CostUp序列;行④～⑨while循环依次选择资源消耗最小的处理器CostUpk加入Replica(ti);行⑤～⑦表示如果将任务ti复制到所有的处理器仍不能满足可靠性要求，则返回.

算法4首先计算任务ti在各个处理器上消耗的资源，时间复杂度为O(m×ei)，其中ei为任务ti的直接前驱数；然后对处理器进行排序，时间复杂度为O(mlbm)；最后遍历所有的处理器直到可靠性满足要求，时间复杂度为O(m).基于这些分析，算法4的时间复杂度为O(m×ei+mlbm)，该复杂度与算法3的时间复杂度相同.因此，如果MRCR调用算法4，时间复杂度也为O(m×e+n×mlbm).

4.4 MRCR算法(算法2)示例

本节给出算法2示例，以下将MRCR调用算法3称为MRCR-1，调用算法4称为MRCR-2，调用回溯法寻找最优处理器称为MRCR-3.沿用4.2节中的参数调度图1中的任务，可靠性目标设为0.98.应用MRCR-1进行调度的结果如表5所示(另外2个算法略).最后，MRCR-1消耗的资源为1 251，系统的可靠性为0.982 575 05；MRCR-2消耗的资源为856，系统的可靠性为0.987 954 83；MRCR-3消耗的资源为805，系统的可靠性为0.982 008 67.

Table 5 Processor Assignments for Tasks Using MRCR-1表5 MRCR-1算法的调度结果

3个算法都能满足系统可靠性要求，MRCR-1算法消耗的资源最多，MRCR-3算法消耗的资源最少.从观察3个算法选择的处理器可知，MRCR-1算法偏向于将任务分配到处理器2和处理器3，即先选择可靠性高的处理器，然后选择资源消耗少的处理器；MRCR-2算法偏向于将任务复制到处理器3和处理器1，即优先选择资源消耗率低的处理器；MRCR-3算法选择满足可靠性目标的处理器组合，在3个处理器选择中没有明显的倾向.

5 实 验

5.1 实验环境及参数

通过仿真实验对本文提出的算法进行测评.基于Windows平台应用C++语言编写一个调度模拟器.将处理器和任务表示为对象并设置标识，根据实验描述生成相应的DAG任务图.初始化时将任务图、处理器参数、每个任务在各处理器上的WCET分别存放至文件，保证各算法使用完全相同的数据，最后分别调用各算法将任务分配至处理器.

因为MaxRe算法[20]、RR算法[21]和MRCRG算法[24]的目标和本文类似，所以将本文算法和这些算法进行比较.现将这3个算法计算单个任务可靠性目标的方法简单介绍如下：

MaxRe算法中任务ti的可靠性目标为

(31)

RR算法中任务ti的可靠性目标为

(32)

MRCRG算法中任务ti的可靠性目标为

(33)

根据文献[5-7,24]中相关参数的取值，本文中任务参数为10≤wi,j≤100,10≤ci,j≤100；处理器资源消耗率为0.1≤rcrpi≤0.9；单位时间通信资源消耗率rcrc=0.2；错误参数0.000 001≤λj≤0.000 009.为了测试不同情况下各个算法的性能，我们运用一些分布式系统中常用的有先后约束关系的任务图，如高斯消元应用、快速傅里叶变换[15,22,24]及随机生成的DAG任务图对算法进行模拟.根据文献[24]中描述ISO 26262中损伤发生的概率级别E3(中等概率)和E2(低概率)确定系统的可靠性目标取值范围为0.9～0.99.

因为MRCRG算法主要针对非复制的情况，所以我们先比较非复制的情况，用本文提出的MRC算法和MaxRe算法、RR算法及MRCRG算法进行比较，然后再比较复制的情况，用本文提出的MRCR系列算法和MaxRe算法、RR算法进行比较.

5.2 非复制情况下各算法的性能比较

Fig. 2 Gaussian elimination application with ρ=5图2 ρ=5的高斯消元DAG

Fig. 3 Resource consumption and actual reliability of algorithms for different number of tasks图3 任务数不同时各算法的资源消耗及可靠性

从图3(b)可知，4个算法都能满足可靠性要求，从消耗的资源来看MaxRe算法消耗的资源最多，RR算法次之，MRC算法消耗的资源最少.从4个算法消耗的资源总量来看，MRC算法消耗的资源是MaxRe算法的59.0%，是RR算法的63.4%，是MRCRG算法的87.9%.从图3(a)可知，当ρ<24时，MRCRG算法与MRC算法消耗的资源没有明显差异，这是因为，任务数较少时系统能达到的最大可靠性Rmax_nonrep(G)相对更高一些，MRCRG算法与MRC算法给任务ti分配的可靠性目标相对于Rmax_nonrep(ti)更低一些，这样2个算法可能会选择相同的处理器执行任务ti；当ρ>24时，任务数变多，系统能达到的最大可靠性相对低一些，MRCRG算法假设后面的任务的可靠性为Rmax_nonrep(ti)，而给前面的任务分配较低的可靠性，所以实际调度时后面的任务必须分配到可靠性较高的处理器，导致选择处理器的机会相对较少，从而资源消耗较多.MRC算法根据任务平均最坏执行时间确定任务的可靠性目标，各任务选择处理器的机会更加均衡.而MaxRe算法给每个任务确定的可靠性目标都相同，RR算法在此基础上有些改进，但由于系统异构的原因，所以效果不如MRCRG算法与MRC算法.

实验2. 基于高斯消元应用比较可靠性目标变化时各算法的性能.本次实验应用8个处理器，ρ=16，即任务数为135，可靠性目标从0.95增加到0.98时，4个算法消耗的资源和实际可靠性如图4所示.

Fig. 4 Resource consumption and actual reliability of algorithms for different reliability goals图4 可靠性目标不同时各算法的资源消耗及可靠性

从图4可知，4个算法都能满足可靠性目标要求，随着可靠性目标的提高，4个算法消耗的资源都增加，相对来说，MaxRe算法消耗的资源最多，RR算法次之，MRC算法消耗的资源最少.从4个算法消耗的资源总量来看，MRC算法消耗的资源是MaxRe算法的69.7%，是RR算法的72.9%，是MRCRG算法的95.0%.该结果和实验1的结果有一些差别，导致这种现象的原因是：随着系统的可靠性目标的提高，当一个任务被分配时，可被选择的处理变得越来越少，所以这些算法消耗的资源总量差异变小.

实验3. 基于快速傅里叶变换比较应用规模变化时各算法的性能.快速傅里叶变换经常被用于分布式系统，为了描述任务节点总数，引入参数ρ，任务总数n=(2×ρ-1)+ρ×lbρ，其中ρ=2y，y为正整数.图5为一个ρ=4的具有15个任务节点的快速傅里叶变换DAG(在调度时构造一个不需要实际执行虚拟任务表示texit).本次实验应用8个处理器，可靠性目标设为0.95，ρ分别为8，16，32，64，即DAG中任务数分别为39，95，223，511时，4个算法的资源消耗和实际可靠性如图6所示.

Fig. 5 D AG of fast Fourier transform application with ρ=4图5 ρ=4的快速傅里叶变换DAG

Fig. 6 Resource consumption and actual reliability of algorithms for different number of tasks图6 任务数不同时各算法的资源消耗及可靠性

实验3的结果类似于实验1和实验2，在ρ=64之前所有算法都能满足可靠性要求，且随着ρ的增加各算法消耗的资源都变多，综合来看，MRC算法消耗的资源仍然最少.

从实验1～3可知，本文提出的算法优于已有的3个算法，特别地，当给出的系统可靠性目标Rgoal(G)相对于系统能达到的最大可靠性Rmax_nonrep(G)更低一些的时候，本文算法在节省系统资源方面将具有非常明显的优势.

5.3 任务复制情况下各算法的性能比较

本节比较本文提出的MRCR系列算法和MaxRe算法、RR算法的性能.

Fig. 7 Resource consumption and actual reliability of algorithms for different number of tasks图7 任务数不同时各算法的资源消耗及可靠性

从图7(b)可知，5个算法的实际可靠性都大于0.96，满足系统可靠性要求.从图7(a)可知，5个算法消耗的资源会随着任务数的增加而增加.从5个算法消耗的资源总量来看，MRCR-1算法消耗的资源总量是MaxRe算法的72.6%，是RR算法的82.4%；MRCR-2算法消耗的资源总量是MaxRe算法的58.5%，是RR算法的66.4%；MRCR-3算法消耗的资源总量是MaxRe算法的57.2%，是RR算法的64.9%.5个算法中，MaxRe算法消耗的资源最多，RR算法消耗的资源次之，MRCR-3算法消耗的资源最少，这是因为MaxRe算法中单个任务的可靠性目标被设定得较高，可被选择的处理器偏少，所以消耗了更多的资源；RR算法每次选择可靠性大的处理器进行任务复制，所以也消耗了较多的资源；MRCR系列算法用任务的平均最坏执行时间为参考确定任务的可靠性目标，从而单个任务的可靠性目标不会过低或过高，可被选择的处理器数更加均衡，所以MRCR系列算法消耗的资源更少.其中，MRCR-3算法选择满足可靠性要求并且资源消耗最小的处理器组合，所以资源消耗最小.MRCR-1算法和MRCR-2算法消耗的资源小于MaxRe算法和RR算法，其中MRCR-2算法消耗的资源和MRCR-3算法比较接近，说明每次将任务复制到资源消耗较小的处理器能有效地节省资源.

实验5. 主要测试DAG的并行度对算法的影响.随机生成具有600个任务的DAG任务，应用16个处理器，a分别为0.25，0.5，1.0，2.0，4.0，每个任务的出度outdegree在[1,4]范围内均匀分布，系统可靠性目标设为0.96.5个算法的资源消耗和实际可靠性如图8所示：

Fig. 8 Resource consumption and actual reliability of algorithms for different a values图8 任务数的并行度不同时各算法的资源消耗及可靠性

当a从0.25增加到4时，任务的并行度约从6增加到98.从图8(b)可知，5个算法都能使系统满足可靠性目标要求.从图8(a)各算法消耗的资源看，无论任务的并行度如何变化，5个算法消耗的资源从大到小依次为MaxRe，RR，MRCR-1，MRCR-2，MRCR-3，且MRCR-2和MRCR-3消耗的资源明显少于其他算法.

实验6. 基于快速傅里叶变换DAG测试应用程序的规模较大时各算法的性能.设ρ=256，即DAG中任务数为2 559，应用32个处理器，可靠性目标从0.95增加到0.99，每次增加0.01.5个算法的资源消耗和实际可靠性如图9所示：

Fig. 9 Resource consumption and actual reliability of algorithms for different reliability goals图9 可靠性目标不同时各算法的资源消耗及可靠性

从图9(b)可知，5个算法都能适用可靠性目标要求，除MaxRe算法之外，其余4个算法的实际可靠性更敏感地随着可靠性目标的改变而改变，其主要原因是这4个算法对单个任务的可靠性要求相对于MaxRe算法更低一些.从图9(a)可知，MaxRe算法和RR算法的资源消耗更多一些，MRCR系列算法消耗的资源相对少一些，MRCR-2算法消耗的资源非常接近MRCR-3算法.

由实验1～6可知，无论是DAG的规模、并行度的变化，还是系统可靠性目标的变化，当不进行任务复制时，MRC算法的性能优于其他几个算法.当应用任务复制技术提高系统的可靠性时，MRCR系列算法的性能优于已有的算法，其中MRCR-2算法消耗的资源非常接近MRCR-3算法.另外，在这6组实验中，MRCR-2算法产生的实际可靠性略高于MRCR-3算法，说明当系统中处理器的数目非常多时，应用MRCR-2算法进行调度既能保证系统的可靠性又能有效地节省系统资源.

6 结 论

随着嵌入式系统应用范围的不断扩大，出现了越来越多的并行应用运行于异构系统.一方面，对于很多安全关键的系统而言，可靠性目标必须被满足；另一方面，资源对于很多系统来说是昂贵的，节省资源对这些系统而言也十分重要.为了保证系统的可靠性要求并节省系统资源，本文设计了3个可靠性目标约束下的最小化资源算法并应用实际DAG任务和随机生成的DAG任务对算法进行了验证.因为本文提出的算法基于异构多处理器系统，所以这些算法可扩展至大多数分布式异构系统中可靠性目标约束下的资源(或代价、能量)最小化的应用.然而，对于系统能耗而言，如果运用电压/频率调整技术降低处理器的执行频率实现节能，任务的可靠性将会降低，在今后的工作中，我们将进一步研究如何保证系统的可靠性目标被满足并且最小化系统能耗的问题.