XPS: FP: Real-Time Scheduling of Parallel Tasks

必须在特定期限内完成的任务（称为实时任务）出现在许多计算机与人类或物理环境交互的系统中，例如自动驾驶汽车、交通管理、机器人、工业过程管理、视频监控、雷达跟踪和混合结构测试。随着出现这种交互的应用程序域数量的增加，对能够在严格的时间限制下运行复杂任务的系统的需求也在增加。在一个独立但相关的趋势中，处理器时钟速度在很大程度上停滞不前，大多数现代计算机都是并行计算机，每个平台上都有多个内核或处理器。为了跟上新兴嵌入式系统的需求，并有效地利用多核计算机的能力，实时应用程序必须比迄今为止更有效地利用并行性。本研究将通过对如何有效地实现和执行并行实时任务进行理论和实证研究，使这些重要的应用成为可能。本研究旨在开发可证明的并行实时任务的良好算法。这些算法必须保证正确性和性能。重点研究三个具体方向：(1)调度基础：考虑现代并行平台的复杂性特点，设计和分析并行实时任务的高效调度算法。(2)同步机制：设计有效的同步技术，以实现不同任务之间的协调和资源共享，以及同一并行任务的不同线程。(3)并发平台：实现一个模块化和可扩展的实时并行任务并发平台，用于开发、测试和验证运行这些任务所需的调度和同步机制。这个平台将在最大限度允许的开源许可下提供给那些希望并行化实时应用程序或扩展平台本身以验证他们自己的调度解决方案的从业者。

Tasks which must complete by specific deadlines (known as real-time tasks) appear in many systems where computers interact with humans or the physical environment such as autonomous vehicles, traffic management, robotics, industrial process management, video surveillance, radar tracking, and hybrid structural testing. With a growing number of application domains where this kind of interaction occurs, there is an increasing need for systems that can run complex tasks within stringent timing constraints. In a separate, but related trend, processor clock speeds have largely stagnated, and most modern computers are parallel computers with multiple cores or processors on each platform. Both to keep up with the demands of emerging embedded systems, and to exploit the capacity of multicore computers effectively, real-time applications must harness parallelism more effectively than has been possible to date.  This research will enable these important applications by conducting both theoretical and empirical research on how to implement and execute parallel real-time tasks efficiently.This research intends to develop provably good algorithms for parallel real-time tasks.  These algorithms must provide guarantees of both correctness and performance. The research focuses on three specific directions: (1) Scheduling foundations: Design and analysis of efficient scheduling algorithms for parallel real time tasks that take the complex characteristics of modern parallel platforms into consideration.  (2) Synchronization mechanisms: Design of effective synchronization techniques in order to allow coordination and resource sharing between different tasks as well as different threads of the same parallel task.  (3) Concurrency platform: Implementation of a modular and extensible concurrency platform for real-time parallel tasks that will be used to develop, test and validate the scheduling and synchronization mechanisms required to run these tasks.  This platform will be made available under a maximally permissible open source license to practitioners who wish to parallelize their real-time applications or to extend the platform itself to validate their own scheduling solutions.