New Approaches to Multiserver Scheduling

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

This award will contribute to the advancement of national prosperity and economic welfare by deriving efficient scheduling methods to improve response times across a range of critical service industries, notably in cloud computing and data center management. The significant rise in artificial intelligence applications, particularly large language models, puts a heavy burden on existing computing environments and requires efficient scheduling of thousands of processing resources to meet performance requirements. This project will develop new queueing methods to extend beyond current single- or small multi-server models to very large scale multi-server models. The project will provide tools that enable practitioners to design smarter scheduling policies, thereby improving the responsiveness and efficiency of modern data centers and resulting in economic and environmental benefits. The project includes activities to mentor female graduate students, and broad dissemination of results to different communities through tutorials and an online textbook. This project will employ queueing-theoretic analysis to explore the performance of complex scheduling policies, including Shortest Remaining Processing Time and the Gittins Index, for multi-server queues. The project will develop new theory for scheduling in multi-server systems that significantly extends previously considered job models and allows for far more representative characterization of today's data centers. These include consideration of multi-server jobs, where a single job requires several servers simultaneously to run, jobs with dynamically changing holding costs, and dependencies between jobs. The performance metrics considered will also be driven by today's cloud systems, with particular emphasis on meeting tail response time targets, rather than simply meeting average waiting time targets. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.