随着多核技术发展,实时嵌入式领域日益关注软件的高性能和实时性.OpenMP能够充分反映实时计算的并行特征,是构建下一代实时嵌入式系统最有希望的编程范式之一.OpenMP实时调度理论突破了传统理论局限性,产生了许多挑战性问题.这些问题虽然在应用中已遇到,但尚未解决.本课题正是针对OpenMP实时调度中的困难问题开展研究,具体特色和创新之处:一是针对OpenMP复杂并行语义,提出全新的实时调度算法和程序响应时间分析(RTA)理论.二是针对并行-分支嵌套的程序特征,研究RTA计算复杂性理论,设计伪多项式时间算法.三是针对OpenMP程序-调度闭环交互难题,彻底突破传统的“模型-算法-分析”递进式理论框架,将调度算法纳入问题模型,基于最优化理论和方法提出OpenMP程序RTA问题的全新理论框架.通过上述研究,将实时调度理论和方法纳入到OpenMP技术框架中,加速OpenMP实时标准的构建进程.

Multicores are becoming mainstream platforms for real-time embedded systems, to meet their increasing requirements in high performance and low power consumption. To fully utilize the capacity of multicores, software must be parallelized. OpenMP is the de facto parallel programming framework on shared memory architectures. It has been widely used in general purpose and high-performance computing, and recently gains a lot of attentions in real-time embedded community. Real-time scheduling of OpenMP tasks breaks through the limitation of traditional real-time scheduling theories, and brings many challenging problems. Nowadays, some of these problems have been conquered, and some are still open, although they have been come up with in real-world applications. This project focuses on these kind of difficult problems in the real-time scheduling of OpenMP task systems. .This research aims to investigate the real-time scheduling problem for OpenMP task systems systematically, and to conquer the challenges in theories, formulations, algorithms and applications. The main contributions of the project are listed as follows..(1).We analyze how the complicate OpenMP semantics affect the scheduling behavior in runtimes, and propose the novel scheduling algorithms for OpenMP tasks and provide guaranteed response time bound for OpenMP programs..(2).We consider the if-else and loop conditional components in the OpenMP programs, and investigate the computational complexity theories for the response time bound calculation problems for the OpenMP system with conditional branches. Moreover, if response-time bound calculation problems are NP-hard, we propose the pseudo-polynomial time algorithm to solve them. .(3).OpenMP programs are interactive with scheduling algorithms, i.e., OpenMP programs are able to change their structure to adapt different states of scheduling algorithms during the runtime. The traditional real-time analysis framework is not available for the interactive OpenMP programs. Thus, we propose a new theory framework for analysis of interactive OpenMP programs. More details, we formulate the OpenMP tasks and the scheduling algorithm into a single formulation, and then use the methodologies of optimization theory to solve such formulation, and eventually obtain the response time bound. . The ultimate goal of this project is to understand existing and missing features of OpenMP making it suitable to real-time systems, so that timing correctness can be guaranteed while the benefit of using OpenMP in performance and programmability are maximized. From a long-term perspective, the insights gained in this project may potentially push forwards the OpenMP standard to include official real-time support.