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 20 CPU cores and 15 GB of memory. Jobs come in three types, A 3 cores, 7 GB, B 4 cores, 1 GB, and C 10 cores, 1 GB, and run to completion once started. The jobs running together form the server's configuration. Jobs arrive in the ratio A : B : C = 1 : 4 : 2, so near full load the server keeps up only by running A + 4B half the time and 2C the other half.
Two policies
MSR Our policy
Hold one of the two good configurations for a random stretch, then drain: stop replacing finished jobs until the next one fits.
A + 4B→ drain →2C→ drain ↺
First-Fit greedy baseline
Whenever a job arrives or finishes, start any queued job that fits, oldest first.
The two that keep up
A + 4B
2C
Where First-Fit gets stuck
2B + C
A + B + C
First-Fit keeps slipping small B jobs into freed cores, so the 20 free cores that 2C needs rarely appear and the server gets stuck in mixes that serve too little. As a result, First-Fit cannot stabilize the system above load ρ ≈ 0.9: its queue grows without bound. MSR is throughput-optimal, so its queue stays finite at any load below 1.
The simulation
Below, our MSR policy and First-Fit serve the same stream of jobs. The pills above MSR track its place in the cycle, and hatched jobs are backfilled into room MSR reserved but had nothing waiting for. At the default load of 0.98, First-Fit's queue keeps climbing and never comes back down, while MSR's levels off.
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.