Calculating response-time bounds for openmp task systems with conditional branches

Jinghao Sun, Nan Guan, Jingchang Sun, Yaoyao Chi

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

5 Citations (Scopus)

Abstract

Existing DAG-based task models in real-time scheduling research assume well-nested structures recursively composed by single-source-single-sink parallel and conditional components. However, realistic OpenMP task systems in general have more flexible structures that do not comply with this assumption. In this paper, we model the behaviors of general OpenMP task systems with non-well-nested branching structures and study the problem of how to bound their worst-case response times (WCRT). A naive solution is to apply the established WCRT bound for DAG tasks without conditional branches to the exponentially many possible execution flows, which has exponential time complexity. In this paper, we develop a linear-time algorithm to efficiently calculate WCRT bounds for OpenMP task systems with non-well-nested branching structures. Experiments with both synthetic task graphs and realistic OpenMP programs are conducted to evaluate the performance of our method.

Original languageEnglish
Title of host publicationProceedings - 25th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2019
EditorsBjorn B. Brandenburg
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages169-181
Number of pages13
ISBN (Electronic)9781728106786
DOIs
Publication statusPublished - Apr 2019
Event25th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2019 - Montreal, Canada
Duration: 16 Apr 201918 Apr 2019

Publication series

NameProceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS
Volume2019-April
ISSN (Print)1545-3421

Conference

Conference25th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2019
CountryCanada
CityMontreal
Period16/04/1918/04/19

Keywords

  • Conditional DAG
  • OpenMP
  • Response time

ASJC Scopus subject areas

  • Engineering(all)

Cite this