XPS: FP: Real-Time Scheduling of Parallel Tasks

Washington University, Saint Louis MO

Investigators

Abstract

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.