Jul 21, 2017
Jolley Hall, Room 309
Scheduling for Latency-Critical Applications"
Advisers: Chenyang Lu and Kunal Agrawal
In order to provide safety guarantees or quality of service guarantees, many of today's systems consist of latency-critical applications, e.g. applications with deadlines. The problem of scheduling multiple latency-critical jobs on a multiprocessor or multicore machine has been extensively studied for sequential (non-parallizable) jobs and different system models and different objectives have been considered. However, the computational requirement of a single job is still limited by the capacity of a single core. To provide increasingly complex functionalities of applications and to complete their higher computational demands within the same or even more stringent deadlines, we must exploit the internal parallelism of jobs, where individual jobs are parallel programs and can potentially utilize more than one core in parallel. However, there is little work considering scheduling multiple parallel jobs that are latency-critical.
This dissertation will focus on different scheduling strategies for latency-critical parallel jobs on multicore systems. In particular, the research is focused on two types of systems: static systems where the temporal properties of the jobs that need to execute is known a priori and the goal is to guarantee the temporal correctness of the applications prior to their executions; and dynamic systems where multiple jobs arrive over time and the goal to optimize for a performance objective during the execution. For static systems, I will show that federated scheduling, global earliest deadline first and global rate monotonic have the best known theoretical performance for parallel tasks under any scheduling strategy, any global strategy and any fixed priority scheduling, respectively. In addition, I will generalize federated scheduling to systems with stochastic tasks and systems with multiple criticality levels and prove the first known results in these problem settings. For dynamic systems, I will analyze different online scheduling strategies for different objectives, including minimizing the maximum flow time and maximizing the number of jobs meeting a target latency or individual deadlines.