Communications and Signal Processing Seminar

How to Schedule Near-Optimally under Real-World Constraints

Ziv ScullyPh.D. CandidateComputer Science, Carnegie Mellon University
WHERE:
Remote/Virtual
WHEN:
Thursday, September 9, 2021 @ 4:00 pm - 5:00 pm
This event is free and open to the publicAdd to Google Calendar
SHARE:

ABSTRACT: Scheduling is a critical part of practical computer systems, and scheduling has also been extensively studied from a theoretical perspective. Unfortunately, there is a gap between theory and practice, as the optimal scheduling policies presented by theory can be difficult or impossible to perfectly implement in practice. In this work, we use recent breakthroughs in queueing theory to begin to bridge this gap. We show how to translate idealized policies from theory—which provably minimize mean response time (a.k.a. latency)—into near-optimal policies that are easily implemented in practical settings. Specifically, we handle the following real-world constraints:

  • We show how to schedule in systems where job sizes (a.k.a. running times) are unknown, or only partially known. We do so using simple policies that achieve performance very close to the much more complicated theoretically optimal policies.
  • We show how to schedule in systems that have only a limited number of priority levels available. We show how to adapt theoretically optimal policies to this constrained setting and determine how many levels we need for near-optimal performance.
  • We show how to schedule in systems where job preemption can only happen at specific checkpoints. Adding checkpoints allows for smarter scheduling, but each checkpoint incurs time overhead. We give a rule of thumb that near-optimally balances this tradeoff.

Related Papers:

  1. https://ziv.codes/publications/#soap-one-clean-analysis-of-all-age-based-scheduling-policies.
  2. https://ziv.codes/publications/#the-gittins-policy-in-the-mg1-queue.

BIO: Ziv Scully is a graduate student in Computer Science at CMU advised by Mor Harchol-Balter and Guy Blelloch. He graduated from MIT in 2016 with a BS in Mathematics with Computer Science. He is the recipient of an NSF Graduate Fellowship and an ARCS Foundation scholarship. Ziv’s research focus is optimizing and analyzing computer systems and algorithms from a stochastic perspective, including job scheduling, load balancing, combinatorial optimization under uncertainty, and parallel algorithms. Recent publications of his have been recognized with awards from ACM SIGMETRICS (Best Paper Award, 2021; Best Video Award, 2020; Outstanding Student Paper Award, 2019), IFIP PERFORMANCE (Best Student Paper Award, 2018), and the INFORMS Applied Probability Society (Best Student Paper Prize finalist, 2018). During the COVID-19 pandemic, he served as an algorithms consultant for the NOVID exposure-notification project.

Join Zoom Meeting https://umich.zoom.us/j/92211136360

Meeting ID: 922 1113 6360

Passcode: XXXXXX (Will be sent via e-mail to attendees)

Zoom Passcode information is also available upon request to Katherine Godwin ([email protected]).

See Full seminar by Ziv Scully

Faculty Host

Lei YingProfessorEECS, University of Michigan