Most modern computing systems contain multiprocessor hardware which is shared by many applications. In these systems, good scheduling algorithms that decide how to allocate resources among applications are crucial to ensure good quality of service and efficient use of system resources. This project will design foundational algorithms and prototype implementations of scheduling algorithms that provide guarantees of performance and resource utilization for these shared machines. This work will shape the efficiency of critical computing infrastructure by improving performance of parallel systems from personal computers to data centers to supercomputers. All results, including published articles and software artifacts, will be released to the public via world-wide web. The PIs will integrate research with education by incorporating this research into the PIs' graduate courses and training PhD, MS, and BS students in applied and theoretical parallel computing research.
The project will involve designing practically efficient schedulers guided by theoretical foundations. The PIs will design a theory of multi-programmed scheduling for parallel programs by considering a variety of scheduling objectives important to system designers. In particular, the research will focus on optimizing latency objectives that are used in servers, clouds, and interactive systems. The PIs will also explore efficient mechanisms that can be used to implement these algorithms in practice and perform empirical validations of their designs. By combining theoretical analysis with feedback from empirical evaluations, the proposed work will gain insights that will advance the state of the art of both theory and practice of parallel job scheduling.
