Decomposition-based Real-Time Scheduling of Parallel Tasks on Multi-cores Platforms

Xu Jiang, Nan Guan, Xiang Long, Han Wan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

Multi-core processors have become mainstream computation platforms, not only for general and high-performance computers, but also for real-time embedded systems. To fully utilize the computation power of multi-cores, software must be parallelized. Recently, there has been a rapidly increasing interest in real-time scheduling of parallel real-time tasks, but the field is still much less mature than traditional real-time scheduling of sequential tasks. In this paper, we study the real-time scheduling and techniques for parallel real-time tasks based on decomposition, where a task graph is transferred to a set of independent sporadic tasks. In particular, we propose new decomposition strategies that better explore the structure feature of each task to improve schedulability. We develop schedulability tests for the global EDF (Earliest Deadline First) scheduling algorithm based on decomposition and three types of its variants, with their own pros and cons in different aspects. We conduct experiments to evaluate the real-time performance of our proposed scheduling algorithms against the state-of-the-art scheduling and analysis methods of different types.

Original languageEnglish
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
DOIs
Publication statusAccepted/In press - 1 Jan 2019

Keywords

  • DAG
  • Decomposition.
  • Global EDF
  • Multi-core
  • Parallel Tasks
  • Real-Time Scheduling

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Cite this