Please join us in the Electrical and Computer Engineering Department at the Technological Institute for an hour-long seminar with Professor Mor Harchol-Balter, PhD, from Carnegie Mellon University.

Abstract: Scheduling is the primary tool we have for improving system performance without purchasing additional resources. By simply changing the order in which we run jobs, we can dramatically improve response time (both mean response time and the tail of response time). Scheduling is particularly effective in the case of heavy-tailed job size distributions, which are omnipresent and can result in very high response times. In this talk we focus on the heavy-tailed job size setting.

We will start by reviewing optimal scheduling for the single-server queue (the M/G/1), both for the mean and asymptotic tail of response time. This is well understood.

We then turn to multi-server systems (the M/G/n), where almost nothing is understood on optimal scheduling. We present our new results on the first scheduling algorithms for the M/G/n which are asymptotically strongly tail optimal.

We finish by discussing newer job models, like the multi-server job model, which is representative of today's datacenter jobs. Here we present some recent algorithms for optimal scheduling under heavy traffic.

Throughout, our emphasis will be on intuition and lessons learned.

Bio: Mor Harchol-Balter is the Bruce J. Nelson Professor of Computer Science at Carnegie Mellon. She received her Ph.D. from U.C. Berkeley in 1996, under the direction of Manuel Blum. She is the SIG Chair for ACM SIGMETRICS (a 4-year elected position), having served as General Chair in 2013 and PC Chair in 2007. She is also a Fellow of both ACM and IEEE and has received several teaching awards, including the Herbert A. Simon Award and Spira Teaching Award. Mor's work focuses on designing new resource allocation policies, including load balancing policies, power management policies, and scheduling policies. Mor is heavily involved in the SIGMETRICS / PERFORMANCE / INFORMS research community where her papers have received many awards (ValueTools 24, INFORMS George Nicholson Prize 22, SIGMETRICS 21, SIGMETRICS 19, PERFORMANCE 18, INFORMS APS 18, EUROSYS 16, MASCOTS 16, MICRO 10, SIGMETRICS 03, ITC 03, SIGMETRICS 96). She is the author of two popular textbooks, both published by Cambridge University Press: Performance Analysis and Design of Computer Systems (2013), which bridges queueing theory and computer science, and Introduction to Probability for Computing (2024).