针对异构多处理器上半预知混合关键性系统的热感知与能效调度

《Sustainable Computing: Informatics and Systems》：Thermal-aware and energy-efficient scheduling for semi-clairvoyant mixed-criticality systems on heterogeneous multiprocessors

　　摘要
混合关键性系统（MCS）被广泛应用于安全至关重要的嵌入式平台中，这些平台中具有不同保障级别的任务共享有限的计算资源。随着现代多核处理器功率密度的增加，能耗和热管理已成为混合关键性调度中的关键挑战。由于能耗和处理器温度紧密相关，仅优化能耗不足以有效控制峰值温度。尽管现有研究独立地探讨了节能调度或热感知技术，但在半可视混合关键性系统中（特别是在异构多处理器平台上），它们的联合优化仍然很大程度上未被探索。本文提出了一种用于不精确混合关键性任务的两阶段热感知和能效调度框架。在离线阶段，开发了一种节能任务划分算法，将任务映射到异构处理器上，在确保可调度性的同时最小化能耗。在在线阶段，利用半可视执行信息回收动态空闲时间，并将其分配给具有更高稳态温度的任务，从而通过动态电压和频率调节降低峰值处理器温度。在异构混合关键性任务集上的广泛模拟表明，与最强的竞争基线WFOPTRA（CU-WFD划分结合我们的在线空闲时间回收算法OPTRA）相比，所提出的框架可将系统能耗降低多达11.75%，峰值处理器温度降低多达6.49°C；与未管理的First-Fit EDF基线（FFEDF）相比，相应的降低幅度达到13.76%和7.61°C。这些改进是在可忽略的在线开销下实现的。我们还提供了在异构频率和半可视模式转换下进行空闲时间回收的形式化可调度性保证。

引言
混合关键性系统（MCS）[1]在共享计算平台上集成了具有不同保障级别的任务，并已成为现代嵌入式系统的基本设计范式。这些系统广泛应用于航空航天、汽车控制和医疗设备等安全关键领域，在这些领域中，具有不同关键性级别的任务必须共存于同一硬件平台上。混合关键性任务模型最初由Vestal [2]引入，根据任务的保障级别为它们分配不同的最坏情况执行时间（WCET）估计，并允许系统在高关键性任务超过其低置信度执行预算时切换执行模式。这种机制在保持高关键性任务所需的安全保障的同时，实现了高效的资源共享。
大量研究调查了MCS的调度技术。早期研究主要集中在保证不同关键性模式下的时间正确性。随后，研究人员通过将动态电压和频率调节（DVFS）技术纳入MCS [3]来探索节能调度。这些方法通过根据系统工作负载调整处理器频率来减少能耗。同时，热感知调度引起了越来越多的关注，旨在通过在执行过程中考虑处理器温度动态来缓解热热点问题。然而，大多数现有工作独立考虑了能耗优化和热管理。此外，许多研究专注于单处理器平台或传统的非可视模型，在这些模型中，任务执行时间直到完成之前都是未知的。半可视调度 [4] 被引入，其中作业可以在到达时确定它是否可以在其低置信度WCET内完成。这种额外的执行信息使得调度决策更加高效，特别是在动态空闲时间回收和DVFS方面。
现有研究通常分别考虑能耗优化或热管理。然而，在异构多处理器混合关键性系统中，这两个方面是根本相互依赖的。任务分配决策决定了处理器的工作负载和基础能耗，这反过来又通过功率损耗影响温度。同时，运行时调度决策影响瞬态热行为和峰值温度。当存在半可视信息时，这种互动变得更加显著，因为执行时间意识使得动态空闲时间回收和DVFS成为可能。因此，能耗、温度演变和调度决策在离线和在线阶段都是紧密耦合的。因此，单独优化这些方面是不够的。相反，需要一个统一的调度框架，该框架同时考虑节能分配和热感知的运行时控制。
为了解决这些挑战，本文提出了一种用于异构多处理器上半可视混合关键性系统的热感知和能效调度框架。所提出的框架包括两个协调阶段。在离线阶段，我们开发了一种节能任务划分算法，该算法根据任务活动因素和处理器功率特性将任务映射到处理器上，从而在确保可调度性的同时减少系统能耗。在在线阶段，我们利用半可视执行信息回收由任务提前完成产生的动态空闲时间，并将其分配给具有更高稳态温度的任务。通过基于回收的空闲时间动态调整处理器频率，所提出的方法在运行时有效降低了峰值处理器温度。
这项工作超越了传统方法，将在异构多处理器上的半可视混合关键性模型下将能耗和热管理视为一个联合优化问题，而不是分别处理它们。这项工作的新颖性不仅在于各个算法组件，还在于协调设计，它捕捉了半可视调度下能耗和热动态之间的相互作用。核心洞察是，能耗优化和热管理在不同的时间尺度上运作。节能任务分配决定了处理器间的长期功率分布，而热感知的运行时调度则解决了短期温度波动问题。通过协调这两个层面，所提出的框架实现了更有效的系统级优化。
据我们所知，这项工作是第一个同时解决以下四个维度的：(i) 异构多处理器平台，(ii) Agrawal等人[4]提出的半可视任务模型，(iii) 具有优雅降级的不精确混合关键性（IMC）模型[5]、[6]、[7]，以及(iv) 联合能耗/热管理优化。这种组合新颖性正好体现在这个交叉点：之前的热感知MCS工作（Li等人[8]、Ranjbar等人[9]、[10]、Safari等人[11]以及我们之前的工作[12]）最多只涵盖了这四个维度中的三个，而异构性特别需要新的任务-处理器匹配分析（第5.2节）和每个核心的热限制（第5节）。
本文的主要贡献可以总结如下：
- 我们为异构多处理器上的半可视不精确混合关键性任务制定了一个联合能耗-热管理优化问题，明确考虑了任务分配、执行动态和热行为之间的相互作用。
- 我们提出了一种两阶段调度框架，该框架将节能任务划分与热感知的运行时空闲时间回收相结合，以协调离线资源分配和在线温度管理。这包括：一种节能任务划分算法，它在满足可调度性约束的同时最小化系统能耗；以及一种在线峰值温度降低策略，该策略利用动态空闲时间回收来降低峰值温度。
- 广泛的仿真结果表明，与现有的基线调度策略相比，所提出的方法有效降低了系统能耗和峰值处理器温度。
定量上，所提出的框架在能耗方面比最强的竞争基线WFOPTRA（结合了最先进的Criticality-Unaware Worst-Fit Decreasing (CU-WFD) [13]划分和我们的在线空闲时间回收算法OPTRA）高出11.75%，在峰值处理器温度方面高出6.49°C。与未管理的First-Fit EDF基线（FFEDF）相比，相应的降低幅度分别达到13.76%和7.61%。第6节报告了对两种划分策略（First-Fit和CU-WFD）和两种在线策略（plain EDF和OPTRA）的完整2 × 2消融测试。额外的在线成本主要由标准的???(log???) EDF优先级队列更新所主导。表1包括本文中使用的主要符号。
本文的其余部分组织如下。第2节回顾了相关工作。第3节介绍了系统模型和初步知识。第4节阐述了问题并提供了可调度性分析。第5节介绍了所提出的调度算法。第6节通过仿真评估了该方法，第7节总结了本文。

半可视任务模型
在传统的MCS任务模型中，当HI任务的执行时间超过其LO模式WCET时，会触发系统模式切换。Agrawal等人[4]引入了半可视任务模型，与传统非可视模型相比提供了额外的执行信息。具体来说，作业可以在到达时确定它是否可以在其LO模式WCET内完成。如果不是，则该作业在其到达时触发从LO模式到HI模式的系统模式切换。

任务模型
我们关注在包含??个异构处理器??={????|1≤??≤??}的多处理器平台上基于EDF的半可视抢占式调度。每个处理器可以表示为????={??????????,????3??2????,????,????}，并且支持DVFS，其中??????????是????上的最大标准化处理器频率。我们假设处理器????可以提供?个离散频率。
MCS任务集??包含??个独立的偶发实时任务，表示为??={????|1≤??≤??}。在我们的分析中，

可调度性分析
任务????在处理器????上以离线初始频率????3??3??3??执行，从可用处理器频率集合（????3??3??3??∈[??????????,??????????]中选择。

引理2
LO任务????和HI任务????在频率????3??3??下的执行需求计算如下：
??3??3??′2(????,????,??)=????2(??)?????2(??2??)????3??2??3??+??3??3??2(????2(??)),??????????+1)?(????2(??3??)?????2(??2??))????3??3??3??,
??3??3??′2(????,????,??)=????2(??)?????2(??3??)????3??3??3??+????2(???????)?(????2(??2??)?????2(??3??))????3??3??,
其中????2(??)=??3????3(?????????????+1,0)是在任何连续时间间隔??内任务????的最大数量。

能量感知任务分配和在线调度方案
这两个阶段如何互动。离线EAPMC算法（第5.2节）通过为每个任务????选择满足引理3的可调度性测试的主处理器????和离线频率????3??3??来固定长期热/能耗基线。在线OPTRA算法（第5.3节）通过利用半可视空闲时间来细化这个基线：每当任务提前完成时，产生的空闲时间就会被捐赠给具有最高稳态温度的就绪队列任务（公式(38)）。

性能评估
我们根据两个关键指标评估所提出的方法：标准化能耗和峰值处理器温度。为了分离EAPTR（能量感知任务分配和热感知空闲时间回收）每个组件的贡献，我们比较了四种基线，这些基线涵盖了两种划分策略（First-Fit vs. CU-WFD [13]）和两种在线调度策略（plain EDF vs. 我们的OPTRA）的2 × 2消融测试：
- FFEDF：任务使用First-Fit (FF)划分进行分配。

结论
在本文中，我们提出了EAPTR，这是一种用于异构多处理器平台上半可视模型下半精确混合关键性（IMC）任务的两阶段能量和热感知调度框架。离线阶段通过将具有较高泄漏功率耗散因子的任务分配给具有较低功率耗散因子的处理器来执行能量感知任务划分（EAPMC），从而在保持可调度性的同时最小化基础动态能耗。在线阶段应用CRediT作者贡献声明
Zhang Yi-Wen：撰写——原始草案、验证、资源收集、调查、资金获取、正式分析。Ma Jin-Peng：撰写——原始草案、软件、调查。Gu Zonghua：撰写——原始草案、调查、正式分析。

利益冲突声明
不存在利益冲突。

致谢
本项工作得到了中国福建省自然科学基金（项目编号2023J01139）和中国中央高校基本研究经费（项目编号ZQN-1009）的支持。

Zhang Yi-Wen | Ma Jin-Peng | Gu Zonghua
中国华侨大学计算机科学与技术学院