Outstanding paper award: Analysis of global EDF for parallel tasks

Jing Li, Kunal Agrawal, Chenyang Lu, Christopher Gill

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

51 Scopus citations

Abstract

As multicore processors become ever more prevalent, it is important for real-time programs to take advantage of intra-task parallelism in order to support computation-intensive applications with tight deadlines. We prove that a Global Earliest Deadline First (GEDF) scheduling policy provides a capacity augmentation bound of 4-2/m and a resource augmentation bound of 2-1/m for parallel tasks in the general directed a cyclic graph model. For the proposed capacity augmentation bound of 4-2/m for implicit deadline tasks under GEDF, we prove that if a task set has a total utilization of at most m/(4-2/m) and each task's critical path length is no more than 1/(4-2/m) of its deadline, it can be scheduled on a machine with m processors under GEDF. Our capacity augmentation bound therefore can be used as a straightforward schedulability test. For the standard resource augmentation bound of 2-1/m for arbitrary deadline tasks under GEDF, we prove that if an ideal optimal scheduler can schedule a task set on m unit-speed processors, then GEDF can schedule the same task set on m processors of speed 2-1/m. However, this bound does not lead to a schedulabilty test since the ideal optimal scheduler is only hypothetical and is not known. Simulations confirm that the GEDF is not only safe under the capacity augmentation bound for various randomly generated task sets, but also performs surprisingly well and usually outperforms an existing scheduling technique that involves task decomposition.

Original languageEnglish (US)
Title of host publicationProceedings - 25th Euromicro Conference on Real-Time Systems, ECRTS 2013
Pages3-13
Number of pages11
DOIs
StatePublished - Oct 15 2013
Externally publishedYes
Event25th Euromicro Conference on Real-Time Systems, ECRTS 2013 - Paris, France
Duration: Jul 9 2013Jul 12 2013

Publication series

NameProceedings - Euromicro Conference on Real-Time Systems
ISSN (Print)1068-3070

Other

Other25th Euromicro Conference on Real-Time Systems, ECRTS 2013
CountryFrance
CityParis
Period7/9/137/12/13

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture

Keywords

  • capacity augmentation bound
  • global EDF
  • parallel scheduling
  • real-time scheduling
  • resource augmentation bound

Fingerprint Dive into the research topics of 'Outstanding paper award: Analysis of global EDF for parallel tasks'. Together they form a unique fingerprint.

Cite this