星载异构计算环境下的能耗优化任务调度

2021-09-11安建峰游红俊赵伟勋刘咪咪张盛兵

上海航天 2021年4期

安建峰，游红俊，赵伟勋，刘咪咪，张盛兵

（1.西北工业大学计算机学院，陕西西安 710129；2.上海航天电子技术研究所，上海 201109）

0 引言

在诸如航天探测系统等尖端领域里，系统对安全性、可靠性、实时性以及功耗都有较高的要求，其中，安全性和可靠性一般通过硬件设备进行保障，实时性及功耗往往通过合理的任务调度方案来保证。随着近些年异构多核处理器的发展，在异构平台上，如何处理上述问题成为一种研究方向。

异构多核处理器由不同类型的处理器核组成，相比较单核、同构多核处理器具有独特的优势，能够更有针对性地处理特定的事件。常见的异构多核处理器有CPU 和GPU，或FPGA 的集成、ARM的BIG.LITTLE 架构等，根据处理器核的类型数量称之为二型异构多核处理器。在异构处理器中，研究最为广泛的就是ARM BIG.LITTLE 架构处理器下的任务调度算法［1-3］。

异构多核处理器的任务调度已经被证明是NP完全问题，目前还没有算法可以在多项式时间内求得最优解，现有算法大多使用启发式的算法求得近似解［4］。异构调度模式一般分为3 种类型：不迁移、同构核间迁移以及全局核间迁移。

1）不迁移［5-7］是指当任务分配到一个处理器核后只在该处理器核上执行；

2）同构核间迁移是指任务在执行期间可以迁移到同种类型的处理器核上执行；

3）全局核间迁移是指一个任务在执行期间可以迁移到任意类型处理器核上执行。

RARAVI 等［8］提出了用整数线性规划（Integer Linear Programming，ILP）的方法来解决同构核间迁移模式下的任务调度问题，并且提出了一种按分类进行分配的近似算法（Sort and Assign，SA）。BARUAH［9］对全局核间迁移模式下周期性任务调度的可行性进行了分析和研究，通过一组线性规划（Linear Programming，LP）约束判定对于给定处理器平台和任务集是否存在可行的调度方案。CHWA 等［10］提出了一种最优的全局核间迁移模式下的周期性任务调度算法，然而其未考虑功耗问题。李延祺等［11］提出一系列基于计算概率的建模方法，用来解决星载实时嵌入式系统中，对于具有数据依赖的非周期性任务的处理器和电压分配相关问题，在所有时间约束下具有更好的能效。杨亚琪等［12］提出一种异构多核下兼顾应用公平性和能耗的调度方法。

本文的主要工作是以二型异构多处理器为调度平台，将调度算法分为负载分配及任务调度2 个步骤：

1）负载分配算法EB-Split 是在CHWA 等［10］提出的全迁移算法（Hetero-Split）基础上加入能耗优化的思想；

2）任务调度算法BI-Wrap 则根据负载分配的结果合理安排任务时间片，保证调度的可行性。

实验表明：本算法在不损失Hetero-Split 算法所能寻找到的可行方案数的条件下，能耗降低约23%～24%。

1 系统模型构建

约定每一个任务都独立且可抢占，可以在处理器集群内部，也可以跨集群进行任务的迁移，假定这些迁移代价可以接受。每一个任务都会被重复地调用，每一个此类调用称为一个作业或者任务实例。

调度遵从非并行执行（No Parallel Execution，NPE）限制：

1）每个处理器在任一时刻只能运行一个任务；

2）一个任务实例任一时刻只能运行在一个处理器上。

为了方便调度算法的设计，将调度方案分为2个子部分：负载分配和任务调度。

1）负载分配问题决定了在保证实时性的条件下，每个任务在每个类型的处理器核上该分配多少子任务，同时尽可能降低系统能耗；

2）调度生成问题在解决负载分配问题的基础上，生成一个合理的调度方式使得所有任务都可以满足截止期约束条件。

2 负载分配算法EB-Split

基于能耗优化的二型异构负载分配算法EBSplit 是在文献［10］中的分配算法的基础上加入能耗的因素，调整任务分配，使得在保证可调度性的条件下，尽量减小系统能耗。

2.1 可行性条件

为了保证任务的截止期约束，任务τi应该分配给type-1 类型和type-2 类型处理器集群的最小任务分配量分别记作和。任务τi在两类集群上的剩余工作负载分别记作和，即

为使给每个处理器集群分配的任务可调度，以下条件必须满足：

综上，负载分配算法Hetero-Split 理论上保证了只要存在则必然能够找到可行的负载分配方案［10］。

2.2 基于能耗的分配调整

对于给定的处理器平台和任务集，理论上可能存在多种满足要求的任务调度方案。设SUR 代表Surplus。

定义type-1 和type-2 类型处理器集群执行能力剩余量分别为SUR1和SUR2，则由约束条件C3和C4可得

能耗优化算法的思想就是在保证SUR1和SUR2都非负的前提下，调整和的大小，尽可能地降低系统总能耗。

2.3 能耗优化目标

系统总能耗E由各任务在2 种类型处理器集群上的能耗之和得到，因此，在给定时间片长度L下，该时间片内的系统总能耗的计算公式如下：

2.4 能耗优化分析

式中：W1为那些已经分配到type-1 类型的处理器群上（＞0），但是从减小系统能耗的角度则更适合分配到type-2 类型处理器群上的任务；W2同理。

首先考虑从W1中选取任务τi，将其以更大的比例重新分配到type-2 类型的处理器群上。用表示在分配调整的过程中任务τi在2 种类型处理器上的分配比例变化，即重新分配后有

设ΔU2为SUR2在该过程中的减小量，ΔE为系统总能耗E在该过程中的减小量，则由式（2）可得

在不考虑能耗的任务分配方案下，SUR2为定值，所以为最大限度地减小系统的总能耗，从W1中选取任务的规则就是每次选取对应ΔE/ΔU2值即值最大的任务，以一定的比例ki(ki≤)重新调整到type-2 类型处理器核上；从W2中选取任务的方法同理。

2.5 分配方法

对于W1和W2中元素存在与否，分为以下4 种情况：

1）W1和W2均为空：表示已经不存在待调整的任务，分配方案结束；

2）W1非空，W2为空：选取W1中的第一个任务τi，以比例ki重新调整到type-2 类型处理器核上；

3）W1非空，W2为空：与2）同理；

4）W1和W2均非空。

选取W1中的第一个任务τi，以比例ki重新调整到type-2 类型处理器核上；选取W2中的第一个任务τj，以比例kj重新调整到type-1 类型处理器核上。为使SUR1和SUR2都非负，需要保证满足以下几个条件：

在此过程中，系统总能耗的减小量ΔE为

为在满足约束条件CC 的情况下使得ΔE最大，利用二元线性规划，易求得ki和kj，根据ki和kj值做相应的分配比例调整。

3 任务调度算法BI-Wrap

为保证在EB-Split 算法下所有的任务都满足截止期需求且不违背NPE 原则，还需设计一种合适的任务调度方法，决定在某一时刻哪个任务具体在哪个处理器核上执行。

3.1 时间片划分

LEVIN 和FUNK 证明了对于一个多核处理器上的任务调度问题，如果参与调度的任务具有2 个或者2 个以上的不同的截止期，那么就无法找到合适的任务调度方案。而如果任务集中的所有任务都具有相同的截止期，那么就可以找到可行的任务调度方案［13］。

因此，在二型异构多核平台上，要保证任务集中的所有任务都具有相同的截止期，可采用时间片划分［14-16］的思想，将整个时间轴划分为多个时间片，每个时间片分配相应的任务工作量，即同一个时间片内部所要调度的任务均共享同一个截止期。

3.2 时间片划分方法

每个任务τi在执行过程中会产生多个周期性的作业，每个作业的释放周期为相对截止时间Ti，故任务τi所释放的第k个作业的绝对截止时间为k×Ti。

将所有任务τi∈τ的所有绝对截止时间呈现于同一时间轴上，按照绝对时间的先后顺序定义为时间节点tj（j=0，1，…，j），其中，t0=0 表示时间轴的起始节点，也是任务调度执行的开始时间。用σj表示时间片划分完成后的第j个时间片，用Lj表示第j个时间片的长度，则时间片划分的结果为

3.3 时间片上的任务工作量安排

在长度为Lj的时间片σj内，根据等比例划分的方法，任务τi在type-1 类型处理器上的工作量安排为

在type-2 类型处理器上的工作量安排与type-1同理。

3.4 BI-Wrap 调度算法

τa、τb表示。

定义 4 个队列：P1、R1、P2、R2，将集合{E，M，SP1，SP2}中的任务按照下列规则添加到这4个队列中：

在type-1 类型处理器群以及type-2 类型处理器群上分别对分配好的任务进行调度，调度规则如下：

1）在type-1 类型的处理器上，从core 1 开始，按照处理器核编号递增且时间递增的方式对队列P1中的任务依次进行调度。

2）在type-1 类型的处理器上，从corem1开始，按照处理器核编号递减且时间递减的方式对队列R1中的任务依次排列在时间片上，调度时按时间递增方向进行。

3）在type-2 类型的处理器上，从core 1 开始，按照处理器核编号递增且时间递增的方式对队列P2中的任务依次进行调度。

4）在type-2 类型的处理器上，从corem2开始，按照处理器核编号递减且时间递减的方式对队列R2中的任务依次排列在时间片上，调度时按时间递增方向进行。

3.5 调度举例

任务集的划分结果为

由调度规则可得

应用BI-Wrap 算法中的调度规则在所划分的第1 个时间片（σ1=[ 0，60)，L1=60）上对上述4 个队列中的任务实例进行调度，调度结果如图1 所示。

图1 BI-Wrap 调度算法实例Fig.1 Examples of the BI-Wrap schedule algorithm

如图1 所示，采用BI-Wrap 算法进行任务调度可保证在第1 个时间片内分配的任务工作量都能在时间片截止之前完成，且所有任务在调度过程中都满足非并行执行性。

3.6 BI-Wrap 算法的时间复杂度

BI-Wrap 算法首先将整个任务集划分为4 个子集，这一过程的时间复杂度为O(n)，然后，BIWrap 算法对这4 个子集中的任务均按照既定的规则进行顺序调度，这一过程的时间复杂度也为O(n)。因此，整个BI-Wrap 算法的时间复杂度为O(n)。

4 仿真试验及结果分析

4.1 仿真实验

在Windows 平台下用C++语言模拟算法的调度过程，对SA 算法、Hetero-Split 算法及EB-Split 算法（使用BI-Wrap 算法进行调度）分别进行了模拟调度。

对算法的输入数据，设置处理器集群（m1，m2）的个数平均至少大于2，任务集τ中的每个任务（τi）在不同处理器集群上的参数元组值均由随机函数生成。实验每次测试的任务集数目为10 000。根据分析，实验将首先执行算法的负载分配以追求低能耗的目标，然后，按照BI-Wrap 算法保证分配好的负载能够进行调度。

首先测试得到3 种算法各自满足系统约束的可行任务调度方案数见表1。

表1 各算法所求的可行方案数Tab.1 Numbers of feasible schemes for each algorithm

由实验结果可知，EB-Split 算法不损失Hetero-Split 算法求得的可行方案数，且两者均优于SA 算法。然后对比EB-Split 算法（使用BI-Wrap 算法进行调度）与Hetero-Split 算法（正常调度）的平均系统能耗（分别用E1_avg 和E2_avg 表示），每次测试得到的系统能耗按式（11）计算而得。并计算EB-Split算法相对于Hetero-Split 算法的能耗降低百分比R=（E1_avg-E2_avg）/E1_avg。实验结果如表2、图2 所示。

表2 Hetero-Split 与EB-Split 算法的能耗比Tab.2 Energy consumption ratios of the Hetero-Split and EB-Split algorithms

图2 Hetero-Split 与EB-Split 的能耗对比Fig.2 Energy consumption of the Hetero-Split and EBSplit algorithms

由实验结果可知，EB-Split 算法相较于Hetero-Split 算法在系统总能耗方面约降低23%～24%。

4.2 仿真结果分析

由实验结果可知，EB-Split 算法与Hetero-Split算法在寻求可行性方案上性能相当且优于SA 算法。Hetero-Split 算法已被证明为可行方案数最优的［10］，故本文所设计的EB-Split 算法也满足可行任一方案的最优性。此外，在能耗方面，EB-Split 算法相较于Hetero-Split 算法在系统总能耗方面有大幅度降低，降低比率约为23%～24%。