Subtask-Level Elastic Scheduling

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).

Department(s)

Computer Science

Comments

Washington State University, Grant CPS-2229290

Keywords and Phrases

atmospheric aerosol monitoring; elastic scheduling; federated scheduling; mixed-integer quadratic programming; parallel dag tasks; real-time systems

International Standard Serial Number (ISSN)

1052-8725

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2026 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Jan 2024

Link to Full Text

Share

 
COinS