Monday, October 19, 2020 - 4:00pm to Tuesday, October 20, 2020 - 4:55pm
Event Calendar Category
LIDS Seminar Series
Speaker Name
Mor Harchol-Balter
Affiliation
Carnegie Mellon University
Event Recording
Zoom meeting id
989 1074 4103
Join Zoom meeting
https://mit.zoom.us/j/98910744103
Abstract
Scheduling policies are at the heart of computer systems. The right scheduling policy can dramatically reduce response times, ensure fairness, provide class-based priority, etc., without requiring additional resources. While stochastic response time analysis of different scheduling policies has been the focus of thousands of theoretical papers, results are limited to analyzing a relatively small number of "simple" scheduling policies. In this talk, we introduce the SOAP class of scheduling policies: Schedule Ordered by Age-based Priority. The SOAP policies include most of the scheduling policies in the literature as well as an infinite number of variants that have never been analyzed or maybe even conceived. SOAP policies include the highly intractable SERPT policy (Shortest-Expected-Remaining-Processing-Time), as well as the famously complex Gittins Index policy. SOAP also includes all sorts of "combination" policies, like a policy that performs Shortest Job First on jobs with known size and Foreground-Background scheduling on jobs with unknown size, or a policy that is allowed to preempt jobs only when they hit certain checkpoint ages. In this talk, we present a stochastic response time analysis of all SOAP policies in the M/G/1 setting. If time permits, we will briefly mention new SOAP-related work for the M/G/k.
This talk is based on the SOAP paper with Ziv Scully and Alan Scheller-Wolf (Sigmetrics 2018, APS 2018 Best Student Paper Finalist). SOAP follow-up work includes papers with Isaac Grosof and Ziv Scully in Performance 2018 (Best Student Paper Award), Sigmetrics 2019 (Best Student Paper Award), Sigmetrics 2020 (Best Video Award), Performance 2020, and Sigmetrics 2021.
Biography
Mor Harchol-Balter is the Bruce J. Nelson Professor of Computer Science at CMU. She received her Ph.D. from U.C. Berkeley in 1996 and did her postdoc at MIT from 1996-1999, under the NSF Mathematical Sciences Postdoctoral Fellowship. Mor is a Fellow of both the ACM and IEEE. She is a recipient of the NSF CAREER award, many teaching awards, and dozens of faculty research awards from companies with whom she collaborates, particularly Google, Microsoft, Facebook, IBM, and Intel. 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 research community, where she has received many best paper awards. She is also the author of a popular textbook, "Performance Analysis and Design of Computer Systems," published by Cambridge University Press, which bridges Operations Research and Computer Science. Mor is best known for her vivacious keynote talks and her many successful PhD students.
