About Us
Our goal is to develop and evaluate concurrency platforms, analyses, and scheduling and synchronization techniques for parallel real-time computing. As multi-core architectures become increasingly common and sequential processing speeds stagnate while numbers of cores grow, parallel computing becomes necessary for real-time systems with significant computational demands. We focus on enabling the computation-intensive real-time and cyber-physical systems of tomorrow, including those for increasingly autonomous vehicles and real-time hybrid simulation, among others.
To that end, we have three objectives:
- Develop theoretical models for parallel real-time computataion.
- Construct runtime systems capable of executing parallel real-time workloads.
- Create methods for logging and analyzing runtime performance of multi-processor real-time systems.
Real-Time Scheduling and Platform for Parallel Tasks
During the last decade, the performance increase of processor chips has come primarily from increasing numbers of cores. It is important for real-time programs to take advantage of real-time scheduling techniques that can exploit multicore and multiprocessor systems. In order to enable tasks with higher execution demands and tighter deadlines, such as those used in autonomous vehicles, video surveillance, computer vision, radar tracking and real-time hybrid testing, we must enable parallelism within tasks.
Parallel Real-Time Scheduling Theory
Our hope is to classify and provide a range of task models for various parallel workloads. We are currently investigating the parallel-synchronous task model for bulk-synchronous parallelism under static priority partitioned scheduling, and the general directed acyclic graph (DAG) model for general parallelism under earliest deadline first (EDF) scheduling.
Our previous work on scheduling parallel tasks derived bounds for partitioned deadline monotonic and global EDF based on decomposing each parallel task into a set of sequential subtasks. We are currently analyzing the performance of a global EDF scheduler without decomposition and a clustered scheduler. Our hope is to derive schedulability analysis, augmentation bounds and easy schedulability test for scheduling parallel tasks under different scheduling algorithms.
Our current work in elastic parallel real-time systems allows for the dynamic re-allocation of resources for parallel real-time tasks. Specicically, each task may adapt its period or workload. Our hope is to generalize this to allow for each task to simultaneously adapt its period and workload for full system elasticity and adaptability under a variety of scheduling paradigms.
Real-Time OpenMP (RT-OpenMP)
A real-time concurrency platform that provides a parallel programming language, automatic task set analysis and scheduling onto Linux-based real-time platforms. RT-OpenMP currently implements the parallel-synchronous task model, but we will expand this as we are able.
Real-Time Logging and Visualization
Parallel runtime systems are inherently more complex than sequential systems, so to support the ongoing development of RT-OpenMP and other multi-processor real-time systems we are currently developing software to provide robust and non-interfering data logging and system analysis.
Contributors
WashU CSE Faculty
Doctoral Students
- Son Dinh (former)
- David Ferry (former, now at St. Louis University)
- Jing Li (former, now at New Jersey Institute of Technology)
- James Orr (former, now faculty at WUSTL)
- Abusayeed Saifullah (former, now at Wayne State University)
Master's and Undergraduate Students
- Shaurya Ahuja (MS, former)
- John Emmons (BS, former)
- Kevin Kieselbach (MS, former)
- Jordan Krage (MS, former)
- Mahesh Mahadevhan (MS, former)
- Anish Naik (MS, former)
- Tommy Powers (BS, former)
- Kevin Zheng (BS, former)
Summer Undergraduate Researchers
- Phyllis Ang (2018)
- Bradley Beeksma (2015)
- Harsh Bhatt (2013)
- Steven Bosch (2015)
- Christian Cianfarani (2018)
- Matt Dole (2014)
- Meir Friedenberg (2014)
- Sierra Gregg (2013)
- Nick Nooney (2014)
- Joey Woodson (2014)
- Christopher Wong (2018)
Publications
J. Orr, C. Gill, K. Agrawal, J. Li, and S. Baruah, Elastic Scheduling for Parallel Real-Time Systems, Leibniz Transactions on Embedded Systems, accepted.
N. Ueter, G. von der Bruggen, J. Chen, J. Li and K. Agrawal, Reservation-Based Federated Scheduling for Parallel Real-Time Tasks, IEEE Real-Time Systems Symposium (RTSS'18), December 2018. Outstanding Paper Award
J. Orr, C. Gill, K. Agrawal, S. Baruah, C. Cianfarani, P. Ang and C. Wong. Elasticity of Workloads and Periods of Parallel Real-Time Tasks, In Proceedings of the 26th International Conference on Real-Time Networks and Systems (RTNS '18). ACM, New York, NY, USA, 61-71. October 2018.
S. Dinh, J. Li, K. Agrawal, C. Gill and C. Lu, Blocking Analysis for Spin Locks in Real-Time Parallel Tasks, IEEE Transactions on Parallel and Distributed Systems, 29(4): 789-802, April 2018.
J. Li, D. Ferry, S. Ahuja, K. Agrawal, C. Gill and C. Lu, Mixed-Criticality Federated Scheduling for Parallel Real-Time Tasks, Real-Time Systems Journal, Special Issue on Mixed-Criticality, Multi-Core, and Micro-Kernels, 53(5): 760-811, May 2017.
J. Li, D. Ferry, S. Ahuja, K. Agrawal, C. Gill and C. Lu, Mixed-Criticality Federated Scheduling for Parallel Real-Time Tasks, IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'16), April 2016. Outstanding Paper Award
J. Li, Z. Luo, D. Ferry, K. Agrawal, C. Gill and C. Lu, Global EDF Scheduling for Parallel Real-Time Tasks, Real-Time Systems, Special Issue on Best Papers of ECRTS'13, 51(4): 395-439, July 2015.
A. Saifullah, D. Ferry, J. Li, K. Agrawal, C. Lu and C. Gill, Parallel Real-Time Scheduling of DAGs, IEEE Transactions on Parallel and Distributed Systems, 25(12): 3242-3252, December 2014.
D. Ferry, G. Bunting, A. Megareh, S. Dyk, A. Prakash, K. Agrawal, C. Gill and C. Lu, Real-Time System Support for Hybrid Structural Simulation, ACM International Conference on Embedded Software (EMSOFT'14), October 2014.
J. Li, K. Agrawal, C. Gill and C. Lu, Federated Scheduling for Stochastic Parallel Real-time Tasks, IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'14), August 2014.
J. Li, J.-J. Chen, K. Agrawal, C. Lu, C. Gill and A. Saifullah, Analysis of Federated and Global Scheduling for Parallel Real-Time Tasks, Euromicro Conference on Real-Time Systems (ECRTS'14), July 2014.
D. Ferry, A. Megareh, G. Bunting, A. Prakash, K. Agrawal, C. Gill, C. Lu and S. Dyke, On the Performance of a Highly Parallelizable Concurrency Platform for Real-Time Hybrid Simulation, World Conference on Structural Control and Monitoring (6WCSCM), July 2014.
J. Li, K. Agrawal, C.Lu and C.D. Gill, Analysis of Global EDF for Parallel Tasks, Euromicro Conference on Real-Time Systems (ECRTS'13), July 2013. Outstanding Paper Award
D. Ferry, J. Li, M. Mahadevan, K. Agrawal, C.D. Gill and C. Lu, A Real-Time Scheduling Service for Parallel Tasks, IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'13), April 2013.
Abusayeed Saifullah, David Ferry, Kunal Agrawal, Chenyang Lu, Christopher Gill, Real-Time Scheduling of Parallel Tasks Under a General DAG Model (Technical Report 2012), Tech. Rep., WUCSE-2012-14, Washington University in St Louis; 2012
A. Saifullah, K. Agrawal, C. Lu and C.D. Gill, Multi-core Real-Time Scheduling for Generalized Parallel Task Models (RTSS 2011), IEEE Real-Time Systems Symposium (RTSS'11), December 2011. Best Student Paper Award
J. Li, K. Agrawal, S. Elnikety, Y. He, A. Lee, C. Lu and K.S McKinley, Work Stealing for Interactive Services to Meet Target Latency, ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'16), March 2016.
Source Code
Our decomposition based scheduling code can be gotten here. This work is described more fully in A Real-Time Scheduling Service for Parallel Tasks. Installation information and examples are provided, licensing information can be found within the LICENSE file at the root directory.
Our clustered scheduling software can be found here. You can find the user guide here.
Our elastic federating scheduling software from the RTNS 2018 paper can be found here. For usage please see the README in the root directory.
Our discrete elastic federating scheduling software can be found here.
This software is not fully mature- please feel free to direct questions to the authors below!