Provably-Efficient Adaptive Scheduling with Parallelism Feedback

Опубликовано 7 сентября 2016, 17:31

This talk presents feedback-driven adaptive algorithms for efficient scheduling of parallel jobs on multiprogrammed multiprocessors. Multiprocessor scheduling is often structured in two levels, where a kernel-level OS allocator allots processors to jobs and a user-level task scheduler schedules the ready tasks of a job on the allotted processors. In the context of adaptive scheduling, the demand of a parallel job may scale up and down. Therefore, the number of processors allotted to a particular job should vary during the job's execution, and the task scheduler must also adapt to these changes in processor resources. For overall system efficiency, the task scheduler should provide parallelism feedback to the OS allocator to avoid situations, where a job is either allotted too many processors to use productively or it is allotted too few processors to complete without undue delay. Since the future parallelism of a job is generally unknown, how to provide effective parallelism feedback and allocate processors efficiently is a significant research challenge. This talk provides an overview of several adaptive scheduling algorithms we have developed. The proposed schedulers operate in an online nonclairvoyant manner, oblivious to the future characteristics of a job. Firstly the task scheduler A-Greedy provides provably good history-based feedback about a job's parallelism without knowing its future. A-Greedy completes a job in near-optimal time while guaranteeing low waste. Secondly, when A-Greedy is integrated with OS allocator RAD, the two-level scheduler GRAD achieves O(1)-competitiveness against an optimal offline scheduling algorithm with respect to both mean response time and makespan for batched jobs and nonbatched jobs, respectively. GRAD is the first nonclairvoyant scheduling algorithm to offer such performance guarantees. The talk also addresses the design considerations of developing efficient adaptive scheduling algorithms, and discusses the performance improvements with a semi-clairvoyant scheduler that possesses certain information on jobs' parallelism.