TY - JOUR
T1 - Real-Time Scheduling and Analysis of OpenMP DAG Tasks Supporting Nested Parallelism
AU - Sun, Jinghao
AU - Guan, Nan
AU - Li, Feng
AU - Gao, Huimin
AU - Shi, Chang
AU - Yi, Wang
N1 - Funding Information:
This work was supported in part by the National Foundation of Science of China under Grants 61972076, 61672140, 61772123, 61532007, and 61602104, and in part by the Research Grants Council of Hong Kong (GRF 15204917 and 15213818).
Publisher Copyright:
© 1968-2012 IEEE.
PY - 2020/9/1
Y1 - 2020/9/1
N2 - OpenMP is a promising framework to develop parallel real-time software on multi-cores. Although similar to the DAG task model, OpenMP task systems are significantly more difficult to analyze due to constraints posed by OpenMP specifications. One of the most interesting features in OpenMP is the support for nested parallelism, enjoying benefits in enhancing performance transparency of parallel libraries and promoting reuse of black-box code. Previous researches on DAG task scheduling mainly restrict to only one level of parallelism. The problem whether OpenMP tasks with multiple levels of parallelism are suitable to real-time systems remains open. In this paper, we study the real-time scheduling and analysis of OpenMP task systems supporting nested parallelism. First, we show that under existing scheduling algorithms in OpenMP implementations, nested parallelism indeed may lead to extremely bad timing behaviors where the parallel workload is sequentially executed completely. To solve this problem, we propose a new scheduling algorithm and develop two sound response time bounds by considering the trade-off between simplicity and analysis precision. Experiments demonstrate the efficiency of our methods.
AB - OpenMP is a promising framework to develop parallel real-time software on multi-cores. Although similar to the DAG task model, OpenMP task systems are significantly more difficult to analyze due to constraints posed by OpenMP specifications. One of the most interesting features in OpenMP is the support for nested parallelism, enjoying benefits in enhancing performance transparency of parallel libraries and promoting reuse of black-box code. Previous researches on DAG task scheduling mainly restrict to only one level of parallelism. The problem whether OpenMP tasks with multiple levels of parallelism are suitable to real-time systems remains open. In this paper, we study the real-time scheduling and analysis of OpenMP task systems supporting nested parallelism. First, we show that under existing scheduling algorithms in OpenMP implementations, nested parallelism indeed may lead to extremely bad timing behaviors where the parallel workload is sequentially executed completely. To solve this problem, we propose a new scheduling algorithm and develop two sound response time bounds by considering the trade-off between simplicity and analysis precision. Experiments demonstrate the efficiency of our methods.
KW - directed acyclic graph (DAG)
KW - nested parallel
KW - OpenMP
KW - response time analysis
UR - http://www.scopus.com/inward/record.url?scp=85089545029&partnerID=8YFLogxK
U2 - 10.1109/TC.2020.2972385
DO - 10.1109/TC.2020.2972385
M3 - Journal article
AN - SCOPUS:85089545029
SN - 0018-9340
VL - 69
SP - 1335
EP - 1348
JO - IEEE Transactions on Computers
JF - IEEE Transactions on Computers
IS - 9
M1 - 8986583
ER -