@inproceedings{0f0e49445944412bb73c05083c21e1dc,
title = "Elastic Scheduling for Harmonic Task Systems",
abstract = "Elastic scheduling is a framework to reduce task utilizations (often by increasing periods) in response to system overload. This paper extends elastic scheduling to uniprocessor scheduling of implicit-deadline task sets for which periods must remain harmonic. We argue that for tasks with periods constrained to continuous intervals, the problem of selecting harmonic periods from those intervals is unlikely to have a polynomial time solution. However, we outline an approach that is pseudo-polynomial in the range of acceptable periods. We then show that the problem of elastic scheduling is NP-hard with harmonic constraints. Nonetheless, if a total order is imposed on task periods (a natural restriction in many applications with execution pipelines that synchronize input data sources), the problem can be reduced offline to a lookup table, enabling polynomial-Time online adaptation if available CPU bandwidth changes. We implement the proposed algorithm in two real-world applications: The Fast Integrated Mobility Spectrometer (FIMS) and ORB-SLAM3. We demonstrate that elastic scheduling allows FIMS to adjust its execution to avoid missing deadlines on a SWaP-constrained computational platform, and that it improves ORB-SLAM3's localization results by as much as lO.4x when available CPU bandwidth changes dynamically during runtime.",
keywords = "elastic scheduling, harmonic periods, harmonic tasks, period assignment, period ranges, real-Time systems",
author = "Marion Sudvarg and Ao Li and Daisy Wang and Sanjoy Baruah and Jeremy Buhler and Chris Gill and Ning Zhang and Pontus Ekberg",
note = "Publisher Copyright: {\textcopyright} 2024 IEEE.; 30th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2024 ; Conference date: 13-05-2024 Through 16-05-2024",
year = "2024",
doi = "10.1109/RTAS61025.2024.00034",
language = "English",
series = "Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "334--347",
booktitle = "Proceedings - 2024 IEEE 30th Real-Time and Embedded Technology and Applications Symposium, RTAS 2024",
}