这篇文档属于类型a，即报告了一项原创性研究。以下是针对该研究的学术报告：
标题：实时系统中缓存使用最小化的优化方法研究
作者与机构
本研究由来自德国慕尼黑工业大学的Binqi Sun和Marco Caccamo、法国图卢兹LAAS-CNRS的Tomasz Kloda，以及巴西圣卡塔琳娜联邦大学的Sergio Arribas Garcia和Giovani Gracioli合作完成。论文于2023年7月在德国多特蒙德举行的第31届国际实时网络与系统会议（31st International Conference on Real-Time Networks and Systems, RTNS 2023）上发表，后收录于HAL开放档案库（hal-04803571）。
学术背景
研究领域与背景知识
本研究属于实时系统（real-time systems）领域，核心关注点是通过优化缓存分区（cache partitioning）技术减少多任务共享缓存时的相互干扰，同时最小化缓存使用量。缓存分区通过为任务分配独立的缓存段（cache segments），避免高优先级任务抢占低优先级任务时导致的缓存数据被驱逐（cache-related preemption delays, CRPD）。现有研究多以保证任务可调度性（schedulability）为目标，但忽略了在功耗敏感或混合关键性（mixed-criticality）系统中缓存资源的限制需求。
研究动机与目标
传统缓存分配方法假设所有缓存段均可被任务占用，但实际场景中，缓存资源可能受限（如多核系统中需为通用操作系统保留部分缓存）。本研究提出两大核心目标：
1. 最小化缓存使用：在保证任务可调度性的前提下，减少分配给实时任务的缓存总量；
2. 适应不同调度策略：分别针对抢占式（preemptive）与非抢占式（non-preemptive）单处理器系统设计优化算法。
研究流程与方法
研究流程分为三部分：抢占式调度优化、非抢占式调度优化、实验验证。
1. 抢占式调度优化
问题建模：将缓存分配问题转化为整数二次约束规划（Integer Quadratically Constrained Program, IQCP），目标函数为最小化总缓存使用量（公式4），约束条件包括任务执行时间与缓存分配的关系（公式2-3）、响应时间分析（Response Time Analysis, RTA）（公式5-7）。
算法设计：
- 启发式算法（GLS）：基于局部搜索（local search）的引导式优化（Algorithm 1）。初始化为全部分配最大缓存，迭代阶段通过“减少阶段”（选择利用率增量最小的任务减少缓存）和“增加阶段”（选择利用率减量最大的任务增加缓存）调整分配，结合禁忌表（tabu mechanism）避免重复搜索。
- 分支定界（B&B）：通过剪枝策略（pruning）减少搜索空间，利用响应时间分析的可持续性（sustainability）跳过冗余测试（Algorithm 2）。
- 动态规划（DP）：改进Sasinowski的算法，通过提前终止条件快速找到可行解（Algorithm 3）。
2. 非抢占式调度优化
问题特性：任务共享单一缓存分区，无需考虑缓存抢占延迟。
搜索策略：
- 线性搜索：按升序测试缓存大小，利用可持续性跳过无效测试（Algorithm 4）。
- 二分搜索：对每个任务优先级降序测试，复杂度为O(n log m)（Algorithm 5）。
可调度性测试：包括精确的NP-RTA（伪多项式时间）、简化版NP-Single（单区间测试）和NP-Hyper（双曲利用率边界）。
3. 实验验证
实验设置：
- 基准测试：基于CortexSuite视觉处理程序的20个基准，模拟两级LRU缓存（L1: 32KB，L2: 可变大小），测量不同缓存分配下的执行时间。
- 任务集生成：随机生成5,400组任务集，参数包括任务数n ∈ {16, 32, 64}、缓存总大小S ∈ {1024, 2048, 4096} KB，段大小dS ∈ {32, 128, 512} KB，基础利用率U ∈ [0.7, 1.6]。
对比方法：IQCP（Gurobi求解）、GLS、B&B、DP及非抢占式方法。
主要结果
1. 抢占式优化性能
- GLS表现最优：平均最优性差距仅0.79%，运行时间仅为IQCP的10%，且相比传统缓存分配方法平均减少39.15%缓存使用。
- 任务规模影响：n=64时，非抢占式方法在高利用率（U>1.3）下比抢占式节省更多缓存（图4c）。
2. 非抢占式优化对比
- NP-RTA效果最佳：比NP-Single和NP-Hyper分别节省24.9%和41.4%缓存（图7a），但运行时间较长（图7c）。
3. 缓存段粒度影响
- 段大小（dS）增加：所有算法缓存使用量上升，B&B在粗粒度（dS=512KB）下表现接近GLS（图5c）。
结论与价值
科学价值：
- 首次将缓存最小化作为优化目标，提出IQCP模型和高效启发式算法GLS。
- 揭示了非抢占式调度在高利用率场景下的缓存优势，为混合关键性系统设计提供新思路。
应用价值：
- 适用于多核嵌入式系统（如车载或航空电子设备），通过减少实时任务缓存占用，预留资源给非实时任务或降低功耗。
亮点与创新
1. 多算法覆盖：结合数学规划、启发式搜索和动态规划，兼顾最优性与效率。
2. 实际导向实验：基于真实基准程序生成任务集，验证算法的工程适用性。
3. 非抢占式优化：首次系统分析其缓存节省潜力，补充了现有研究空白。
其他发现
- 缓存段分配策略：任务执行的“拐点”（corner points）机制（例5.1）可加速搜索，跳过无效分配（图2）。
- 硬件扩展讨论：支持Intel CAT（Cache Allocation Technology）和ARM缓存锁定（lockdown）等硬件特性（第2节）。
总结
本研究为实时系统缓存管理提供了理论严谨且实用的解决方案，其方法论和开源实现（HAL存档）可为后续研究奠定基础。未来可扩展至多核环境或结合抢占式/非抢占式混合调度进一步优化。