Position: Ph.D. Student

Current Institution: University of Washington in St. Louis

Abstract:
Federated Scheduling for Real-Time Systems with Parallel Tasks

Real-time scheduling is used in many cyber-physical systems where applications interact with humans or the physical environment. The scheduling of real-time tasks is different from traditional scheduling because real-time tasks have deadlines, usually according to the need in physical world. Therefore, the scheduling theory and system must provide guarantees assuring that all deadlines can be met. For more than four decades, researchers have developed theories to provide real-time guarantees for sequential tasks on single and multi-processor machines. Recently, parallel tasks with real-time needs have been studied to keep up with the demands of emerging computation intensive tasks and to use multi-core hardware platforms more effectively. However, parallel tasks present new challenges due to their potentially complex dependence structures.

This work proposed and analyzed a new scheduling algorithm, named federated scheduling, for real-time systems with parallel tasks. Federated scheduling calculates the minimum number of cores a parallel task required for meeting its deadline and assigns these dedicated cores to the parallel task. Federated scheduling is proven to have the best theoretical performance. In addition, since tasks are executed without interference from other tasks, federated scheduling also reduces scheduling overheads in practice. Based on above theoretical results, we implemented a federated scheduling system and show that with this system we are now able to perform higher computation within stringent deadlines. In hybrid-testing framework, for example, this allows us to run simulation with larger and more accurate structures.

Bio:
Jing Li is a 5th-year PhD student at Washington University in St. Louis, co-advised by Professors Kunal Agrawal and Professor Chenyang Lu. She is interested in designing theoretically sound and practically efficient schedulers for multiple parallel jobs. More specifically, she designs and analyzes schedulers for systems with dynamically arriving parallel jobs to provide various quality of service guarantees, such as optimizing different latency related objectives for cloud computing platforms (such as Bing search servers) and meeting deadlines for real-time systems (such as autonomous vehicles and other cyber-physical systems). Her work improves our theoretical understanding of how to schedule parallel tasks in multi-core systems to meet specific performance guarantees, but she is not stopping there and is actively involved in
“closing the loop”, i.e., ensuring that this improved theoretical understanding also impacts how
we implement the schedulers in real systems. Her research output includes three journal papers in two of the top venues in her field (IEEE Transactions on Parallel and Distributed Systems, and Real-Time Systems) and eight conference publications in some of the top venues (RTAS’13, ECRTS’14, RTCSA’14, SODA’16, PPoPP’16, SPAA’16, ECRTS’13 and RTAS’16 – the latter two having earned two Outstanding Paper Awards).