一种面向节能的星载实时任务动态调度算法研究

李延祺，任 海，白 亮，邱 源，张凤源，牛建伟，李辉勇

(1.北京航空航天大学 计算机学院，北京 100191； 2. 上海航天电子技术研究所，上海 200082)

0 引言

由于星载嵌入式系统在独立的太空环境中工作，所以航天设备需要的电量资源必须能够自给自足。为了延长设备的工作时间，需要在操作系统层面针对各任务进行合理的调度，以统筹各任务的能耗。对于功能强大的嵌入式处理器来说，合理的分配资源以降低整体能耗是十分重要的。因此，星载实时操作系统的性能和能耗之间的平衡问题是使用电池的嵌入式系统所必须面对的重要课题。

为了提高嵌入式系统对电池资源的利用率，满足任务执行的时间约束以及保证系统的实时性，目前国内外大多采用实时电压和频率缩放(DVS)技术。DVS技术可以让嵌入式设备动态适配CPU的当前电压来达到理想中的低能耗状，目前多数嵌入式和分布式系统都采用DVS技术以降低系统能耗。DVS技术的研究主要从具有严格时间约束的实时独立任务方面进行，以达到显著降低任务整体能耗的目的。如文献[1]采用一种应用在单核处理器的嵌入式系统中的伪多项式动态规划算法，以求解具有离散电压值的周期性实时任务的最优解。文献[2]通过重复利用时间以允许其余任务可以在低于标准电压的情况下运行。

为了能够在满足时间约束的前提下提高整个系统的能效，可以从基于概率的嵌入式系统任务调度方向进行研究。文献[3]首先考虑具有不确定性的执行时间的任务，然后引入概率轮转调度算法来缩短具有无环拓扑架构任务图的执行时间。文献[4]采用调度算法将任务动态地重新映射到适当的处理器中，并设定处理器内部执行任务的顺序，将多余的时间分配给未执行的任务。文献[5]提出一种不限制嵌入式系统处理器数量的动态规划算法来解决异构嵌入式系统的任务分配问题。

本文采用一种局部重启搜索算法(LSR)以找到嵌入式系统的最佳调度策略。首先，设计一个有效的处理器分配算法来生成处理器分配方案；然后使用电压分配算法，以一定概率下完成任务的思路来最小化整体的能耗；最后，为了避免局部最优解，使用带有重新启动的本地搜索再次对资源进行优化并得到全局最优解。本文采用的LSR算法和传统调度算法能够为软实时嵌入式系统提供一些满足时序和置信度要求的更低成本解决方案，以动态调度的思想来解决专属虚拟接入点(PVAP)问题。

1 问题建模

由于条件指令和时变外部环境(如波动的网络带宽、不同的用户输入和DVS)的变化，星载实时嵌入式操作系统的同一任务会在不同环境下产生不同的执行时间。即，一个任务在不同的环境下可能会有不同的完成概率。

以下符号用于问题的数学表述中：DAGG=〈V,E〉用于表示所有任务及其数据的依赖关系，V={v1,…,vi,…,vx}是任务节点集合，x是任务数量。E={e11,…,eij,…,enn}是边的集合，当eij为1时，表示当前vi和vj节点之间存在数据依赖，反之为0无依赖。

关于嵌入式处理器的定义如下：PE={pe1,…,pei,…,pey}是处理器单元的集合，y是处理器数量。pei表示第i个处理器。Vol={Vol1,…,Voli,…,VolM}，Voli={Voli,l,…,Voli,j,…,Voli,L}是pei电压的集合，L是处理器的可用电压值。

TA(G)=max{si+r(i),si+ct(i)},

∀vi∈V

(1)

(2)

(3)

由于任务vi取决于前置的数据输出，当且仅当只有前置任务完成后才能运行。

建模之后，给出PVAP问题的定义：给定一个有限的处理器集合PE，一个电压电平集合Vol，一个执行概率集合B，有向无环图DAGG=〈V,E〉，一个时间约束T和一个置信度P，问题是要为每个任务vi确定一个合适的处理器和电压电平，其提供了在时间约束T下的最小能量消耗和具有保证置信概率P的优先约束。

2 PVAP问题的解决方案

提出了一种面向星载嵌入式系统，具有数据依赖和CPU资源约束的非周期性任务图的可变电压概率调度的解决方案。解决方案分为三个阶段：第一阶段，使用有效的调度算法以获得初始处理器的分配方案；第二阶段，基于已得到的分配策略，提出电压分配算法，以保证任务能在一定的置信度和时间约束下执行完成，同时对能耗较高的任务进行优化分配，并将能耗最小化；第三阶段，使用LSR算法来摆脱局部最优解。LSR算法通过更新目标函数从候选解决方案中搜索最优解，直到任务结束或者超出时间约束，这些都将在下文中对其分别讨论。

2.1 初始处理器分配策略

由于嵌入式系统中处理器的数量有限，研究时需要为每个任务分配合适的处理器，以有效使用处理器。为了避免局部最优解，本文使用不同的调度算法，如基于尽可能晚(ALAP)调度算法[7]、基于尽可能快 (ASAP)调度算法和整数线性规划(ILP)调度算法[8]来生成原始的处理器分配策略。

处理器调度算法(ASAP/ALAP)的实现过程如下：首先使用拓扑排序获得目标任务列表具有优先级限制的DAG拓扑序列；然后计算每个任务的最差执行时间，在最早/最近状态下，使用ASAP/ALAP算法根据任务的优先级进行调度，通过为同一处理器上的连续任务间插入模拟边界来保证任务的执行顺序；最后使用ASAP/ALAP算法将任务图中的每个任务分配给适当的处理器，就可以生成用于解决PVAP问题的新DAG。

ILP算法的实现如下：首先计算每个任务的执行时间；然后采用整数线性规划(ILP)调度算法[8]完成ILP的PVAP问题的数学表达式；最后使用LINGO 9.0软件的非线性规划解算器来获得处理器分配策略。

2.2 电压分配方案

该节讨论如何使用动态编程(DP)来解决PVAP中电压分配问题。

1)令K={S1,S2}，式中，S1和S2分别是图G1和G2的解空间；

2)S′0=CombineSubSolution(K)；

3)S0=S′0⊙B0；

4)删除S0中的冗余解和不可行解。

根据上述思想，按照自下向上的顺序计算出图1(a)任务树中各个节点i的解决方案。当算法到达根节点0时，需计算出S0所需要的全部结果，并重复使用子图的解来计算。然后从最小的子图开始，逐步解决大规模的问题。在此计算过程中应保存已有子图的解决方案，通过重复使用子图来提高问题的解决速度。整个图的PVAP问题可以分解为多个子图的PVAP问题。通过去除Si中的冗余和不可行解，可获得满足时间和概率约束的候选解，并将具有最小能耗的解视为整棵树的最优解。共同节点问题如图1所示。

图1 共同节点问题Fig.1 Common node problem

然而对于具有任意数量边和节点的DAG，由于其中可能存在公共节点(出现在2个或更多子图中的节点)，所以在电压选择过程中会产生冲突。例如在图1(b)中，v4节点属于2个子图G1和G2，可能存在V4在S1中为v4优先选择vol0，而在S2中选择。因此即使G1和G2的解决方案(S1和S2)都是最佳的，但是由于电压的选择会发生冲突，所以S0不能获得最佳的分配方案。下面列举所有节点中可能存在的组合方案来解决此问题，在所有可能的组合中，PVAP_DP算法能够选择最佳的电压分配方案。算法流程如图2所示。

图2 算法流程图Fig.2 Algorithm flowchart

采用PVAP_DP算法来解决电压分配问题，如图2(a)所示。首先要解决子问题，得到逆拓扑排序。之后为了解决公共节点的问题，需要列举多个节点中可能存在的电压分配方案。由于从逆拓扑顺序的第1个节点(假设为v1)没有子节点，所以可行解S1就是概率执行列表B1。

为了得到Si，第一步首先需要通过Gi,Gi1,…,Giw的解来得到S′i,然后对于每个S′i,j∈S′i和b=Bi,对s′i,j和b进行⊙操作从而得到Si。当内层的循环结束时，得到所有节点的最优电压分配SN。最后合并每个循环中产生的最佳电压分配方案SN。当外层循环结束时，在当前的处理器选择下获得所有节点的最优电压分配方案。当外循环结束后，从集合S中去除冗余解和不可行解，得到最优解。

2.3 LSR局部重启搜索策略

采用局部重启搜索算法(LSR)在所有候选解中寻找最优解。图2(b)中给出了LSR算法流程图。首先使用有效调度算法(如ALAP)生成初始处理器调度(DAG)；然后基于新生成的DAG，在该步骤中采用带有局部搜索的PVAP_DP算法来最小化能耗；最后从初始调度开始，在内部循环中，采用局部搜索算法在候选解的解空间中寻找更优的处理器和电压分配。为了避免局部最优，在外循环中应用LSR。使用不同的处理器调度策略(本例中使用PVAP_DP算法)来生成初始处理器分配方案，以便对不同的初始调度表采用LSR。当达到重启次数时终止循环。重启次数是一个经验常数，取决于不同的应用场景。

3 实验

依据参考文献[9]进行实验设计，并且利用实验结果对PVAP_LSR算法进行性能评估[10]。ASAP和ALAP调度算法广泛应用于各种处理器和电压分配算法中，本文实验中使用的基于ASAP/ALAP的调度算法是ASAP/ALAP和PVAP_DP的结合，而PVAP_LSR算法是LSR和PVAP_DP算法的结合，通过这种方式能够提升LSR算法的性能。本文还对PVAP_LSR算法和其他搜索算法，如禁忌搜索(TS)和模拟退火算法(SA)进行比较。

3.1 实验基准

针对表1中2个基准进行了对比实验，使用随机化任务图生成器[7]得到任务图，TGFF-1具有很长的关键路径，TGFF-2具有相对较短的关键路径。

表1 实验任务图的基准描述

首先针对估计不同频率下的CPU功率进行分析。本文采用PowerPC处理器和ARM处理器。处理器的电压以及各自的功率与频率见表2。

表2 ARM和PowerPC处理器的电压和功耗

在表3～5、图3～4中，能源消耗的单位是能源单位(EU)，时间约束或者任务执行时间的单位是时间单位(TU)，列“TC/PEs”表示“时间约束/处理器数量”。PVAP_LSR算法的平均提升效果显示在每个表的最后一行。实验中可以灵活的选择要部署的处理器数量(2个或者3个)。前者意味着所有任务都在2个处理器(PowerPC和ARM处理器)上执行，后者意味着所有任务在2个PowerPC处理器和1个ARM处理器上执行。

3.2 与ILP算法的比较

将本文中使用的算法和ILP进行了比较。对使用TGFF-1标准的实验结果分别见表3，4。在表3，4中，“ILP1”“ILP2”和“PVAP_LSR”三列分别表示不含DVS的ILP、具有DVS的ILP和PVAP_LSR算法获得的结果。“%I1”和“%I2”两列分别代表本文中使用的算法相对于不具有DVS的ILP算法和具有DVS的ILP算法的改进。在本文中，所有表中带有“×”的条目表示相应的分配未能生成有效的调度。

实验结果表明：PVAP_LSR算法在保证置信概率的同时，能够提高能效。表3中 PVAP_LSR算法与ILP2算法相比，在置信概率分别为0.8，0.9和1.0时，平均(最大)能耗降低分别为18.4%(23.7%)，13.3%(17.4%)和9.8%(14.1%)；与ILP1算法相比，分别获得37.2%(41.4%)，33.8%(38.5%)和31.2%(36.0%)的平均(最大)能耗降低，置信概率分别为0.8，0.9和1.0。表4中PVAP_LSR算法与ILP2算法相比，平均(最大)能耗降低分别为17.4% (20.8%)，10.8%(15.7%)和1.3%(4.5%)，置信概率分别为0.8，0.9和1.0；与ILP1算法相比，平均(最大)能耗降低分别为28.0%(41.0%)，22.2%(37.3%)和31.2% (36.0%)，置信概率分别为0.8，0.9和1.0。

表3 有ILP的DVS、无ILP的DVS和PVAP_LSR的能耗比较

表4 有ILP的DVS、无ILP的DVS和PVAP_LSR的能耗比较

对于TGFF-1基准，图3显示算法相对于ILP1和ILP2的改进。与ILP1和ILP2相比，PVAP_LSR算法在所有时间约束下能够实现更好的能效，横坐标为人为设定的时间约束，纵坐标为调度算法执行完的任务总能耗。ILP算法在一定的时间范围内可能无法找到近似最优解。

3.3 与基于ALAP和ASAP的算法比较

将本文使用的算法与其他2种算法(ALAP，ASAP)进行比较。ASAP的使用方法为：对于处理器分配，使用基于ASAP的列表调度；对于电压分配，使用PVAP_DP算法。ALAP的使用方法为：对于处理器分配，使用基于ALAP的列表调度；对于电压分配，使用PVAP_DP算法。

基于TGFF-2标准的实验结果见表5。表中“A1”“A2”和“PVAP_LSR”分别表示由ASAP，ALAP和PVAP_LSR算法的结果，“%A1”和“%A2”分别表示相对于ASAP和ALAP算法的改进效果。

图4是PVAP_LSR相对于TGFF-1基准的ASAP和ALAP调度的改进。在对于TGFF-1基准，PVAP_LSR在功耗方面可以获得最佳的可变电压调度。与基于ALAP的调度相比，PVAP_LSR相对于基于ALAP的调度分别实现15.6%(23.0%)，13.9%(19.2%)和11.5%(17.4%)的平均(最大)能耗降低，置信概率分别为0.8，0.9和1.0)。PVAP_LSR算法与基于ASAP算法相比，PVAP_LSR分别获得15.2%(24.3%)，13.4%(20.6%)和11.0%(18.8%)的平均(最大)功率优化，置信概率分别为0.8，0.9和1.0。而且PVAP_LSR算法在所有时间约束下都具有更好的能效。

图3 ILP1, ILP2和PVAP_LSR基于TGEF-1基准的能耗Fig.3 Benchmark energy consumption of ILP1, ILP2 and PVAP_LSR based on TGEF-1

图4 ALAP, ASAP和PVAP_LSR基于TGEF-1基准能耗Fig.4 Benchmark energy consumption of ALAP, ASAP and PVAP_LSR based on TGEF-1

表5 ASAP, ALAP和PVAP_LSR基于TGFF-2基准的能耗对比

4 结束语

现有的研究对实时嵌入式系统的执行时间和能耗等不确定性因素的关注度不够。针对资源有限的星载实时嵌入式系统，本文采用概率方法，提出一套处理器和电压分配算法来解决具有优先级约束的非周期任务的可变电压调度问题。实验结果表明：与目前流行的方法相比，该方法能够提高星载嵌入式操作系统的能效，为用户实现能效提供更多选择，同时在保证置信度的前提下满足定时约束。本方法对于软实时应用程序较为有效。