通过线程的共址并行调度实现接近最优的缓存共享

《ACM Transactions on Embedded Computing Systems》：Near-Optimal Cache Sharing through Co-Located Parallel Scheduling of Threads

硬实时系统中缓存共享的共定位调度方法研究。针对缓存引入执行时序不确定性导致的调度复杂性，提出3-parm-hd近似算法解决NP难问题，通过任务共定位共享缓存提升28%调度任务量同时减少30%核心资源消耗，较传统2倍近似算法提升45%任务量和41%核心节省率，并在RISC-V平台实验验证了其对2倍近似算法无法调度的任务的有效性。

　　

摘要

对于硬实时系统而言，缓存内存会增加执行时间的不确定性，从而增加时序分析的复杂性。因此，缓存内存通常被视为影响调度性能的负面因素。基于缓存意识的共位调度（cache-aware co-located scheduling）旨在通过精心安排线程来共享缓存数据，从而提高调度性能。线程间的缓存共享能够降低任务执行时间，并在资源有限的情况下提升调度效率。然而，这种调度方式也可能降低并行性，进而影响系统效率。因此，如何确定一组最优的线程进行共位调度，以在满足时序约束的同时最小化资源消耗，是一个复杂的挑战。本研究表明，这种优化问题属于强NP难（NP-Hard）问题。本文提出了一种名为3-parm-hd的近似算法，用于Fork-Join类型任务的共位调度。该算法具有3倍性能保证（3-factor guarantee），并且资源扩展界限为3。仿真测试表明，与不可行的最优调度算法相比，3-parm-hd能够在使用30%更少核心的情况下调度多28%的任务。此外，实验结果表明，在QEMU平台上进行的RISC-V架构测试中，3-parm-hd在调度任务方面表现更优：与传统基于2倍性能保证的近似算法相比，3-parm-hd能够在使用41%更少核心的情况下调度多45%的任务。这些实验结果进一步证实了3-parm-hd的优越性。