CPU-GPU MPSoC 中使用寿命驱动的OpenCL 应用调度方法

2023-05-22龙赛琴李哲涛

计算机研究与发展 2023年5期

曹坤龙赛琴李哲涛,2

1（暨南大学信息科学技术学院广州 510632）

2（网络安全检测与防护国家地方联合工程中心（暨南大学）广州 510632）

近年来，随着半导体技术的快速进步和对应用性能需求的不断增加，多处理器已经取代单处理器，成为当前和未来处理器的主流设计范式.在多处理器设计方法中，集成CPU 和GPU 的多处理器片上系统（multiprocessor system-on-chips，MPSoC）受到广泛关注[1].例如，三星 Exynos 5422 MPSoC[2]集成了4 个ARM Cortex A15 CPU 核心、4 个 ARM Cortex A7 CPU核心、1 个 ARM Mali-T628 MP6 GPU.这类MPSoC 可以充分发挥GPU 核心的并行计算能力和CPU 核心的通用计算能力，从而满足各种新兴应用的低延迟、低开销、节能等需求.

为了充分发挥CPU-GPU MPSoC 的性能，开放计算语言[3-5]（open computing language，OpenCL）逐渐成为一种极具吸引力的应用程序编写标准.OpenCL 支持多级别的线程并行化，可以将应用高效地映射到同构或异构、单个或多个CPU 和GPU 核心.然而，在执行OpenCL 应用时，如何确定CPU 和GPU 的工作负载，充分发挥线程级和数据级并行化优势，一直以来是一个研究难点和重点.图1 为OpenCL 应用的延迟和能耗随CPU 负载变化的示意图.如图1 所示，在执行特定的OpenCL 应用时，存在使该应用获得最优性能的CPU 负载，当分配更多的负载给CPU 核心时，应用的性能不会进一步提升，反而会产生额外的能量和延迟开销.因此，在设计OpenCL 应用调度算法时，需要考虑如何将OpenCL 应用的负载合理地分配给CPU 和GPU 核心.

Fig.1 Performance of OpenCL applications under varied CPU workload fractions [4]图 1 OpenCL 应用在不同 CPU 负载比例下的性能[4]

现有的OpenCL 应用调度技术[6-14]大多面向系统静态阶段给定的初始应用，旨在搜索最佳的负载划分点和负载到处理器核心的映射，以平衡OpenCL 应用的延迟和系统的能耗.对于此类技术，由于应用的指令条数、截止期限、周期等关键参数均在系统静态阶段已知，因此可设计复杂的离线算法，实现降低延迟和优化能耗的目的.基于静态调度方案,也有部分工作[10-14]根据系统运行时的资源利用情况，对初始应用的静态调度表进行微调，以提高应用调度算法的灵活性.然而，这些技术[6-14]均无法有效应对在系统运行时的新到应用.这主要是因为在真实场景中存在事件触发型应用，例如视频监控场景中的人体追踪应用，只有捕捉到人体活动时才会触发后继子任务的执行.考虑到事件的猝发性，事件触发型应用的到达时间在系统静态阶段是未知的.此外，由于事件持续时间的随机性导致采集到与该事件相关的数据总量只有在系统运行时才能确定，而应用需要执行的指令总条数通常依赖于输入数据总量，输入数据总量越多，执行的指令总条数也越多.显然，事件触发型应用执行的指令总条数只有在系统运行时才能确定.如果直接采用现有技术[6-14]处理在系统运行时的新到应用，将不可避免地带来极大的调度决策时间开销，无法确保满足应用的时序要求.尽管文献[15]探究了如何在系统运行时处理新到应用，然而却忽视了对应用时序、系统温度、系统使用寿命的管理.

随着芯片制造技术的快速发展，芯片功率密度呈指数级增长，进而导致芯片温度不断升高.如果芯片工作温度过高，系统将出现功能错误、可靠性低、永久损坏等问题[16-17].因此，温度管理一直是异构计算系统中一个重要而紧迫的研究课题，特别是对于配备有限冷却技术的CPU-GPU MPSoC，迫切需要使用有效的热量管理技术，以实现高性能计算，同时将芯片的峰值温度保持在指定的温度范围内.然而，当前将OpenCL 应用部署到CPU-GPU MPSoC 的研究工作，往往忽略了对芯片温度和使用寿命的管理，导致处理器核心在执行应用时超过了峰值温度，甚至永久性故障的提前发生，无法保证OpenCL 应用在CPUGPU MPSoC 的长久运行.为了弥补现有技术的缺陷，本文将电迁移（electromigration，EM）、经时击穿（time dependent dielectric breakdown,TDDB）、热循环（thermal cycling，TC）三种引起多核处理器系统失效的主要机制考虑在内，旨在降低OpenCL 应用延迟的同时，有效降低芯片温度和延长系统使用寿命.

本文针对CPU-GPU MPSoC，研究了如何在满足时序、温度、能耗、使用寿命约束的前提下，优化初始和新到OpenCL 应用的平均延迟.本文的主要贡献包括3 个方面：

1）针对系统静态阶段的初始应用，提出了一种基于改进交叉熵策略的调度技术，该技术将OpenCL应用的特性充分考虑在内，有效提高了OpenCL 应用的设计点寻优效率；

2）针对系统动态运行阶段的新到应用，设计了一种基于反馈控制策略的调度技术，该技术能够有效降低制定动态调度决策的时间开销，同时最小化新到应用的平均延迟；

3）在真实硬件平台上进行了大量实验验证了所提调度方法的有效性，实验结果表明本文提出的方法可以将应用的平均延迟降低34.58%，同时满足所有的设计约束.

1 相关工作

近年来，如何优化OpenCL 应用在CPU-GPU MPSoC 的性能逐渐成为一个研究热点.文献[6]提出了一种名为 Troodon 的新型负载平衡调度启发式算法，该算法融合了基于机器学习的设备适用性模型，能够根据OpenCL 应用的特征对其分类.此外，Troodon 还包括一个加速预测器，该算法用来预测OpenCL 应用在设备上执行时获得的加速比.通过E-OSched 调度机制，Troodon 以负载平衡的方式将应用分配给CPU 和GPU 核心，从而降低应用的延迟.文献[7]提出了一种面向 OpenCL 应用和CPU-GPU集群的计算架构FlinkCL，该架构使用4 种技术：异构分布式抽象模型、即时编译模式、分层部分缩减策略、异构任务管理策略.

文献[8]探索了如何使用主动模糊学习将OpenCL应用映射到异构CPU-GPU 多核架构.在学习阶段，通过开发一个基于机器学习的设备适用性分类器来创建子样本，以准确预测哪些处理器核心被分配了过多的负载.文献[9]提出了一种基于预测运行时间的OpenCL 应用调度策略.该策略利用了机器学习方法，可以在调度前估计单个应用程序的运行时间.然后，根据预测结果，选择最合适的处理器核心来处理该应用，从而降低应用的运行时间.文献[10]展示了一个用于优化CPU-GPU 协同计算的框架OPTiC，该框架通过利用一系列建模技术，可以准确估计CPU和 GPU 的功率、不同频率点的性能、温度和内存争用对性能的影响.文献[11]介绍了一种编程模型调度器，它允许异构系统中的所有设备协同执行单个OpenCL 应用.该调度器引入了一种新型负载均衡算法，能够实现最优的系统资源配置.

进一步地，文献[12]使用线性回归技术，对OpenCL应用的特征和性能进行建模，在该模型基础上，利用动态电压频率调节技术，确定CPU 和GPU 最佳的工作负载和频率.文献[13]提出了一个用于在异构多核平台上对实时OpenCL 应用进行热感知调度的框架.该框架将任务迁移、频率调整、空闲槽插入等多个控制动作视为任务映射参数，通过调整任务映射参数来降低违背温度约束的概率.文献[14]提出了一种针对运行在CPU-GPU 集成平台上的应用划分策略，它由探索阶段、稳定阶段、最终决策阶段构成，可以动态地将应用负载分配给CPU 和GPU，从而降低应用的执行时间和能耗.文献[15]设计了一种跨设备控制变量自动更新策略，解决了如何使用细粒度共享虚拟内存在具有共享缓存的CPU-GPU 架构上执行OpenCL 应用.

表1 对比了本文提出的方法和现有技术的特点.由表1 可知，本文综合考虑了应用时序、能耗、延迟、温度、系统寿命，而相关工作[6-15]未能将这些因素充分考虑在内.本文弥补了现有工作的不足，针对系统静态阶段的初始应用，提出了一种基于改进交叉熵策略的调度方法，针对系统动态阶段的新到应用，设计了一种基于反馈控制策略的调度技术.本文提出的调度方法能够在满足时序、温度、能耗、使用寿命约束的前提下，最小化初始和新到OpenCL 应用的平均延迟.

2 系统模型

2.1 架构模型

Table 1 Comparison of Our Proposed Method with Existing Techniques表 1 本文提出的方法和现有技术的对比

2.2 应用模型

假设实时的OpenCL应用集合A={A1,A2,…,AS,AS+1,AS+2,…,AQ}在给定的硬件平台上运行.其中，Aoffline={A1,A2,…,AS}表示系统静态阶段的初始应用集合，Aonline={AS+1,AS+2,…,AQ}表示系统动态阶段的新到应用集合.对于一个初始应用As（1 ≤s≤S），它需要执行的指令条数Ws和截止期限Ds是已知的.假设初始应用的执行顺序已经通过现有算法确定，例如采用文献[18]的最短截止期限优先（earliest deadline first,EDF）算法.但是，对于一个新到应用Ar（S+1 ≤r≤Q），它的达到时间Tr、需要执行的指令总数Wr、截止期限Dr在静态阶段是未知的，只有在系统运行时的动态阶段才能获得.

此外，无论是初始应用As和新到应用Ar，均支持数据并行化操作，能够根据系统运行状态调节CPU和GPU 的负载、负载到CPU 大核心和小核心的映射.为了便于表述，用符号Aq（1≤q≤Q）表示集合A={A1,A2,…,AQ}中的任意一个应用.用符号Pq表示应用Aq的划分点，取值为区间[0,1]的离散值.例如，应用划分点集合可以设置为{0,0.2,0.4,0.6,0.8,1}，当Pq=0.4 时，表示40%的指令条数（或工作组）是由CPU 核心完成的，而剩余60%的指令条数（或工作组）是由GPU 核心完成的.

2.3 处理器寿命模型

文献[19-20]指出，电迁移、经时击穿、热循环是引起多核处理器系统失效的主要机制.电迁移指的是在电流和温度的共同作用下，金属线出现断裂从而导致芯片无法正常工作.用符号λEM表示由电迁移引起的久性故障速率，计算公式[19]为

其中ℏ，ω，k1，k2均为非负常量，ψ是电流密度，ψ0是电流密度常量，Ttem为核心的温度.经时击穿指的是在栅极上施加一个电场低于栅氧的本征击穿场强的恒定电压，经过一段时间的运行后，氧化膜被击穿，造成核心的永久性损坏.用符号λTDDB表示由经时击穿引起的久性故障速率，计算公式[20]为

其中 α 和 β分别是场加速因子和跨电介质的电场.与电迁移和经时击穿不同，热循环是指由于相邻材料层的热膨胀系数不匹配产生的热应力造成的磨损，运行时的温度变化导致非弹性变形，最终导致元器件损坏.由文献[19]可知，由热循环引起的永久性故障速率为

3 问题定义和方法概述

3.1 问题定义

Fig.2 Illustration of our studied optimization problem图 2 本文研究问题示意图

给定CPU-GPU MPSoC 和实时应用集合A={A1,A2,…,AQ}，在时序、能耗、峰值温度、使用寿命的约束下，为每个应用找到最佳的设计点（包括划分点以及该应用到CPU 大核心和小核心的映射），从而最小化应用的平均延迟.用符号 Lq表示应用Aq的延迟，则Lq可以估算为[14]

3.2 方法概述

本文针对系统静态阶段的初始应用集合Aoffline={A1,A2,…,AS}和系统动态阶段的新到应用集合Aonline={AS+1,AS+2,…,AQ}，分别提出了相应的设计点优化技术.对于初始应用集合Aoffline={A1,A2,…,AS}，本文基于交叉熵优化策略，首先设计了一种设计点样本表示方法，然后提出利用拉丁超立方采样和样本微调技术来提高设计点寻优效率.对于新到应用集合Aonline={AS+1,AS+2,…,AQ}，本文设计了基于反馈控制的设计点动态优化技术，主要包括比例-积分-微分（proportional-integral-derivative，PID）控制器、应用准入控制器、应用映射控制器、主控制器，能够有效降低制定动态调度决策的时间开销，同时最小化新到应用的平均延迟.通过上述优化过程，本文提出的方案能够在满足所有系统约束的前提下，最小化OpenCL 应用的平均延迟.

4 基于交叉熵策略的初始应用设计点寻优技术

本节设计了一种基于交叉熵策略的初始应用设计点寻优技术，首先介绍交叉熵策略的理论基础，然后描述应用特性驱动的交叉熵策略改进机制，最后给出基于改进机制的设计点静态寻优算法.

4.1 交叉熵策略的理论基础

给定任意一个关于多维变量x的函数Φ(x)，目标是在搜索空间 S内找到最优映射，使得函数Φ(x)在x=x*处取最小值，即

显然，式（11）所示的优化问题是一个确定性优化问题.与直接求解该确定性问题的传统优化策略不同，交叉熵策略采用了问题转化的思想，将原问题转化成一个随机优化问题[21].本质上，交叉熵策略是一种基于重要性抽样的通用蒙特卡洛方法，用于解决稀有事件的概率估计.在交叉熵优化策略中，式（11）可转化为

在式（12）中，根据当前的第u个概率T(x,u)，生成了包含Z个随机样本的样本集合X={X1,…,Xz,…,XZ}，其中每个样本代表原问题的一个解.γ为阈值，Tu(Φ(X)≤γ) 是样本函数值Φ(X)不大于阈值γ的概率.IΦ(X)≤γ是指示函数，表达式为

Θu(IΦ(X)≤γ)为指示函数IΦ(X)≤γ的期望，计算式为

交叉熵策略采用了迭代抽样方法，试图逐步改变随机搜索的抽样分布，使稀有事件的概率不断增加.采样算法的每次迭代会生成代表原始问题解的多个随机样本，这些随机样本以一定概率收敛于最优解.概括地说，利用交叉熵策略求解优化问题的主要步骤包括：

1）初始化迭代计数器g←1和概率向量T0；

2）根据概率向量Tg-1随机产生Z个样本集合X={X1,…,Xz,…,XZ}；

3）计算样本的性能，按照性能递减的顺序对样本排序，然后选取性能最好的Belite个精英样本；

4）利用式（15）计算第g次迭代的阈值

其中 ϑ为性能最好的Belite个精英样本的下标集合；

5）利用式（16）更新第g次迭代的概率

其中xz,a为样本Xz的第a（1 ≤a≤U）个元素，为在第g次迭代过程中元素xz,a映射到b（1 ≤b≤U*）的概率，且为Tg的元素；

6）如果满足终止迭代条件，输出性能最好的样本，退出，否则更新g←g+1，返回步骤2）.

4.2 应用特性驱动的交叉熵策略改进机制

传统的交叉熵策略作为一种启发式的迭代优化策略，在每次迭代中都会产生大量的蒙特卡洛样本，带来巨大的运行时间开销.本文提出了一种交叉熵策略改进机制来探索静态的设计点寻优方案.与标准的交叉熵优化过程相比，改进后的交叉熵策略在第2）步的样本生成阶段进行了优化.首先设计了一种设计点样本表示方法，然后提出利用拉丁超立方采样和样本微调技术来提高设计点寻优效率.中有5 个应用{A1,A2,A3,A4,A5}，应用划分点以步长0.2 进行设置，因此可供每个应用选择的划分点为{0,0.2,0.4,0.6,0.8,1}.应用A1选择0.2 作为划分点，则

具体地说，我们采用了2 个二维数组来表示应用设计点样本，1 个数组用来存储应用的划分点，另一个数组用来存储应用到核心的映射.图2（a）展示了应用划分点数组，该数组中的行号指代应用编号，数组中的每列表示给定的划分点是否被选中.图2（a）该应用20%的指令条数是在CPU 上完成的，剩余的80%的指令条数是在GPU 上完成的.需要特别指出的是，划分点的步长是可以调节的，当步长较小时，表明系统对应用进行了细粒度划分，最终输出解的精度也就越高.图2（b）为应用到核心的映射数组示意图，在图2（b）中，假设有4 个同构的CPU 大核、4个同构的CPU 小核、1 个GPU 核心，且CPU 和GPU都支持4 个离散的频率.应用到核心映射点数组的第1～4 列指示了某个CPU 大核是否被选中执行特定的应用，如果被选中，则将对应的单元置为1；第5～8列指示CPU 大核的频率等级.类似地，第9～12 列指示了某个CPU 小核是否被选中执行特定的应用，第13～16 列指示CPU 小核的频率等级，第17 列指示GPU 核心的频率等级.图2（c）展示了根据生成的划分点和应用到核心的映射，5 个应用在核心上运行的示意图.

接下来，利用文献[22]提出的拉丁超立方采样技术来生成样本点.拉丁超立方采样是用于多元参数分布的近似随机分层抽样技术.对于一维变量抽样，拉丁超立方采样技术首先使用概率分布来估计变量的不确定性，然后将变量的范围划分为概率相等的区间，并在每个区间产生变量的样本值.对于二维变量抽样，拉丁超立方采样技术首先将样本空间划分为若干个具有相同采样概率的二维网格，然后随机选择1 个网格来生成样本，同时与该网格相同行或相同列的网格不能作为未来样本生成的候选网格.以对二维变量(x1,x2)进行抽样为例，图3 展示了采用随机采样技术和拉丁超立方采样技术的采样结果.从图3 可以看出，与随机采样技术生成的样本点相比，拉丁超立方采样技术可以用更少的样本数来较好地覆盖采样空间，极大地缩短了采样的时间开销.类似地，对于多维变量抽样，拉丁超立方采样技术需要将每一维分成互不重叠的若干区间，并确保每个区间有相同的采样概率，紧接着在区间内随机抽取1 个点，并将它们组成1 个样本.考虑到拉丁超立方采样技术的优势，在设计点采样阶段，本文利用该技术来生成样本点.

Fig.3 Comparison of random sampling and Latin hypercube sampling图 3 随机采样和拉丁超立方采样对比

在产生样本集合X={X1,…,Xz,…,XZ}后，进一步对每个样本Xz（1 ≤z≤Z）进行微调操作以提高单个样本的性能.具体地说，样本微调测策略是受到文献[4]的实验观察启发：在执行特定的应用程序时，存在一个使该应用获得最优性能的CPU 大核和CPU 小核的最佳组合，当更多的CPU 核心参与到应用程序的执行时，应用的性能不会进一步提升，反而会产生额外的能量和延迟开销.根据这一观察，可以对样本进行微调操作，微调后的样本更接近最优解，进而显著地提高了交叉熵算法的迭代效率.以图2（b）展示的从应用到核心的映射为例，应用A2在CPU 大核和的第2 个频率等级、小核和的第3 个频率等级上运行.首先，如图4（a）所示，尝试增加执行应用A2的CPU 大核数目，选择交换应用A2和应用A1的CPU 大核映射点，此时4 个CPU 大核全部参与应用A2的执行，所有的CPU 小核都不参与应用A2的执行.接下来，尝试减少执行应用A2的CPU 大核和CPU 小核的数目.如图4（b）所示，可以将应用A2和应用A4的CPU 大核和CPU 小核映射点进行交换，此时应用A2在CPU 大核的第4 个工作频率、小核的第4 个工作频率上执行.对于图4（a）和图4（b）生成的2 个微调样本，分别计算出它们对应的性能，然后比较它们的性能是否优于微调前的样本性能.如果图4（a）中的微调样本性能优于微调前的样本性能，则在下次样本微调操作时，应尝试继续增加执行应用A2的CPU 资源，比如提高CPU 大核的工作频率、增加执行应用A2的CPU 小核数目等；否则，在下次样本微调操作时，应尝试减少执行应用A2的CPU 资源，比如降低CPU 大核和CPU 小核的工作频率.

Fig.4 Example of fine tuning the samples of design points图 4 设计点样本微调示例

4.3 基于改进机制的初始应用设计点寻优算法

根据应用特性驱动的交叉熵策略改进机制，本文提出了一种应用设计点静态寻优技术，如算法1所示.

算法1.基于改进交叉熵策略的静态寻优算法.

算法1 的输入为应用集合Aoffline={A1,A2,…,AS}和核心集合{Cbig,Clittle,}.算法1 首先对概率向量T0和迭代计数器g进行初始化操作，然后以迭代的方式寻找最优的静态设计点.在迭代过程中，根据概率向量Tg-1，利用样本生成函数ProduceS ample（Tg-1,Z）产生总共Z个拉丁超立方采样样本.紧接着，调用应用选择函数SelectApp(Aoffline,Y)，从应用集合Aoffline={A1,A2,…,AS}中随机选取Y个应用进行样本微调操作.对于任意一个被选中的应用Ay（1 ≤y≤Y），使用样本微调函数TuneS ample(X,Ay)对其样本进行微调操作.同时，引入标志位如果=1，表示更多的CPU 资源会带来应用Ay的性能提升，即需要增加分配给应用Ay的CPU 资源；反之，如果=-1，表示更多的CPU 资源反而会降低应用Ay的性能，即需要减少分配给应用Ay的CPU 资源.因此，可以比较微调后样本Xu的性能是否强于微调前样本的性能.如果是，用微调后的样本Xu替代微调前的样本并将当前的标志位赋值给下次迭代的标志位如果微调后的样本性能均弱于微调前的样本性能，则表明当前的微调操作不能提升样本的性能，需要将当前标志位的相反数赋值给下次迭代的标志位.经过总共gmax次迭代，算法1 最终输出性能最优的单个样本.

5 基于反馈控制的新到应用设计点优化技术

本节介绍基于反馈控制的新到应用设计点优化技术，首先概述该技术的基本思想，然后详述PID 控制器、应用准入控制器、应用映射控制器、主控制器工作过程.

5.1 反馈控制策略的基本思想

图5 展示了本文提出的基于反馈控制的动态技术示意图.如图5 所示，该动态技术包含了准入队列、等待队列、PID 控制器、应用准入控制器、应用映射控制器、EDF 调度器、主控制器.对于系统静态阶段的初始应用集合Aoffline={A1,A2,…,AS}，可以直接调用静态方案为它们选取最优的设计点.对于系统运行时的新到应用集合Aonline={AS+1,AS+2,…,AQ}，设计了2 个队列：准入队列用来存储被系统允许进入的应用，等待队列用来存储未被系统允许进入的应用.PID 控制器周期性地对当前系统中处理器核心的平均利用率 θ进行采样，并将控制动作 φ返回给主控制器.主控制器调用应用映射控制器和应用准入控制器，以使当前系统中处理器核心的平均利用率 θ与利用率控制变量 φ相匹配.应用映射控制器负责将空闲的处理器核心分配给新到应用.EDF 调度器根据EDF 调度策略，负责管理准入队列里的应用在处理器核心上的执行.

5.2 PID 控制器

PID 控制器的运行过程如算法2 所示.算法2 的输入是预先设定的约束条件违背等级的阈值ε.首先判断当前的约束条件违背等级εnow是否大于阈值 ε，如果是，则需要迭代地优化系统的资源利用率.根据文献[23]，可利用式（17）更新系统资源利用率控制变量.

Fig.5 Overview of our feedback control based dynamic scheduling technique图 5 基于反馈控制的动态调度技术概览

其中 ℓ1，ℓ2，ℓ3分别代表PID 控制器的比例、积分、微分系数，ξ(t)表示约束条件违背等级εnow和阈值 ε的差值（即ξ(t)=ε-εnow），φ1表示在系统运行时发生积分误差的调度窗口个数，φ2表示系统运行时发生微分误差的调度窗口个数.算法2 使用PID 控制器对应用执行状态采样以更新约束条件违背等级εnow.当满足终止迭代条件时，输出系统资源利用率控制变量 φ.容易看出，当φ ＞0时，可以允许更多的新应用进入系统以提高系统的资源利用率；相反，当φ ＜0时，需要禁止新应用进入系统执行从而降低系统的资源利用率.

算法2.PID 控制算法.

5.3 应用准入控制器

应用准入控制器的运行过程如算法3 所示.该算法的输入包括系统资源利用率控制变量 φ、准入队列里的应用个数Qaccept、等待队列里的应用个数Qwait.如果系统资源利用率控制变量 φ＞0，此时可以允许更多的新应用进入系统执行以提高系统的资源利用率，因此需要根据EDF 算法对等待队列里的应用排序.对于等待队列里的队头应用Ai，分配给该应用可用于提升系统资源利用率的阈值 φi.根据应用的指令条数来确定 φi，即

换言之，一个应用的指令条数越多，则分配给它的可用于提升系统资源利用率的阈值越大.如果φ-φi＞0成立利用θ ←θ+φi以更新系统当前的资源利用率，利用φ ←φ-φi更新系统资源利用率控制变量.随后，从等待队列中删除队头应用，更新准入队列里应用的个数.当系统资源利用率控制变量 φ＜0 时，输出{φi|1 ≤i≤Qaccept}后退出.

算法3.应用准入控制算法.

5.4 应用映射控制器

应用映射控制器的运行过程如算法4 所示.

算法4.应用映射算法.

算法4 的输入为用于提升系统资源利用率的阈值集合{φi|1 ≤i≤Qaccept}.对于准入队列里的任意一个应用，调用函数CoreIdleCheck来判断系统中是否有处于空闲状态的核心，如果系统存在处于空闲的核心，函数CoreIdleCheck返回值为1，否则返回值为0.如果函数CoreIdleCheck返回值为1，则进入空闲核心分配过程.此时，需要进一步判断 φi是否大于0，如果是，随机分配一个空闲核心给Ai，并计算资源利用率增量 ϱi，更新可用于提升系统资源利用率的阈值 φi.注意到在该过程中，分配给应用Ai的空闲核心的工作频率是由同一个集群中的处于运行状态的核心确定的.应用Ai负载的划分采用平均分配原则，即分配给应用Ai的空闲核心需要执行的指令条数是相等的.当可用于提升系统资源利用率的阈值 φi耗尽时，进行下一次迭代.整个算法在输出准入队列里的应用设计点集合后退出.

5.5 主控制器

主控制算法整合了PID 控制器、应用准入控制器、应用映射控制器，形成一个闭环，有效提高了控制过程对外部干扰的鲁棒性.主控制器的运行过程如算法5 所示.

算法5.主控制算法.

算法5 的输入为在系统动态运行时，新到来的应用集合Aonline={AS+1,AS+2,…,AQ}.算法5 调用算法2以获取系统资源利用率控制变量 φ，调用算法3 获取可用于提升系统资源利用率的阈值集合{φi|1 ≤i≤Qaccept}.接下来，算法5 调用算法4 生成应用调度表并采用EDF 调度器执行应用.

6 实验验证

6.1 硬件平台

本文采用2 种CPU-GPU MPSoC 硬件平台.一种是Hardkernel Odroid-XU3 硬件平台[2]，集成了三星Exynos 5422 MPSoC，包含4 个ARM Cortex A15 核心、4 个ARM Cortex A7 核心、1 个ARM Mali-T628 MP6 GPU.4 个ARM Cortex A15 核心构成了高性能的CPU 大核集群，每个核心都支持步长为100 MHz、200～2 000 MHz之间的多种离散频率.4 个ARM Cortex A7 核心组成了低功耗的CPU 小核心集群，每个核心都支持步长为100 MHz、200～1 400 MHz 之间的不同离散频率.对于ARM Mali-T628 MP6 GPU，它的工作频率从600 MHz，543 MHz，480 MHz，420 MHz，350 MHz，266 MHz，177 MHz 中选取.

除了Hardkernel Odroid-XU3 平台，本文还将三星Exynos 9810 MPSoC[24-25]作为测试硬件平台.Exynos 9810 MPSoC 的CPU 大核集群包含4 个M3 核心，每个核心支持18 种离散的工作频率，包括2652 MHz，2496 MHz，2314 MHz，2106 MHz，2002 MHz，1924 MHz，1794 MHz，1690 MHz，1586 MHz，1469 MHz，1261 MHz，1170 MHz，1066 MHz，962 MHz，858 MHz，741 MHz，704 MHz，650 MHz；CPU 小核集群包含4 个ARM Cortex A55 核心，每个核心支持10 种不同的离散频率，包括1690 MHz，1456 MHz，1248 MHz，1053 MHz，949 MHz，832 MHz，794 MHz，715 MHz，598 MHz，455 MHz；GPU 集群由ARM Mali-G72 MP18 GPU 构成，支持6 种离散的工作频率，包括572 MHz，546 MHz，455 MHz，338 MHz，299 MHz，260 MHz.

对于Hardkernel Odroid-XU3 和Exynos 9810 MPSoC，在系统静态阶段，我们采用热量仿真工具Hot-Spot[26]获取GPU 和任意CPU 核心的温度.在系统动态阶段，为了降低获取温度数值的时间开销，利用片上系统的温度传感器来捕捉核心温度.Hardkernel Odroid-XU3 部署了5 个温度传感器，其中4 个温度传感器分别用来监测4 个ARM Cortex A15 核心的温度，1 个温度传感器用来监测ARM Mali-T628 MP6 GPU的温度.Exynos 9810 MPSoC 同样部署了5 个温度传感器，但只有1 个温度传感器用来测量CPU 大核集群的温度，无法获取CPU 小核集群和GPU 的温度.考虑到无论是CPU 小核集群还是GPU 的工作频率，它们支持的平均工作频率均低于CPU 大核集群支持的平均工作频率，导致CPU 小核集群和GPU 的温度通常低于CPU 大核集群的温度.因此，我们采用与文献[24]和文献[27]类似的做法，在系统动态阶段，忽略对Hardkernel Odroid-XU3 的CPU 小核集群、Exynos 9810 MPSoC 的小核集群和GPU 的温度管理.相应地，在系统动态阶段，只对Hardkernel Odroid-XU3 的CPU大核集群和GPU、Exynos 9810 MPSoC 的大核集群进行使用寿命优化.

6.2 基准应用

如表2 所示，我们从Hetero-Mark OpenCL[28]，PolyBench[29]，PARSEC[30]三个基准应用库选取了16个典型的OpenCL 应用作为测试应用，包括K 均值聚类算法（K-means，KM）、页面排序（page rank，PR）、高级加密标准（advanced encryption standard,AES）、背景提取（background extraction，BE）、颜色直方图制作（color histogramming，CH）、布莱克-舒尔斯模型(Black-Scholes model,BS)、力导的边绑定方法（force directed edge bundling，FDEB）、有限冲激响应滤波器（finite impulse response，FIR）、K 近邻算法（K-nearest neighbors，KNN）、演化规划（evolutionary programming，EP）、二叉查找树插入（binary search tree insertion，BSTI）、基因比对（gene alignment，GA）、二维卷积（convolution-2D，C2D）、对称rank-2k 更新（symmetric rank-2k update，SYR2K）、人体追踪（body track，BT）、内容相似性搜索（content similarity search，CSS）.单个基准应用的指令条数和工作组个数如表2 所示，它的截止期限设置为

6.3 基准算法

为了验证本文算法的性能，我们将基于交叉熵策略的静态算法与延迟感知的集成式热量管理算法[13]（latency-aware integrated thermal management，LITM）、延迟感知的粒子群优化算法[31]（latency-aware particle swarm optimization,LPSO）进行对比.此外，还将基于反馈控制的动态算法与对数曲线拟合算法[14]（logarithmic curve fitting，LCF）和高能效映射重新划分算法[4]（energy efficient mapping and repartitioning，EEMR）进行对比.

1）LITM.一个用于在异构多核平台上对实时OpenCL 应用进行热感知调度的框架，该框架将任务迁移、频率调整、空闲槽插入等多个控制动作视为任务映射参数，通过自适应的方式调整任务映射参数来降低违背温度约束的概率.

2）LPSO.一种旨在降低应用执行时间的静态方法，在应用实时性、系统能耗、处理器温度、系统使用寿命的约束下，采用粒子群优化算法完成应用指令条数的划分、CPU 核心和GPU 核心的频率选择.

3）LCF.一种针对运行在CPU-GPU 集成平台上的应用划分策略，由探索阶段、稳定阶段、最终决策阶段构成，可以动态地将应用负载分配给CPU 和GPU，以同时降低应用的延迟和能耗.但是，它忽视了应用的时序要求和系统的使用寿命需求.

4）EEMR.一种节能的运行时应用映射和划分方法，根据应用的实时性要求，对于每个并发执行的应用程序，映射过程会找到适当数量的 CPU 核心以及CPU 核心和 GPU 核心的运行频率，应用划分过程考虑到了CPU 核心和 GPU 核心之间的负载平衡.然而，它忽视了系统的使用寿命和峰值温度约束.

Table 2 Number of Instruction Cycles and Work-Groups of Benchmarking Applications[28-30]表 2 基准应用的指令条数和工作组个数[28-30]

6.4 实验分析

在本文提出的静态算法中，设置迭代次数gmax=50，每次迭代生成的样本数目Z=50，用于微调的样本数目Y=30.在本文提出的动态算法中，PID 控制器的参数 ℓ1，ℓ2，ℓ3分别设置为0.5，0.05，0.1.

6.4.1 静态算法性能分析

图6 比较了FDEB，FIR，KNN，EP，BSTI，GA，C2D，SYR2K，KM，CSS 共10 个基准应用在Hardkernel Odroid-XU3 硬件平台上执行的延迟.从图6 可以看出，本文提出的静态算法可以有效地降低基准应用的延迟.例如，在执行基准应用EP 时，本文提出的静态算法、基准算法LITM、基准算法LPSO 取得的应用延迟分别为89.41 s，130.30 s，109.71 s.此外，与基准算法LITM 和LPSO 相比，本文提出的静态算法能够将10 个基准应用的平均延迟分别降低29.83%和23.95%.图7 比较了10 个基准应用在Exynos 9810 MPSoC 硬件平台上执行的延迟.与基准算法LITM 和LPSO 相比，本文提出的静态算法将基准应用的平均延迟分别降低了34.58%和25.42%.

Fig.6 Latency achieved by static algorithms when running on the Hardkernel Odroid-XU3 platform图 6 静态算法在 Hardkernel Odroid-XU3 平台上执行实现的延迟

图8 和图9 分别比较了10 个基准应用在Hardkernel Odroid-XU3 硬件平台、Exynos 9810 MPSoC 执行的应用能耗.在图8 中，设置应用的能量预算Ebgt=3 000 J.图8 的数据表明本文提出的静态算法和2 种基准算法都可满足应用总能耗的约束.此外，本文提出的静态算法的应用能耗大于2 种基准算法的应用能耗.类似地，从图9 可知，对于任意应用，本文提出的静态算法的应用能耗大于基准算法的应用能耗.这主要是因为优化能耗和优化延迟是互斥目标，本文提出的静态算法充分利用了给定的能耗预算，以最小化基准应用的延迟.

Fig.7 Latency achieved by static algorithms when running on the Exynos 9810 MPSoC platform图 7 静态算法在 Exynos 9810 MPSoC 平台上执行实现的延迟

Fig.8 Energy consumption achieved by static algorithms when running on the Hardkernel Odroid-XU3 platform图 8 静态算法在 Hardkernel Odroid-XU3 平台上执行实现的能耗

Fig.9 Energy consumption achieved by static algorithms when running on the Exynos 9810 MPSoC platform图 9 静态算法在 Exynos 9810 MPSoC 平台上执行实现的能耗

图10 列出了本文提出的静态算法、基准算法LITM、基准算法LPSO 取得的处理器核心峰值温度.在本组实验中，将Hardkernel Odroid-XU3 和Exynos 9810 MPSoC 的峰值温度阈值分别设置为70℃和90℃.从图10 可以发现，无论是Hardkernel Odroid-XU3 还是Exynos 9810 MPSoC 硬件平台，本文提出的静态算法和2 种基准算法都可以满足峰值温度的约束.图11 给出了本文提出的静态算法、基准算法LITM、基准算法LPSO 取得的系统使用寿命.在这组比较实验中，将Hardkernel Odroid-XU3 和Exynos 9810 MPSoC 使用寿命需求分别设置为16 年和18 年.如图11 所示，无论是Hardkernel Odroid-XU3 还是Exynos 9810 MPSoC 硬件平台，本文提出的静态算法和2 种基准算法都可以满足使用寿命的约束，并且本文提出的静态算法充分利用了给定的使用寿命阈值，以优化应用的延迟.

Fig.10 Peak temperature of processor cores achieved by static algorithms图 10 静态算法实现的处理器核心峰值温度

Fig.11 Lifetime achieved by static algorithms图 11 静态算法实现的使用寿命

6.4.2 动态算法性能分析

图12 比较了3 种动态算法在Hardkernel Odroid-XU3 硬件平台上执行6 个基准应用BT，PR，AES，BE，CH，BS 时的应用延迟.由图12 可知，与基准算法LCF 和EEMR 相比，本文提出的动态算法可以将基准应用的平均延迟分别降低23.47%和24.89%.进一步地，图13 探究了3 种动态算法在Exynos 9810 MPSoC硬件平台上执行6 个基准应用时的应用延迟.与图12展示的结果类似，本文提出的动态算法在Exynos 9810 MPSoC 硬件平台上实现的性能仍然优于基准算法LCF 和EEMR.

Fig.12 Latency achieved by dynamic algorithms when running on the Hardkernel Odroid-XU3 platform图 12 动态算法在 Hardkernel Odroid-XU3 平台上执行实现的延迟

Fig.13 Latency achieved by dynamic algorithms when running on the Exynos 9810 MPSoC platform图 13 动态算法在 Exynos 9810 MPSoC 平台上执行实现的延迟

图14 展示了3 种动态算法在Hardkernel Odroid-XU3 硬件平台上执行基准应用BT，PR，AES，BE，CH，BS 时的能耗.在这组实验中，设置应用的能量预算Ebgt=3 000 J.从图14 可以看出，与基准算法LCF 和EEMR 相比，本文提出的动态算法在执行单个应用时消耗了更多的能量，但是消耗的总能量没有超过给定的能量预算.进一步地，图15 展示了3 种动态算法在Exynos 9810 MPSoC 硬件平台上执行基准应用时的能耗.在这组实验中，设置应用的能量预算Ebgt=2 000 J.由图15 可知，本文提出的动态算法消耗的总能量依然没有超过给定的能量预算.

Fig.14 Energy consumption achieved by dynamic algorithms when running on the Hardkernel Odroid-XU3 platform图 14 动态算法在 Hardkernel Odroid-XU3 平台上执行实现的能耗

Fig.15 Energy consumption achieved by dynamic algorithms when running on the Exynos 9810 MPSoC platform图 15 动态算法在Exynos 9810 MPSoC 平台上执行实现的能耗

图16 探究了本文提出的动态算法、基准算法LCF、基准算法EEMR 取得的处理器核心峰值温度.在本组实验中，Hardkernel Odroid-XU3 和Exynos 9810 MPSoC 的峰值温度阈值仍然分别为70℃和90℃.由图16 可知，本文提出的动态算法执行6 个基准应用时，均未超过硬件平台设定的峰值温度阈值.相反，基准算法LCF 和EEMR 都超过了硬件平台设定的峰值温度阈值.图17 比较了本文提出的动态算法和基准算法LCF、基准算法EEMR 取得的系统使用寿命.在这组对比实验中，Hardkernel Odroid-XU3 和Exynos 9810 MPSoC 的使用寿命需求仍然分别设置为16 年和18 年.由图17 可知，本文提出的动态算法在执行6 个基准应用时，始终没有违背系统使用寿命约束，而基准算法LCF 和EEMR 均不能满足使用寿命需求.

Fig.16 Peak temperature of processor cores achieved by dynamic algorithms图 16 动态算法实现的处理器核心峰值温度

Fig.17 Lifetime achieved by dynamic algorithms图 17 动态算法实现的使用寿命

图18 比较了本文提出的动态算法和基准算法LCF、基准算法EEMR 生成任务调度表的运行时间.从图18 看出，本文提出的动态算法可以降低生成任务调度表的运行时间.例如，当运行在Hardkernel Odroid-XU3 平台时，本文提出的动态算法与基准算法LCF 和EEMR 相比，运行时间分别降低了23.47%和30.92%；当运行在Exynos 9810 MPSoC 时，本文提出的动态算法与LCF 和EEMR 相比，运行时间分别降低了24.71%和32.63%.