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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

9 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Article number8686234
Pages (from-to)2283-2295
Journal / PublicationIEEE Transactions on Parallel and Distributed Systems
Volume30
Issue number10
Online published11 Apr 2019
Publication statusPublished - Oct 2019
Externally publishedYes

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.

Research Area(s)

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