- Rating
- 3
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper targets round-based GPU cluster schedulers where a job whose GPU set changes between rounds must be checkpointed and restarted, said to cost 40–60 minutes for LLMs. Tesserae is a scheduler-agnostic post-processing step that relabels GPU IDs in the next round's plan, preserving node structure, to maximize overlap with the current placement via two nested Hungarian assignments. On one simulated 128-GPU trace, Tesserae cuts Tiresias's average job completion time by 1.36× with far fewer migrations.
Critical strengths
- Clean, cheap, scheduler-agnostic formulation. Treating post-scheduling GPU assignment as a node-preserving relabeling solved by two nested assignment problems (Algorithms 2–3) is simple and optimal for its surrogate objective.
- Negligible overhead with a real implementation. The relabeling costs 2.66 s at 1,200 GPUs regardless of queue length (Figure 7), versus ~80 s for Gavel's LP, and is implemented in Blox with a calibrated simulator.
Critical weaknesses
- Sole baseline is no migration policy at all. "Gavel's heuristic migration policy" is an identity GPU-ID mapping on a plan Listing 1 rebuilds from scratch every round; keeping continuing jobs on their current GPUs is equally pluggable yet never compared. Since the original Tiresias and Themis do not re-place running jobs each round, the ~5,500 migrations attributed to Tiresias may be a Blox artifact.
- Evidence for generality is missing from the submission. Sections A, B, D, E and Table 2 are referenced but absent from the PDF, with the ablation, second (Gavel-style) trace and workload table, so the headline numbers rest on one trace at one arrival rate with no error bars.
- Migration cost contradicts the motivation; the JCT gain is unexplained. The introduction motivates with 40–60 minutes per LLM migration, but Figure 1 shows ~38–40 s, which the introduction itself calls negligible; at that cost the ~3,450 migrations removed for Tiresias are worth roughly 35–40 job-hours against an average-JCT reduction summing to ~990 job-hours, a ~25× amplification attributed only qualitatively to lower queueing.
Questions for authors
- Does Blox's placement keep continuing jobs on their current GPUs; if not, how does Tesserae compare with a sticky-placement variant of Listing 1?
- Which per-model migration costs does the simulator charge, and what produces the ~25× gap between removed migration overhead and JCT savings?
3 comments
Thank you for the response! The appendix question is resolved but two points from my review are still open. I am keeping my rating.
Thank you for your follow-up questions. Our responses are below:
-
In our Blox implementation, the placement planner constructs a new plan each round without reserving the GPUs previously assigned to continuing jobs. We agree that a sticky placement policy can preserve the scheduler’s preemption decisions. Our intended point is that strictly retaining the GPU assignments of continuing jobs can prevent the placement of an otherwise feasible set of scheduled jobs.
Consider a cluster with two nodes, each with four GPUs. In the previous round, two continuing one-GPU jobs, J1 and J4, run on different nodes, as shown in (a). In the next round, the scheduler selects J1, J4, and three two-GPU jobs, J7–J9, each of which requires both GPUs to be on the same node. Retaining J1 and J4 on their original GPUs leaves three free GPUs on each node. Each node can therefore accommodate only one two-GPU job, leaving J9 unplaced despite two GPUs remaining free across the cluster, as shown in (b).
A feasible next-round plan places J1, J4, and J7 on one node and J8 and J9 on the other. Tesserae can realize this plan by migrating only J4 while keeping J1 on its original GPU, as shown in (c). A sticky policy can also realize this plan if it allows J4’s reservation to be released.
Placement Node GPU 0 GPU 1 GPU 2 GPU 3 (a) Previous round 0 J1 J2 J2 J3 1 J4 J5 J5 J6 (b) Strict sticky placement 0 J1 J7 J7 Free 1 J4 J8 J8 Free (c) Feasible plan: migrate only J4 0 J1 J4 J7 J7 1 J8 J8 J9 J9 Strictly retaining the GPU assignments of continuing jobs can be incompatible with the scheduling decisions made by Tiresias and Gavel, as it may prevent the placement of an otherwise feasible set of scheduled jobs.
-
Thank you for your question. We detail the simulator’s per-model migration costs and explain how reduced queueing delays amplify the direct savings from avoided migrations, accounting for the approximately 25× gap.
Simulator cost model. When a job starts or restarts, the simulator charges 25 seconds of warmup for ResNet-50, VGG-19, DCGAN, and PointNet, 35 seconds for GPT3-Medium, and 40 seconds for GPT3-XL and GPT3-3B. A job that continues on the same GPUs incurs 5 seconds of warmup per round. The simulator also charges 2 seconds per launch command and 0.5 seconds per running job for metrics collection. The model includes no separate checkpoint save or restore charge.
Effect on queueing. When jobs are launched sequentially, launch overhead extends the current scheduling round. Jobs launched later wait longer to begin execution, while queued or preempted jobs must wait longer for subsequent scheduling opportunities. Reducing the number of launches therefore reduces both immediate launch delays and queueing delays in later rounds. These benefits accumulate across jobs and scheduling rounds, allowing aggregate JCT savings to exceed the time saved directly on restarts.
Sensitivity to launch concurrency. We replayed the 900-job Shockwave trace on 128 GPUs with 360-second rounds and five paired seeds. We held the per-command launch cost and per-model warmup costs fixed and varied the number of launch commands issued concurrently. In the batched configurations, all launch commands in one batch return before the next batch is issued.
Launch configuration Baseline mean JCT (h) Tesserae mean JCT (h) Baseline total queueing time (job-hours) Tesserae total queueing time (job-hours) Sequential 4.126 3.041 2,327.3 1,500.2 Batches of 2 3.538 2.835 1,878.5 1,343.3 Batches of 4 3.227 2.744 1,641.6 1,273.6 Batches of 8 3.032 2.689 1,492.0 1,231.4 Fully concurrent 2.910 2.677 1,401.2 1,223.7 Total queueing time is summed over all 900 jobs in each run and averaged across five seeds. Increasing launch concurrency reduced queueing time for both policies, with a larger reduction for the baseline. With sequential launches, reduced waiting to resume after preemption accounted for 817.9 of the 827.1 job-hours of queueing savings. With fully concurrent launches, the reduction in this resumption waiting time fell to 177.5 job-hours. These differences are measured over complete simulation runs and reflect both the immediate effects of launch overhead and its downstream effects on scheduling decisions.
In simulation, Tesserae achieved a 1.36× mean JCT speedup with sequential launches and a 1.1x mean JCT speedup with fully concurrent launches. The simulator does not model contention among concurrent launches; in our implementation, we observed that high launch concurrency can cause contention and increase launch latency.
Please let us know if you have any further questions. Thank you for your time and feedback.
We appreciate your constructive suggestions. Please find our responses to your questions below:
Weaknesses:
As discussed in the introduction, existing schedulers typically assume negligible preemption and migration costs, limiting the available baselines that explicitly account for these overheads. We welcome suggestions for additional relevant baselines and would be happy to include them in our evaluation.
The appendix is included in the supplementary material, which was submitted separately from the main paper. If needed, we can also upload a single document containing both. See my answer to Question 2.
Questions:
Blox’s placement policy does not preserve the GPU assignments of continuing jobs. We do not compare Tesserae against a sticky-placement variant of Listing 1 because, if preserving these assignments prevents preemption, it can cause blocking similar to that in FIFO scheduling, forcing queued jobs to wait for running jobs to complete and potentially compromising scheduling fairness [1].
First, we would like to clarify that we do not consider an overhead of approximately 38-40 seconds negligible. As discussed in line 38, many existing schedulers treat it as such, whereas our paper emphasizes that this overhead should be accounted for in deep learning scheduling in line 44. Second, regarding the reduction in average JCT, job completion time comprises waiting time, execution time, and overhead, including warmup and checkpoint restoration. As you noted, execution time remains unchanged. Thus, beyond the 35-40 job-hours saved by reducing overhead, the remaining improvement comes from reduced queueing time.
[1] Gu, Juncheng, et al. "Tiresias: A {GPU} cluster manager for distributed deep learning." 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19). 2019.