异构处理器上部分可复制任务链的能耗感知调度策略

《Parallel Computing》:Energy-aware scheduling strategies for partially-replicable task chains on heterogeneous processors

【字体: 大 中 小 】 时间:2026年09月30日 来源:Parallel Computing 1.1

编辑推荐:

   摘要 异构(或混合)多核架构的到来为应用程序带来了新的性能权衡,同时也为系统提供了效率机会。此外,它们还增加了与线程调度相关的挑战,因为任务的执行时间会根据其放置在大核(性能核)或小核(能效核)上而有所不同。在本文中,我们专注于异构多核处理器给部分可复制任务链(如软件定义无线

  

摘要
异构(或混合)多核架构的到来为应用程序带来了新的性能权衡,同时也为系统提供了效率机会。此外,它们还增加了与线程调度相关的挑战,因为任务的执行时间会根据其放置在大核(性能核)或小核(能效核)上而有所不同。在本文中,我们专注于异构多核处理器给部分可复制任务链(如软件定义无线电 (SDR) 中实现数字通信标准的任务链)带来的挑战。我们的目标是在最大化这些任务链吞吐量的同时最小化其功耗。我们将此问题建模为一种流水线工作流调度问题,在两种类型的资源上使用流水线和复制并行性,其目标是 minimize 周期并使用尽可能多的小核。我们提出了两种贪心启发式(FERTAC 和 2CATAC)和一种最优动态规划(HeRAD)解决方案来解决该问题。我们使用合成任务链评估了我们的解决方案,并比较了其调度的质量(周期和资源利用率)及其执行时间。我们还研究了基于 StreamPU 运行时的开源 DVB-S2 通信标准实现。涵盖了 ARM、Apple、AMD 和 Intel 平台的主流处理器厂商。评估了实现的吞吐量和能耗。我们的结果展示了不同提出解决方案的优缺点。平均而言,FERTAC 和 2CATAC 实现了近最优的解决方案,其周期比最优解(HeRAD)差不到 10%,使用的额外核心少于 2 个。这三种调度策略现在使 StreamPU 的程序员和用户能够透明地利用异构多核处理器,并实现平均比理论最大值相差不到 6% 的吞吐量。在 DVB-S2 接收机上,还表明异构解决方案在能源效率方面平均比最佳同构解决方案高出 8%。

引言
由不同类型核心(也称为异构、混合或非对称)组成的多核处理器架构如今越来越常见。这可能始于 2011 年 ARM 的 big.LITTLE 架构的低功耗处理器 [1],现已存在于 Apple(自 2020 年起)、Intel(自 2021 年起)[2] 和 AMD(自 2023 年起)生产的处理器中。这些处理器的一个共同特征是高性能(或大)核和高能效(或小)核之间共享指令集架构 (ISA),这使得应用程序可以在两种类型的核心上透明执行。

异构多核架构具有多种优势,例如提供了在不需要时关闭大核以节省能源的机会(出于电池或环境原因)。研究还表明,在固定预算(无论是面积、功耗还是两者)下,它们优于同构架构 [3], [4]。我们邀请读者查阅 Mittal 对这些处理器的综述 [5] 以获取更多信息。这些优势伴随着编程复杂性增加的缺点,因为为这些架构编程并行应用程序时,必须决定如何在不同的核心和核心类型之间平衡工作负载。换句话说,如果不考虑它们差异的解决方案可能会导致性能降低和能耗增加。

在这种背景下,我们关注一种由部分可复制任务链组成的并行应用程序的特殊特性。任务链表示具有线性依赖关系的任务序列(即,除了源任务和 sink 任务外,所有任务都有一个后继者和一个前驱者)。当任务链中只有一些任务可以被复制时(即,同一任务的多个副本可以同时处理不同的数据集以提高吞吐量),该任务链被认为是部分可复制的。例如,在软件定义无线电 (SDR) [6] 的数字通信标准背景下可以找到这些任务链。我们考虑在异构多核处理器上调度这些流式任务链的问题,以透明地优化其吞吐量和功耗,减少程序员和终端用户的复杂性。

本工作初步版本出现在第 34 届计算异构性研讨会 (HCW 2025) 上,作为第 39 届 IEEE 国际并行与分布式处理研讨会的一部分 [7]。在本文中,我们 (I) 提供了优化问题的表述;(II) 提出了两种贪心启发式和一种最优动态规划解决方案;以及 (III) 使用模拟和现实世界的数字通信标准(DVB-S2 [8])评估了这些解决方案的性能。在本文中,我们扩展了初步工作 [7],具有以下贡献:
• 我们通过综合示例说明了提出的调度算法;
• 我们提供了动态规划解决方案的最优性证明;
• 我们提供了关于用于现实世界实验的 StreamPU 运行时的额外信息,特别是关于其内部实现;
• 我们考虑了两个基于 ARM 和 AMD 处理器的额外平台;
• 我们评估了不同解决方案的功耗和能源效率;
• 我们测量了不同线程放置(固定)策略对吞吐量的影响;
• 我们实现了一个基于由操作系统管理的每块一线程调度的新基线。

本文其余部分组织如下:第 2 节讨论相关工作。第 3 节提出了问题的表述。第 4 节新贪心启发式:FERTAC 和 2CATAC、第 5 节最优动态规划解决方案详细介绍了我们提出的调度解决方案。第 6 节涵盖模拟和分析结果,而第 7 节介绍了重要的运行时特性。最后,第 8 节提供了 DVB-S2 SDR 接收机的现实世界实验,第 9 节总结了本文。

章节片段
相关工作
我们主要关注部分可复制任务链的吞吐量优化问题。我们关注使用流水线和复制并行性以及区间映射 [9] 的解决方案。流水线通过使不同的依赖任务能够同时处理不同的数据集来改善吞吐量,为原本顺序执行的执行添加了并行性。同时,复制通过让任务的多个副本同时处理不同的数据集来改善吞吐量,从而
问题定义
在两种资源上最大化任务链吞吐量的问题可以建模为流水线工作流调度问题 [9]。工作流可以描述为 ?? 个任务 ??={??1,…,????} 的线性链,这意味着 ???? 只能在 ?????1 之后执行。任务被划分为两个子集 ?????????? 和 ??????????,分别为可复制(无状态)任务和顺序(有状态)任务。顺序任务由于其内部状态而不能被复制(即,复制会导致错误结果)。
计算
新贪心启发式:FERTAC 和 2CATAC
我们提出了两种启发式来在两种类型的资源上调度部分可复制任务链。它们都基于 OTAC [10],后者能够找到同构资源的最优解决方案。简而言之,OTAC 使用二分搜索来设定目标周期(类似于算法 2),然后尝试通过尽可能多地将任务装入每个阶段来贪心地构建调度(如算法 3 所示)。我们的新启发式,名为 FERTAC 和 2CATAC,使用不同的手段来最小化周期,同时
最优动态规划解决方案
本节首先介绍我们的动态规划解决方案,然后证明该解决方案的最优性。我们的动态规划解决方案可以基于此问题的递推进行定义。设 ????(??,??,??) 为将任务从 ??1 映射到 ???? 时,使用多达 ?? 个大核和 ?? 个小核时实现的最佳周期。????(??,??,??) 可以使用公式 (4) 中的递推进行计算,其中 ????(0,??,??)=0,且当 ??>0 时 ????(??,0,0)=∞。
????(??,??,??)=min??∈[1,??]??{ {?{ {?min??∈[1,??]?(max?(????(???1,?????,??),???([????,????],??,?)))
min??∈[1,??]?(max?(????(???1
模拟与分析结果
在本节中,我们研究合成任务链和处理器,以检查策略能够多大程度上优化我们的两个目标,并分析它们的执行时间。比较包括我们的三种策略和 OTAC [10](仅处理同构资源)。我们在接下来的小节中提供了关于实验环境和结果的更多细节。源代码、结果文件和脚本可在线免费获取 [27]。
运行时系统
上一节介绍了忽略通信和同步开销的分析结果。在本节中,我们概述了运行时实现的主要方面,它作为 StreamPU 开源项目 [6] 的一部分提供。
现实世界 SDR 实验
在本节中,我们采用我们的三种策略和 OTAC [10] 在 StreamPU [6] 和四种异构多核处理器上调度 DVB-S2 数字通信标准 [8] 的实现。然后,我们评估它们的吞吐量、能耗以及线程固定策略对性能的影响。我们在接下来的小节中提供了关于实验环境和结果的更多细节。源代码、结果文件和脚本可在线免费获取 [29]。
结论
在本文中,我们考虑了在异构多核处理器上调度部分可复制任务链的问题,以优化吞吐量(最小化周期)和功耗(使用尽可能多的小核)。我们提出了两种贪心策略(FERTAC 试图尽早使用小核,2CATAC 试图在每个阶段使用两种核心类型)和一种最优动态规划策略(HeRAD)。图 14 总结了它们的主要特征,基于
CRediT 作者贡献声明
Yacine Idouar: 撰写 - 原稿,软件,调查,概念化。Adrien Cassagne: 撰写 - 审查与编辑,撰写 - 原稿,监督,软件,概念化。Laércio L. Pilla: 撰写 - 审查与编辑,撰写 - 原稿,监督,软件,概念化。Julien Sopena: 监督,调查,概念化。Manuel Bouyer: 软件,硬件,资源。Diane Orhan: 撰写 - 原稿,概念化。Lionel Lacassagne:
利益冲突声明
作者声明以下可能被视为潜在利益冲突的财务利益/个人关系:Yacine Idouar 报告财务支持由法兰西岛航天学院 (Académie Spatiale d'?le-de-France) 提供。如果有其他作者,他们声明没有已知的竞争性财务利益或个人关系,这些利益或关系可能会影响本报告中报告的工作。
致谢
本工作得到了 France 2030 通过名为法兰西岛航天学院 (https://academiespatiale.fr/) 的项目的支持,该项目由国家研究局管理,参考文献编号为 ANR-23-CMAS-0041。
Yacine Idouar|Adrien Cassagne|Julien Sopena|Manuel Bouyer|Diane Orhan|Lionel Lacassagne|Christophe Jégo
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号