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

Jinghao Sun, Nan Guan, Jingchang Sun, Xi Zhang, Yaoyao Chi, Feng Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

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.

Original languageEnglish
Article number9054989
Pages (from-to)57-71
Number of pages15
JournalIEEE Transactions on Computers
Volume70
Issue number1
DOIs
Publication statusPublished - 1 Jan 2021

Keywords

  • conditional directed acyclic graph
  • OpenMP
  • response time analysis

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this