Oct 11, 2016
Jolley Hall, Room 309
"Scheduling Parallel Jobs with Deadlines"Jing Li
Advisor: Chenyang Lu
In order to provide safety guarantees or quality of service guarantees, many of today's systems consist of applications with deadlines. The problem of scheduling multiple jobs with deadlines 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. While the problem of scheduling jobs with deadlines has been well-studied for sequential jobs, there is little work considering scheduling multiple parallel jobs with deadlines. Therefore, in this proposal we will focus on different scheduling strategies for parallel jobs with deadlines 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.
In summary, my overall goal is to design, analyze, implement and evaluate scheduling strategies for executing parallel jobs with deadlines on multicore systems.