BLSA：一种基于缓存意识的任务图均衡负载调度方法

《Future Generation Computer Systems》：BLSA: A cache-aware balanced load scheduling approach on task graphs

　　刘家正|刘松|李飞|聂世强|王金宇|吴伟国
中国陕西省西安市西安交通大学西安南二路28号，邮编710049

摘要
任务图被广泛用于描述具有依赖关系的计算任务，如数值模拟和模型训练。如何在多核处理器上基于任务图来调度任务，以充分利用计算资源，已成为越来越重要的问题。然而，当前的研究往往忽视了共享缓存竞争问题。在任务图调度过程中，由缓存竞争导致的性能下降常常被忽略。本文提出了一种考虑缓存的平衡负载调度方法（BLSA），旨在缓解最后一级缓存（LLC）的竞争状况并缩短任务执行时间。在BLSA中，我们首先提出了一种生成平衡负载标准的算法，调度器可利用该标准来减轻缓存竞争。此外，我们还设计了一种基于任务图的动态调度算法，该算法在考虑任务局部性和执行时间的同时，不会违反任务图中的依赖关系。实验结果表明，在四种不同的任务图拓扑结构和多种类型的任务中，与先来先服务（FCFS）相比，BLSA最多可将任务执行时间缩短16.22%，降低LLC缓存未命中率24.77%。与另外三种先进的任务图调度算法相比，BLSA在典型场景下平均可使任务执行时间缩短8.89%，降低LLC缓存未命中率13.24%，在大规模、高竞争环境下效果更为显著。

引言
在许多科学计算应用以及人工智能模型的训练/推理框架中[1]、[2]、[3]，任务都是严格按照其依赖关系有序执行的。有向无环图（DAG）[4]、[5]、[6]、[7]被用作任务图模型，用来描述任务之间的依赖关系。对于任务图调度而言，DAG的拓扑结构限制了任务的合法执行顺序，从而影响调度算法的性能。由于执行过程中性能会波动，无法准确预测任务的到达顺序，因此调度算法需要在运行时处理新准备就绪的任务。这就使得静态调度算法难以分析和预测任务图的最优调度顺序。关于任务图调度的研究[8]、[9]、[10]通常会考虑图的拓扑结构及关键路径，以便充分利用计算资源以提高执行性能。但这些研究忽略了共享缓存竞争所带来的性能下降问题。由于共享缓存资源容量有限，若在调度时不考虑任务的缓存需求，那么在多核系统上执行任务时就可能会引发缓存竞争。虽然多核系统通过提供更多的计算核心和并行化机会，大大提升了计算应用的执行性能，但同时也带来了缓存竞争的问题[11]。缓存干扰分为两种类型：核心内干扰和核心间干扰[12]。有研究[13]表明，当多个任务在多核处理器上同时执行时，缓存竞争会显著增加缓存未命中次数，进而导致额外的内存访问，从而使性能下降。因此，在调度过程中考虑任务组合之间的缓存资源竞争是非常重要的。关于考虑缓存的调度研究[14]、[15]、[16]通常会设计一些策略，利用任务的局部性特征来减轻调度过程中的共享缓存竞争。在大多数研究中，都假设任务之间是相互独立的，没有依赖关系。但在任务图中，大多数任务必须在其前置任务完成后才能被调度。尽管实时调度研究会考虑任务依赖约束，但其主要目标是提高系统吞吐量[17]和成功率[18]，以确保尽可能多的任务能在截止时间前完成。而对于科学应用以及模型训练/推理而言，首要目标则是最小化任务执行总时间并提升执行性能。任务执行总时间是指从第一个任务开始执行到所有任务完成所消耗的总时间。在这种场景下，任务图调度面临的一个关键挑战就是，要在考虑LLC竞争对性能的影响，并在任务图的依赖关系约束下充分利用计算资源的前提下，进一步缩短任务执行总时间。遗憾的是，现有的调度方法并未很好地解决这一问题。因此，我们针对基于对称多处理（SMP）架构的多核处理器上的缓存竞争问题，提出了用于任务图的平衡负载调度方法（BLSA）。BLSA通过以一种能够平衡各任务缓存需求的方式来调度任务，从而有效降低LLC缓存未命中率并缩短整体执行时间。本文的主要贡献如下：
• 我们提出了一种生成平衡负载标准的算法。该算法通过分析所有任务的LLC缓存未命中率，来计算出理想的局部性负载标准。这一平衡负载标准将模糊的减少缓存竞争的目标转化为可量化的标准。
• 我们设计了基于任务图的动态调度算法。该算法遵循任务图的依赖关系，并根据我们的优先级计算机制来调度任务，该机制紧密结合了用于减少缓存竞争的局部性负载差异以及用于缩短任务执行总时间的执行时间差异，而这些都是基于平衡负载标准得出的。
• 在具有不同拓扑结构及多种类型任务的场景中，与传统的FCFS调度算法以及三种先进的任务图调度算法相比，BLSA在任务执行总时间和LLC缓存未命中率方面都具有优势。

本文的其余部分结构如下：第2节介绍任务图模型、存在的问题以及相关研究工作；第3节详细阐述BLSA的具体实现过程以及所采用的策略；第4节展示对比实验结果；最后，第5节对本文进行总结。

任务图模型
每个任务都可以表示为DAG中的一个节点。一般来说，大小为N的任务集合可表示为T={t1,t2,…,tN}，对应的具有N个节点和M条有向边的任务图可表示为G(V,E)，其中V={v1,v2,…,vN}是节点集合，E={e1,e2,…,eM}是有向边集合。在任务图G中，每个节点vi代表一个可执行的任务，而每条有向边ek=(vi,vj)则表示从节点vi到节点vj的有向连接，意味着任务节点vj依赖于任务节点vi。

BLSA的流程
如图1所示，BLSA的流程包含四个主要模块，这些模块实现了该方法的功能。GProcess模块用于分析任务图的相关信息（如节点数量、拓扑结构、任务节点的执行时间以及局部性等），并执行相应的更新操作。CPUStat模块实时监控CPU，以获取必要的信息（如核心数量、核心编号、核心使用率等）。ReadyQueue模块用于构建待调度任务池，便于添加新的任务。

实验环境
小型和中型实验是在频率为3.60 GHz的Intel i7 - 7700处理器上进行的。该处理器拥有4个核心，采用三级缓存架构，每个核心拥有64 KB的私有L1缓存和256 KB的私有L2数据缓存，4个核心共享一个8MB的L3数据缓存。大型实验则是在同样采用三级缓存架构的Intel i7 - 13700K处理器上进行的。实验中我们使用了8个性能相同的效率核心，每个核心拥有64 KB的缓存。

结论
在本文中，我们研究了在考虑共享缓存竞争的情况下，在SMP系统上调度任务图这一重要问题。我们提出了BLSA方法，用以减轻共享缓存竞争对性能下降的影响。在该方法中，我们利用各个任务的LLC缓存未命中率来量化任务的局部性。我们设计了一种算法来确定用于衡量局部性的平衡负载标准。基于该算法，我们综合考虑各个任务的LLC缓存未命中率和执行时间来计算任务优先级。

作者贡献声明
刘家正：撰写——初稿、验证、方法论部分。刘松：撰写——审阅与编辑。李飞：撰写——审阅与编辑。聂世强：撰写——审阅与编辑。王金宇：撰写——审阅与编辑。吴伟国：撰写——审阅与编辑。

利益冲突声明
作者声明不存在任何可能影响本文研究工作的已知财务利益或个人关系。刘家正于2024年在中国西安交通大学获得计算机科学与技术学士学位，目前他正在该校计算机科学与技术学院攻读计算机科学硕士学位。他的研究兴趣包括高性能计算和并行算法。