Elastic Scheduling for Harmonic Task Systems

Marion Sudvarg, Ao Li, Daisy Wang, Sanjoy Baruah, Jeremy Buhler, Chris Gill, Ning Zhang, Pontus Ekberg

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings - 2024 IEEE 30th Real-Time and Embedded Technology and Applications Symposium, RTAS 2024
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages334-347
Number of pages14
ISBN (Electronic)9798350358414
DOIs
StatePublished - 2024
Event30th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2024 - Hong Kong, China
Duration: May 13 2024May 16 2024

Publication series

NameProceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS
ISSN (Print)1545-3421

Conference

Conference30th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2024
Country/TerritoryChina
CityHong Kong
Period05/13/2405/16/24

Keywords

  • elastic scheduling
  • harmonic periods
  • harmonic tasks
  • period assignment
  • period ranges
  • real-Time systems

Fingerprint

Dive into the research topics of 'Elastic Scheduling for Harmonic Task Systems'. Together they form a unique fingerprint.

Cite this