Work-in-Progress: Response Time Bounds for Typed DAG Parallel Tasks on Heterogeneous Multi-cores

Meiling Han, Nan Guan, Jinghao Sun, Qingqiang He, Qingxu Deng, Weichen Liu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


Heterogenerous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of typed scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the non-self-sustainability problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its non-self-sustainability problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are significantly more precise than the existing bound while having good scalability.

Original languageEnglish
Title of host publicationProceedings - 39th IEEE Real-Time Systems Symposium, RTSS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages2
ISBN (Electronic)9781538679074
Publication statusPublished - 4 Jan 2019
Event39th IEEE Real-Time Systems Symposium, RTSS 2018 - Nashville, United States
Duration: 11 Dec 201814 Dec 2018

Publication series

NameProceedings - Real-Time Systems Symposium
ISSN (Print)1052-8725


Conference39th IEEE Real-Time Systems Symposium, RTSS 2018
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Work-in-Progress: Response Time Bounds for Typed DAG Parallel Tasks on Heterogeneous Multi-cores'. Together they form a unique fingerprint.

Cite this