Lune

RTSS2023Top-tier venue

Co-Located Parallel Scheduling of Threads to Optimize Cache Sharing

Corey Tessler, Venkata Prashant Modekurthy, Nathan Fisher, Abusayeed Saifullah, Alleyn Murphy

Abstract

For hard-real time systems, cache memory increases execution time variability, increasing the complexity of timing analysis. As such, cache memory is often treated exclusively as a detractor to schedulability. Cache-aware co-located scheduling aims to improve schedulability by carefully scheduling threads to share cached values. Cache sharing between threads potentially reduces task execution times and increases schedulability with fewer resources. Antithetically, co-located scheduling may reduce parallelism, decreasing efficiency. Thus, identifying the optimal set of threads to co-locate that minimizes the resources required while ensuring timing constraints is a complex challenge. This work establishes optimal co-location as NP-Hard in the strong sense. It offers an approximation method for the co-located scheduling of Fork-Join tasks named 3-PARM-HD. The approximation has a 3-factor guarantee and a resource augmentation bound of 3. The simulated evaluation shows 3-PARM-HD increases schedulability compared to an optimal intractable algorithm (without co-location) scheduling 28% more tasks with 30% fewer cores. Simulated results show 3-PARM-HD outperforms a 2-factor approximation for traditional makespan, scheduling 39% more tasks with 44% fewer cores. An experimental RISC-V evaluation running on a QEMU platform confirms the benefits of 3-PARM-HD, scheduling and executing tasks deemed unschedulable by a 2-factor makespan approximation without co-location.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on7

  1. DAG Scheduling and Analysis on Multiprocessor Systems: Exploitation of Parallelism and DependencyShuai Zhao, Xiaotian Dai, Iain Bate, Alan Burns et al.RTSS 2020 · 73 citations
  2. Virtually-Federated Scheduling of Parallel Real-Time TasksXu Jiang, Nan Guan, Haochun Liang, Yue Tang et al.RTSS 2021 · 22 citations
  3. Response-Time Analysis and Optimization for Probabilistic Conditional Parallel DAG TasksNiklas Ueter, Mario Günzel, Jian-Jia ChenRTSS 2021 · 13 citations
  4. Conditionally Optimal Parallelization of Real-Time DAG Tasks for Global EDFYoungeun Cho, Dongmin Shin, JaeSeung Park, Chang-Gun LeeRTSS 2021 · 12 citations
  5. A Multi-Level DPM Approach for Real-Time DAG Tasks in Heterogeneous ProcessorsFederico Reghenzani, Ashikahmed Bhuiyan, William Fornaciari, Zhishan GuoRTSS 2021 · 12 citations

Related papers

  1. Co-Optimizing Cache Partitioning and Multi-Core Task Scheduling: Exploit Cache Sensitivity or Not?Binqi Sun, Debayan Roy, Tomasz Kloda, Andrea Bastoni et al.RTSS 2023 · 4 citations
  2. Precise and scalable shared cache contention analysis for WCET estimationWei Zhang, Mingsong Lv, Wanli Chang, Lei JuDAC 2022 · 12 citations
  3. A Cache/Algorithm Co-design for Parallel Real-Time Systems with Data Dependency on Multi/Many-core System-on-ChipsZhe Jiang, Shuai Zhao, Ran Wei, Yiyang Gao et al.DAC 2024 · 3 citations
  4. Per-Bank Bandwidth Regulation of Shared Last-Level Cache for Real-Time SystemsConnor Sullivan, Alex Manley, Mohammad Alian, Heechul YunRTSS 2024 · 4 citations
  5. Tight Cache Contention Analysis for WCET Estimation on Multicore SystemsShuai Zhao, Jieyu Jiang, Shenlin Cai, Yaowei Liang et al.RTSS 2025 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines