Computer Science Thesis Oral

— 4:00pm

Location:
In Person and Virtual - ET - Gates Hillman 8102 and Zoom

Speaker:
ISAAC GROSOF , Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://isaacg1.github.io/

Optimal Scheduling in Multiserver Queues

Scheduling theory is a key tool for reducing latency (i.e. response time) in queueing systems. Scheduling, i.e. choosing the order in which to serve jobs, can reduce response time by an order of magnitude with no additional resources. Scheduling theory is well-developed in single-server systems, where one job is processed at a time. However, almost nothing is known about scheduling in multiserver systems, where many jobs are processed at once. Today's datacenters have thousands of servers, and scheduling theory is unable to analyze such systems. This thesis proves the first optimality results and first mean response time analysis for scheduling policies in multiserver models which reflect the behavior of modern computing systems. The thesis explores three themes:

  1. I start by studying one-server-per-job multiserver models, and prove the first results on optimal scheduling in that setting. Optimality results are proven for both a central-queue model and a dispatching model. I invent a novel class of dispatching policies, guardrails, to achieve these results.
  2. Next, I study the multiserver-job (MSJ) model, where different jobs require different amounts of resources to be served. I prove the first characterization of mean response time for any scheduling policy in the MSJ model, as well as the first optimality results. I invent novel scheduling policies, ServerFilling and ServerFilling-SRPT, to achieve these results.
  3. Finally, I study the effects of scheduling on the tail of response time, rather than mean response time. The prior state-of-the-art for scheduling for the tail was First-Come First-Served, which was conjectured to achieve optimal asymptotic tail. I invent a novel scheduling policy, Nudge, which I prove to be the first policy to outperform FCFS's asymptotic tail of response time.

Thesis Committee:

Mor Harchol-Balter (Chair)
Weina Wang
Anupam Gupta
Alan Scheller-Wolf
Michael Mitzenmacher (Harvard University)

In Person and Zoom Participation. See announcement.


Add event to Google
Add event to iCal