36 citations · 122 across the 30 of their papers we have counts for
33 papers
DynaSPLIT: Strong tail-optimal scheduling for the M/G/n with heavy-tailed job sizes
Zhouzi Li, Mor Harchol-Balter, Alan Scheller-Wolf
We study the asymptotic response time tail in the M/G/n queue with heavy-tailed (regularly varying) job sizes. For this setting, strongly tail optimal policies are known only at lo…
SPLIT: SymPathy for Large jobs Improves Tail latency
Zhouzi Li, Mor Harchol-Balter, Alan Scheller-Wolf
We study the asymptotic response time tail in the M/G/n multi-server queue with heavy-tailed (regularly varying) job sizes, a setting representative of modern computing workloads.…
Mean field optimal Core Allocation across Malleable jobs
Zhouzi Li, Mor Harchol-Balter, Benjamin Berg
Modern data centers and cloud computing clusters are increasingly running workloads composed of malleable jobs. A malleable job can be parallelized across any number of cores, yet…
BOA Constrictor: Squeezing Performance out of GPUs in the Cloud via Budget-Optimal Allocation
Zhouzi Li, Cindy Zhu, Arpan Mukhopadhyay +2
The past decade has seen a dramatic increase in demand for GPUs to train Machine Learning (ML) models. Because it is prohibitively expensive for most organizations to build and mai…
LookAhead: The Optimal Non-decreasing Index Policy for a Time-Varying Holding Cost problem
Keerthana Gurushankar, Zhouzi Li, Mor Harchol-Balter +1
In practice, the cost of delaying a job can grow as the job waits. Such behavior is modeled by the Time-Varying Holding Cost (TVHC) problem, where each job's instantaneous holding…
An Upper Bound on the M/M/k Queue With Deterministic Setup Times
Jalani Williams, Weina Wang, Mor Harchol-Balter
In many systems, servers do not turn on instantly; instead, a setup time must pass before a server can begin work. These "setup times" can wreak havoc on a system's queueing; this…
Improving Upon the generalized c-mu rule: a Whittle approach
Zhouzi Li, Keerthana Gurushankar, Mor Harchol-Balter +1
Scheduling a stream of jobs whose holding cost changes over time is a classic and practical problem. Specifically, each job is associated with a holding cost (penalty), where a job…
How to Rent GPUs on a Budget
Zhouzi Li, Benjamin Berg, Arpan Mukhopadhyay +1
The explosion in Machine Learning (ML) over the past ten years has led to a dramatic increase in demand for GPUs to train ML models. Because it is prohibitively expensive for most…
Analysis of Markovian Arrivals and Service with Applications to Intermittent Overload
Isaac Grosof, Yige Hong, Mor Harchol-Balter
In many important real-world queueing settings, arrival and service rates fluctuate over time. We consider the MAMS system, where the arrival and service rates each vary according…
Can Increasing the Hit Ratio Hurt Cache Throughput? (Long Version)
Ziyue Qiu, Juncheng Yang, Mor Harchol-Balter
Software caches are an intrinsic component of almost every computer system. Consequently, caching algorithms, particularly eviction policies, are the topic of many papers. Almost a…
Asymptotically Optimal Scheduling of Multiple Parallelizable Job Classes
Benjamin Berg, Benjamin Moseley, Weina Wang +1
Modern computing workloads are often composed of parallelizable jobs. A parallelizable job can be completed more quickly when run on additional servers. However, each job can only…
The RESET and MARC Techniques, with Application to Multiserver-Job Analysis
Isaac Grosof, Yige Hong, Mor Harchol-Balter +1
Multiserver-job (MSJ) systems, where jobs need to run concurrently across many servers, are increasingly common in practice. The default service ordering in many settings is First-…
Optimal Scheduling in the Multiserver-job Model under Heavy Traffic
Isaac Grosof, Ziv Scully, Mor Harchol-Balter +1
Multiserver-job systems, where jobs require concurrent service at many servers, occur widely in practice. Essentially all of the theoretical work on multiserver-job systems focuses…
The Gittins Policy in the M/G/1 Queue
Ziv Scully, Mor Harchol-Balter
The Gittins policy is a highly general scheduling policy that minimizes a wide variety of mean holding cost metrics in the M/G/1 queue. Perhaps most famously, Gittins minimizes mea…
How to Schedule Near-Optimally under Real-World Constraints
Ziv Scully, Mor Harchol-Balter
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…
Computing the Death Rate of COVID-19
Naveen Pai, Sean Zhang, Mor Harchol-Balter
The Infection Fatality Rate (IFR) of COVID-19 is difficult to estimate because the number of infections is unknown and there is a lag between each infection and the potentially sub…
WCFS: A new framework for analyzing multiserver systems
Isaac Grosof, Mor Harchol-Balter, Alan Scheller-Wolf
Multiserver queueing systems are found at the core of a wide variety of practical systems. Many important multiserver models have a previously-unexplained similarity: identical mea…
Nudge: Stochastically Improving upon FCFS
Isaac Grosof, Kunhe Yang, Ziv Scully +1
The First-Come First-Served (FCFS) scheduling policy is the most popular scheduling algorithm used in practice. Furthermore, its usage is theoretically validated: for light-tailed…
heSRPT: Parallel Scheduling to Minimize Mean Slowdown
Benjamin Berg, Rein Vesilo, Mor Harchol-Balter
Modern data centers serve workloads which are capable of exploiting parallelism. When a job parallelizes across multiple servers it will complete more quickly, but jobs receive dim…
Zero Queueing for Multi-Server Jobs
Weina Wang, Qiaomin Xie, Mor Harchol-Balter
Cloud computing today is dominated by multi-server jobs. These are jobs that request multiple servers simultaneously and hold onto all of these servers for the duration of the job.…
Stability for Two-class Multiserver-job Systems
Isaac Grosof, Mor Harchol-Balter, Alan Scheller-Wolf
Multiserver-job systems, where jobs require concurrent service at many servers, occur widely in practice. Much is known in the dropping setting, where jobs are immediately discarde…
Optimal Resource Allocation for Elastic and Inelastic Jobs
Benjamin Berg, Mor Harchol-Balter, Benjamin Moseley +2
Modern data centers are tasked with processing heterogeneous workloads consisting of various classes of jobs. These classes differ in their arrival rates, size distributions, and j…
Optimal Multiserver Scheduling with Unknown Job Sizes in Heavy Traffic
Ziv Scully, Isaac Grosof, Mor Harchol-Balter
We consider scheduling to minimize mean response time of the M/G/k queue with unknown job sizes. In the single-server case, the optimal policy is the Gittins policy, but it is not…
Simple Near-Optimal Scheduling for the M/G/1
Ziv Scully, Mor Harchol-Balter, Alan Scheller-Wolf
We consider the problem of preemptively scheduling jobs to minimize mean response time of an M/G/1 queue. When we know each job's size, the shortest remaining processing time (SRPT…