Federated scheduling for stochastic parallel real-time tasks

Jing Li, Kunal Agrawal, Christopher Gill, Chenyang Lu

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

6 Scopus citations

Abstract

Federated scheduling is a strategy to schedule parallel real-time tasks: It allocates a dedicated cluster of cores to each high-utilization task (utilization ≥ 1); It uses a multiprocessor scheduling algorithm to schedule and execute all low-utilization tasks sequentially, on a shared cluster of the remaining cores. Prior work has shown that federated scheduling has the best known capacity augmentation bound of 2 for parallel tasks with implicit deadlines. In this paper, we explore the soft real-time performance of federated scheduling and address average-case workloads instead of worst-case ones. In particular, we consider stochastic tasks-tasks for which execution time and critical-path length are random variables. In this case, we use bounded expected tardiness as the schedulability criterion. We define a stochastic capacity augmentation bound and prove that federated scheduling algorithms guarantee the same bound of 2 for stochastic tasks. We present three federated mapping algorithms with different complexities for core allocation. All of them guarantee bounded expected tardiness and provide the same capacity augmentation bound. In practice, however, we expect them to provide different performance, both in terms of the task sets they can schedule and the actual tardiness they guarantee. Therefore, we present numerical evaluations using randomly generated task sets to examine the practical differences between the three algorithms.

Original languageEnglish (US)
Title of host publicationRTCSA 2014 - 20th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781479939534
DOIs
StatePublished - Sep 25 2014
Externally publishedYes
Event20th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2014 - Chongqing, China
Duration: Aug 20 2014Aug 22 2014

Publication series

NameRTCSA 2014 - 20th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications

Other

Other20th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2014
CountryChina
CityChongqing
Period8/20/148/22/14

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Hardware and Architecture
  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Keywords

  • federated scheduling
  • parallel scheduling
  • soft real-time scheduling
  • stochastic capacity augmentation bound

Fingerprint Dive into the research topics of 'Federated scheduling for stochastic parallel real-time tasks'. Together they form a unique fingerprint.

Cite this