Algorithms for Computing the WCRT Bound of OpenMP Task Systems with Conditional Branches

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

View graph of relations

Author(s)

  • Jinghao Sun
  • Jingchang Sun
  • Xi Zhang
  • Yaoyao Chi
  • Feng Li

Detail(s)

Original languageEnglish
Article number9054989
Pages (from-to)57-71
Journal / PublicationIEEE Transactions on Computers
Volume70
Issue number1
Online published2 Apr 2020
Publication statusPublished - Jan 2021
Externally publishedYes

Abstract

Multi-cores are becoming mainstream hardware platforms for embedded and real-time systems. To fully utilize the processing capacity of multi-cores, software should be parallelized. Recently, much work has been done on real-time scheduling of parallel tasks modeled as directed acyclic graphs (DAG), motivated by the parallel task structures supported by popular parallel programming frameworks such as OpenMP. The DAG-based task models in existing real-time scheduling research assume well-nested graph 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 those assumptions. In this article, we model the behavior of general OpenMP task systems with non-well-nested structures. The worst-case response time analysis problem for such systems is more difficult due to the flexible graph structure. As the major technical contribution, we develop two efficient algorithms to compute the worst-case response time bounds, with different trade-offs between efficiency and precision. Evaluation with both randomly generated task graphs and realistic OpenMP programs shows good performance of our approaches in terms of both precision and efficiency.

Research Area(s)

  • conditional directed acyclic graph, OpenMP, response time analysis

Citation Format(s)

Algorithms for Computing the WCRT Bound of OpenMP Task Systems with Conditional Branches. / Sun, Jinghao; Guan, Nan; Sun, Jingchang; Zhang, Xi; Chi, Yaoyao; Li, Feng.

In: IEEE Transactions on Computers, Vol. 70, No. 1, 9054989, 01.2021, p. 57-71.

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