@inproceedings{36824ecd5b1744b189278a466f9b2f1b,
title = "Calculating response-time bounds for openmp task systems with conditional branches",
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.",
keywords = "Conditional DAG, OpenMP, Response time",
author = "Jinghao Sun and Nan Guan and Jingchang Sun and Yaoyao Chi",
year = "2019",
month = apr,
doi = "10.1109/RTAS.2019.00022",
language = "English",
series = "Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "169--181",
editor = "Brandenburg, {Bjorn B.}",
booktitle = "Proceedings - 25th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2019",
note = "25th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2019 ; Conference date: 16-04-2019 Through 18-04-2019",
}