Real-Time Scheduling and Analysis of OpenMP DAG Tasks Supporting Nested Parallelism
Real-Time Scheduling and Analysis of OpenMP DAG Tasks Supporting Nested Parallelism
复制标题
支持嵌套并行的 OpenMP DAG 任务实时调度与分析
DOI：
10.1109/tc.2020.2972385
复制
发表时间：
2020-09
影响因子：
3.7
通讯作者：
Yi Wang
中科院分区：
文献类型：
--
作者：
Sun Jinghao;Guan Nan;Li Feng;Gao Huimin;Shi Chang;Yi Wang
OpenMP是一个很有前途的多核并行实时软件开发框架。尽管与DAG任务模型相似，但由于OpenMP规范的限制，OpenMP任务系统的分析难度要大得多。OpenMP中最有趣的特性之一是对嵌套并行的支持，这在增强并行库的性能透明度和促进黑盒代码的重用方面带来了好处。以往对DAG任务调度的研究主要局限于单一并行度。具有多层并行性的OpenMP任务是否适合实时系统的问题仍然没有解决。本文研究了支持嵌套并行的OpenMP任务系统的实时调度和分析。首先，我们展示了在OpenMP实现中现有的调度算法下，嵌套并行确实可能导致并行工作负载完全顺序执行的极端糟糕的计时行为。为了解决这个问题，我们提出了一种新的调度算法，并考虑了简单性和分析精度之间的权衡，制定了两个合理的响应时间界限。实验证明了我们方法的有效性。
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.
登录
查看更多内容
DOI：
10.1109/tpds.2013.2297919
发表时间：
2014-12
影响因子：
5.3
作者：
Abusayeed Saifullah;D. Ferry;Jing Li;Kunal Agrawal;Chenyang Lu;C. Gill
通讯作者：
Abusayeed Saifullah;D. Ferry;Jing Li;Kunal Agrawal;Chenyang Lu;C. Gill
DOI：
10.1007/978-3-540-79561-2_1
发表时间：
2008-05
期刊：
--
影响因子：
--
作者：
V. Dimakopoulos;P. Hadjidoukas;G. C. Philos
通讯作者：
V. Dimakopoulos;P. Hadjidoukas;G. C. Philos
DOI：
10.1016/b978-0-12-803819-2.00022-7
发表时间：
2016
期刊：
--
影响因子：
--
作者：
Jeongnim Kim;Lawrence Meadows
通讯作者：
Jeongnim Kim;Lawrence Meadows
DOI：
10.1016/b978-0-12-803819-2.00024-0
发表时间：
2015
期刊：
--
影响因子：
--
作者：
James Briggs;S. Pennycook;J. Fergusson;J. Jäykkä;E. Shellard
通讯作者：
James Briggs;S. Pennycook;J. Fergusson;J. Jäykkä;E. Shellard
DOI：
10.1109/rtas.2013.6531098
发表时间：
2013-04
期刊：
2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS)
影响因子：
--
作者：
D. Ferry;Jing Li;M. Mahadevan;Kunal Agrawal;C. Gill;Chenyang Lu
通讯作者：
D. Ferry;Jing Li;M. Mahadevan;Kunal Agrawal;C. Gill;Chenyang Lu