Lune

RTSS2024Top-tier venue

Subtask-Level Elastic Scheduling

Marion Sudvarg, Daisy Wang, Jeremy Buhler, Chris Gill

Abstract

Buttazzo et al.’s elastic scheduling model allows task utilizations to be “compressed” to ensure schedulability atop limited resources. Each task is assigned a range of acceptable utilizations and an “elastic constant” representing the relative adaptability of its utilization. In this paper, we consider federated scheduling, under which each high-utilization parallel task is assigned dedicated processor cores. We propose a new model of elastic workload compression for parallel DAG tasks that assigns each subtask its own elastic constant and continuous range of acceptable workloads. We show that the problem can be solved offline as a mixed-integer quadratic program, or online using a pseudo-polynomial dynamic programming algorithm. We also consider joint core allocation and compression of low-utilization sequential tasks and present a mixed-integer linear program for optimal elastic compression of tasks under partitioned EDF scheduling. We show empirical improvements in schedulability over the prior work and present a case study for the Fast Integrated Mobility Spectrometer (FIMS).

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 on2

  1. Generating Utilization Vectors for the Systematic Evaluation of Schedulability TestsDavid Griffin, Iain Bate, Robert I. DavisRTSS 2020 · 71 citations
  2. PolyRhythm: Adaptive Tuning of a Multi-Channel Attack Template for Timing InterferenceAo Li, Marion Sudvarg, Han Liu, Zhiyuan Yu et al.RTSS 2022 · 12 citations

Related papers

  1. Virtually-Federated Scheduling of Parallel Real-Time TasksXu Jiang, Nan Guan, Haochun Liang, Yue Tang et al.RTSS 2021 · 22 citations
  2. Mixed-Criticality Federated Scheduling for Relaxed-Deadline DAG TasksFei Guan, Jinkyu Lee, Chun Jason Xue, Jen-Ming Wu et al.RTSS 2024 · 6 citations
  3. DPCP-p: A Distributed Locking Protocol for Parallel Real-Time TasksMaolin Yang, Ze-Wei Chen, Xu Jiang, Nan Guan et al.DAC 2020 · 11 citations
  4. FLEX: Adaptive Task Batch Scheduling with Elastic Fusion in Multi-Modal Multi-View Machine PerceptionYuhang Xu, Zixuan Liu, Xinzhe Fu, Shengzhong Liu et al.RTSS 2024 · 5 citations
  5. Bounding the Response Time of DAG Tasks Using Long PathsQingqiang He, Nan Guan, Mingsong Lv, Xu Jiang et al.RTSS 2022 · 19 citations
Dusk over the sea between two cliffs drawn in fine vertical lines