Intra-Task Priority Assignment in Real-Time Scheduling of DAG Tasks on Multi-Cores

Qingqiang He, Xu Jiang, Nan Guan, Zhishan Guo

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

Real-time scheduling and analysis of parallel tasks modeled as directed acyclic graphs (DAG) have been intensively studied in recent years. However, no existing work has explored the execution order of eligible vertices within a DAG task. In this paper, we show that this intra-task vertex execution order has a large impact on system schedulability and propose to control the execution order by vertex-level priority assignment. We develop analysis techniques to bound the worst-case response time for the proposed scheduling strategy and design heuristics for proper priority assignment to improve system schedulability as much as possible. We further extend the proposed approach to the general setting of multiple recurrent DAG tasks. Experiments with both realistic parallel benchmark applications and randomly generated workload show that our method consistently outperforms state-of-the-art methods with different task graph structures and parameter configurations.

Original languageEnglish
Article number8686234
Pages (from-to)2283-2295
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Volume30
Issue number10
DOIs
Publication statusPublished - 1 Oct 2019

Keywords

  • Intra-task priority assignment
  • multi-cores
  • parallel real-time tasks
  • response time analysis

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this