On computing exact WCRT for DAG Tasks

Jinghao Sun, Feng Li, Nan Guan, Wentao Zhu, Minjie Xiang, Zhishan Guo, Wang Yi

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

Abstract

Most current real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Existing worst-case response time (WCRT) bounds (e.g., Graham's bound) derived for DAGs may be very pessimistic. No one precisely knows the gap between the WCRT bound and the actual WCRT. In this paper, we aim to derive the exact WCRT of a DAG task under the list scheduling upon multi-core platforms. We encode the WCRT analysis problem into a satisfaction modular theoretical (SMT) formulation based on insights into the list scheduling algorithm, and prove that our SMT program can solve the WCRT precisely, providing an accurate baseline to measure the tightness of the existing WCRT bounds. Experiments show that our method significantly improves the tightness of the WCRT bound, and is practically quite efficient, e.g., it can analyze DAGs with more than 40 vertices in a few seconds.

Original languageEnglish
Title of host publication2020 57th ACM/IEEE Design Automation Conference, DAC 2020
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-6
ISBN (Electronic)9781450367257
DOIs
Publication statusPublished - Jul 2020
Event57th ACM/IEEE Design Automation Conference, DAC 2020 - Virtual, San Francisco, United States
Duration: 20 Jul 202024 Jul 2020

Publication series

NameProceedings - Design Automation Conference
Volume2020-July
ISSN (Print)0738-100X

Conference

Conference57th ACM/IEEE Design Automation Conference, DAC 2020
Country/TerritoryUnited States
CityVirtual, San Francisco
Period20/07/2024/07/20

ASJC Scopus subject areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modelling and Simulation

Cite this