TY - GEN
T1 - Real-Time Scheduling and Analysis of OpenMP Task Systems with Tied Tasks
AU - Sun, Jinghao
AU - Guan, Nan
AU - Wang, Yang
AU - He, Qingqiang
AU - Yi, Wang
PY - 2018/1/31
Y1 - 2018/1/31
N2 - OpenMP is a promising framework for developing 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 the OpenMP specification. An important feature in OpenMP is tied tasks, which must execute on the same thread during the whole life cycle. Although tied tasks enjoy benefits in simplicity and efficiency, it was considered to be not suitable to real-time systems due to its complex behavior. In this paper, we study the realtime scheduling and analysis of OpenMP task systems with tied tasks. First, we show that under the existing scheduling algorithms in OpenMP, tied tasks indeed may lead to extremely bad timing behaviors where the parallel workload is sequentially executed completely. To solve this problem, we proposed a new scheduling algorithm and developed two response time bounds for it, with different trade-off between simplicity and analysis precision. Experiments with both randomly generated OpenMP task systems and realistic OpenMP programs show that the response time bounds obtained by our approach for tied task systems are very close to that of untied tasks.
AB - OpenMP is a promising framework for developing 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 the OpenMP specification. An important feature in OpenMP is tied tasks, which must execute on the same thread during the whole life cycle. Although tied tasks enjoy benefits in simplicity and efficiency, it was considered to be not suitable to real-time systems due to its complex behavior. In this paper, we study the realtime scheduling and analysis of OpenMP task systems with tied tasks. First, we show that under the existing scheduling algorithms in OpenMP, tied tasks indeed may lead to extremely bad timing behaviors where the parallel workload is sequentially executed completely. To solve this problem, we proposed a new scheduling algorithm and developed two response time bounds for it, with different trade-off between simplicity and analysis precision. Experiments with both randomly generated OpenMP task systems and realistic OpenMP programs show that the response time bounds obtained by our approach for tied task systems are very close to that of untied tasks.
KW - openmp
KW - parallel-software
KW - real-time-systems
KW - response-time-analysis
KW - tied-task
UR - http://www.scopus.com/inward/record.url?scp=85046351006&partnerID=8YFLogxK
U2 - 10.1109/RTSS.2017.00016
DO - 10.1109/RTSS.2017.00016
M3 - Conference article published in proceeding or book
VL - 2018-January
T3 - Proceedings - Real-Time Systems Symposium
SP - 92
EP - 103
BT - Proceedings - 2017 IEEE Real-Time Systems Symposium, RTSS 2017
PB - IEEE
T2 - 38th IEEE Real-Time Systems Symposium, RTSS 2017
Y2 - 5 October 2017 through 8 October 2017
ER -