一种基于强化学习的异构信息物理系统中考虑竞争因素的协同调度方法

《Computer Communications》：A reinforcement learning approach to contention-aware co-scheduling in heterogeneous cyber-physical systems

　　Shaima Rahim|Navaneeth V. Sankar|Piyoosh Purushothaman Nair|Rajesh Devaraj•RL-TMC将蒙特卡洛强化学习与考虑竞争的DTG调度策略相结合。•智能体通过周期性奖励来学习任务优先级，从而优化总完成时间。•启发式解码机制负责处理处理器分配以及共享总线上的竞争问题。•与现有的最佳启发式方法相比，该算法平均能将总完成时间减少17%。•通过汽车硬件上的自适应巡航控制案例研究对其实效进行了验证。

引言
网络物理系统包括汽车电子、航空电子平台、工业自动化以及智能能源基础设施，这类系统由紧密耦合的物理过程和嵌入式计算子系统组成。这些系统在分布式计算平台上执行感知、控制及驱动功能，其中的计算与通信活动彼此深度关联。由于各功能组件之间存在数据依赖关系，许多网络物理系统应用自然可以被建模为DTG，其中节点代表计算任务或通信消息，而边则体现优先级约束[1]、[2]。

随着功能复杂度的提升以及对时间要求的严格化，现代网络物理系统已从同构多处理器架构转向异构分布式平台[3]、[4]。这类平台集成了多种处理单元，如通用CPU、DSP、GPU以及专用加速器，它们通过CAN、FlexRay、LIN、TSN和以太网等共享通信介质相互连接[5]、[6]。例如，现代汽车平台可能包含数十个电子控制单元，这些单元通过总线网络和交换式网络相互连接[7]、[8]。这种架构上的多样性使得系统的执行和通信特性存在很大差异，因此高效地调度任务和消息成为一项关键挑战。

对于给定的DTG和异构分布式平台，调度问题需要确定：(i)计算任务的处理器分配方案，(ii)通信消息的总线分配方式，以及(iii)各自的启动时间，同时还要满足所有的优先级和资源约束条件。通常，其核心目标是最小化总完成时间，即最后一个任务完成的时间。在异构平台上进行DTG调度属于NP完全问题[9]，尽管整数线性规划可以精确描述所有约束条件，但其指数级的计算复杂度使得该方法仅适用于规模较小的问题[10]、[11]。

在许多网络物理系统领域，尤其是汽车和航空电子系统中，控制功能会在系统长期运行过程中定期执行[8]、[12]。对于这类系统，静态调度更为理想，因为它能够避免运行时的调度开销，并便于进行大规模的离线优化[13]。因此，以往的研究大多聚焦于基于启发式的静态调度技术，这类技术以牺牲最优性为代价来换取更好的可扩展性。在这些技术中，HEFT、PEFT和IPPTS等列表调度算法因其较低的计算复杂度而被广泛采用[14]、[15]、[16]、[17]。然而，大多数传统的列表调度器都假设通信网络是完全连通的，且忽略了共享通信资源上的竞争问题。而在实际的网络物理系统中，共享总线极为常见，通信竞争会显著影响调度的可行性和性能[1]、[18]。实验研究表明，忽视通信竞争会导致总完成时间出现明显恶化[19]。为了解决这一问题，已有不少考虑竞争因素的DTG调度启发式方法被提出[20]、[21]。虽然这些方法明确考虑了共享总线的竞争问题并提升了调度的可行性，但由于其贪婪且确定性的特点，难以探索其他可能的任务执行顺序，尤其是在处理大规模DTG时更是如此。随着网络物理系统的工作负载规模和复杂性不断提升，人们越来越需要这样一种调度机制：它既能系统地探索所有可行的任务排序方案，又能保持考虑竞争因素的启发式方法所具备的强可行性保障[22]、[23]、[24]。

为了解决这些问题，本文提出了RL-TMC，这是一种静态调度框架，它将蒙特卡洛强化学习与一种能够考虑竞争因素的任务和消息调度策略相结合。RL-TMC的核心在于生成与DTG的可行拓扑顺序相一致的任务优先级列表，随后通过一个确定性的解码阶段，根据任务优先级、处理器独占性以及共享总线竞争等约束条件，将这些学到的优先级列表转化为有效的调度方案。由于调度的质量只有在任务全部完成后才能确定，因此该系统采用了基于总完成时间改进情况的稀疏周期性奖励信号，这种结构非常适合蒙特卡洛强化学习方法的使用。为了提升在不同规模DTG上的可扩展性，训练过程还引入了一种基于收敛性的自适应终止机制，一旦策略稳定，就会停止进一步探索。本文的主要贡献如下：
•学习辅助调度框架：我们提出了RL-TMC，这是一种学习辅助型的静态调度方法，它将蒙特卡洛强化学习与考虑竞争因素的任务和消息调度策略相结合，用于改善在异构共享总线平台上的DTG调度性能。
•基于蒙特卡洛的任务优先级学习：该调度问题被构建为一个周期性决策过程，在这个过程中，学习智能体会逐步构建出符合拓扑结构的任务优先级列表。来自总完成时间改进情况的稀疏终端奖励能够引导学习过程，无需对资源层面的约束条件进行显式建模。此外，还有一种基于自适应收敛性的停止机制，能够根据问题的复杂程度动态调整训练时长。
•考虑竞争因素的确定性解码：学到的优先级列表会通过一种考虑竞争因素的启发式调度器进行解码，以此确保正确的处理器分配、消息调度，同时也能妥善处理共享总线上的竞争问题。
•全面的实验评估：在多个基准DTG上进行的广泛实验表明，RL-TMC的表现始终优于现有的最佳考虑竞争因素的启发式方法，在最佳情况下总完成时间可减少28%，平均而言也能带来约17%的改善，尤其是在处理通信密集型任务时效果更为显著。
•实际的汽车行业案例研究：通过在具有异构共享总线的汽车平台上开展自适应巡航控制案例研究，验证了所提出框架的实际应用价值。

本文的其余部分结构如下：第2节回顾了关于异构平台上DTG调度的相关研究；第3节介绍了系统模型及相关假设，第4节则给出了问题的正式表述；第5节阐述了强化学习的初步知识；第6节详细描述了所提出的RL-TMC框架，包括其学习模型和调度流程；第7节介绍了实验方法及性能评估方式；第8节通过基于自适应巡航控制应用的汽车案例，展示了该框架的实际应用效果；最后，第9节对全文进行总结。

相关研究
在文献中，关于在异构计算平台上调度DTG的研究已经非常丰富[25]、[26]。早期的研究主要致力于寻找能够在异构执行环境下最小化总完成时间的最优模型和启发式策略。Liu等人[27]提出了一种针对部署在异构多核集群上的DTG的任务分配方法，旨在降低其总完成时间。Kanemitsu等人[28]则提出了一种整数线性规划模型，用于实现异构平台上DTG的最优调度。

系统模型
本节介绍了本文所分析的系统模型，包括目标执行平台、应用计算模型，以及所提出的调度方法所依据的假设条件。

整数线性规划模型
本节给出了在具有共享总线的异构平台上对DTG进行考虑竞争因素调度的整数线性规划模型。该模型能够明确体现任务执行、任务间通信、优先级约束，以及共享计算和通信资源上的竞争情况。由于整数线性规划存在指数级的最坏情况复杂度，因此它仅被用作最优性对比的基准，同时也为后文介绍的学习型调度框架提供了理论依据。

蒙特卡洛强化学习：初步知识
所提出的RL-TMC框架采用了蒙特卡洛强化学习作为启发式搜索机制，用于优化DTG调度中的任务执行顺序。调度问题本质上属于周期性问题：只有在构建出完整的任务优先级列表并将其转换为可行的调度方案之后，才能评估任务选择决策的质量。这一特性使得蒙特卡洛方法尤为适用，因为它们可以通过观察到的反馈值来估算动作的价值。

RL-TMC
本节介绍了RL-TMC，这是一种用于在异构平台上调度DTG的学习辅助型方法。该算法分为两个阶段运作。在第一阶段，学习智能体会利用蒙特卡洛强化学习逐步构建出更优的任务执行顺序，也就是所谓的任务优先级列表。在第二阶段，一种基于列表调度框架开发的确定性、考虑竞争因素的调度器会负责为各种计算任务和通信消息分配合适的处理器。

实验方法与评估框架
为了验证所提出的基于强化学习的调度器RL-TMC的性能，我们在不同配置的异构分布式任务图上开展了大量实验。评估过程中使用了人工生成的基准测试案例，这些案例能够实现对应用特性和系统资源的可控调整，从而涵盖多种不同的计算和通信行为模式。

案例研究：自适应巡航控制器
为展示所提出的基于强化学习的调度框架的实际应用价值，我们以汽车系统中常用的自适应巡航控制应用为例进行了案例分析。自适应巡航控制系统能够自动维持车辆的目标速度，同时通过根据周围车况动态调整车辆的加速和减速速度，从而确保车辆之间保持安全的间距。

结论与未来工作
本文研究了在通过共享通信总线相互连接的异构分布式平台上调度DTG的问题。文中提出了整数线性规划模型，作为考虑竞争因素的任务和消息调度的参考模型，该模型能够涵盖任务执行、通信、优先级以及共享资源约束等各个方面。但由于整数线性规划存在指数级复杂度，它仅适用于规模较小的问题，主要作用是作为最优性对比的基准。为了解决这一限制，未来的研究需要……