Hi there. I am a fifth-year PhD candidate in Computer Science at UNC Chapel Hill, advised by Ben Berg.
I work at the intersection of Queueing Theory and Computer Systems. Namely,
- Multiresource job scheduling
- Scheduling jobs that request resources like (4 CPUs, 8GiBs, 2 GPUs, 10Gbps NIC). Hosts run many jobs in parallel subject to resource limits.
- LLM inference job scheduling
- Resource allocation for inference jobs to improve system throughput and lower latency.
01Research
Our trilogy on throughput-optimal data center scheduling. Animations powered by Claude.
Markovian Service Rate (MSR) Policies
A novel multiresource scheduling policy with response time analysis that supports multiple preemption models.
The problem
A server has 15 CPU cores. Small jobs need 3 cores and large jobs need 5, and a job runs to completion once started. The jobs running together form the server's configuration, written (small, large): (3,1) is three small jobs and one large one. Small jobs arrive twice as often as large ones.
Two policies
MSR Our policy
Alternate between (5,0) and (0,3). Stay in each until a random timer goes off; its mean is precomputed so that, on average, MSR completes jobs faster than they arrive. Then drain the running jobs to make room for the next configuration.
(5,0)→ drain →(0,3)→ drain ↺
First-Fit greedy baseline
Whenever a job arrives or finishes, start any queued job that fits, oldest first. First-Fit is commonly seen data center schedulers.
Arrivals follow the dashed line. MSR's maximum average ◆ lies on the edge, where all 15 cores are busy; the longer its random timers, the less time MSR spends draining and the closer its average gets to this maximum. First-Fit gets stuck in configurations like (3,1), where no waiting job fits even though cores sit idle. The idle cores pull its average ● below the arrivals, so unlike MSR, First-Fit fails to stabilize the system: its queue grows without bound.
The simulation
Below, MSR and First-Fit serve the same jobs. MSR runs with BackFilling: when too few jobs are queued to fill its current configuration, it fills the spare cores with other jobs in First-Fit order.
Quickswap
A novel non-preemptive multiserver scheduling policy that performs well in theory and practice.
The problem
A cluster has 32 servers. Light jobs need one server; heavy jobs need all 32. 90% of jobs are light and none can be paused, so the cluster takes turns: up to 32 light jobs side by side, or one heavy job at a time. Before a heavy job can start, every running light job has to finish.
Two policies
Both serve heavy jobs until none are left, then light jobs. They differ in when they switch back to heavy:
Most Servers First (MSF) state of the art
Once no light jobs remain.
Quickswap (MSFQ) Our policy
Once light jobs drop to a threshold ℓ: stop starting new ones, let the running ones finish, then switch.
MSF
last light job leaves → heavy
Quickswap
light jobs drop to ℓ → drain → heavy
New light jobs keep trickling in, so MSF's wait for zero drags on with most servers idle while heavy jobs pile up. At load 0.8 it lasts about 70 job lengths, with 60-odd heavy jobs waiting by the end; a Quickswap switch takes about 4.
The simulation
Below, MSF and our Quickswap policy serve the same stream of jobs. The strips under the chart record who held the servers, and the ℓ slider moves Quickswap's threshold (ℓ = 0 is MSF).
Scaling Cycles
A novel non-preemptive multiresource scheduling policy that performs optimally in some settings.