Using imprecise computing for improved non-preemptive real-time scheduling

Lin Huang, Youmeng Li, Sachin S. Sapatnekar, Jiang Hu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


Conventional hard real-time scheduling is often overly pessimistic due to the worst case execution time estimation. The pessimism can be mitigated by exploiting imprecise computing in applications where occasional small errors are acceptable. This leverage was previously investigated for preemptive scheduling. We study how to make use of imprecise computing in uniprocessor non-preemptive real-time scheduling, which is known to be more difficult than its preemptive counterpart. Several heuristic algorithms are developed for periodic tasks with independent or cumulative errors due to imprecision. Simulation results show that the proposed techniques can significantly improve task schedulability and achieve desired accuracy-schedulability tradeoff. The benefit is further confirmed by a prototyping implementation in Linux system.

Original languageEnglish (US)
Title of host publicationProceedings of the 55th Annual Design Automation Conference, DAC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Print)9781450357005
StatePublished - Jun 24 2018
Event55th Annual Design Automation Conference, DAC 2018 - San Francisco, United States
Duration: Jun 24 2018Jun 29 2018

Publication series

NameProceedings - Design Automation Conference
VolumePart F137710
ISSN (Print)0738-100X


Other55th Annual Design Automation Conference, DAC 2018
Country/TerritoryUnited States
CitySan Francisco

Bibliographical note

Funding Information:
This work was supported in part by the NSF under awards CCF-1525925 and CCF-1525749.

Publisher Copyright:
© 2018 Association for Computing Machinery.


Dive into the research topics of 'Using imprecise computing for improved non-preemptive real-time scheduling'. Together they form a unique fingerprint.

Cite this