acceptodds
Under review as a conference paper at ICLR 2027

Tesserae: Scalable Migration Policies for Deep Learning Workloads

Abstract

Training deep learning (DL) models has become a dominant workload in data-centers. Existing schedulers allocate computational resources to running jobs with the goal of optimizing objectives such as makespan, fairness and average job completion time. In addition, they often incorporate placement policies that determine where jobs are assigned within the cluster to improve overall resource utilization. However, as model sizes continue to grow, migration costs have become a major bottleneck for cluster schedulers. Our key insight is that migration problems during scheduling can be formulated as graph-matching problems. Building on this observation, we design novel migration policies that can minimize the number of job migrations during scheduling. We integrate these policies into existing schedulers and demonstrate how our design enables a scalable and efficient GPU cluster scheduler. Experimental results show that Tesserae improves average JCT by up to and reduces the number of migrations by up to compared to existing approaches.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
cluster scheduling, parallelism

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Yx9kOpenReview ↗
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

We appreciate your constructive suggestions. Please find our responses to your questions below:

Weaknesses:

  1. 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.

  2. 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:

  1. 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].

  2. 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.

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:

  1. 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.

    PlacementNodeGPU 0GPU 1GPU 2GPU 3
    (a) Previous round0J1J2J2J3
    1J4J5J5J6
    (b) Strict sticky placement0J1J7J7Free
    1J4J8J8Free
    (c) Feasible plan: migrate only J40J1J4J7J7
    1J8J8J9J9

    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.

  2. 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 configurationBaseline mean JCT (h)Tesserae mean JCT (h)Baseline total queueing time (job-hours)Tesserae total queueing time (job-hours)
    Sequential4.1263.0412,327.31,500.2
    Batches of 23.5382.8351,878.51,343.3
    Batches of 43.2272.7441,641.61,273.6
    Batches of 83.0322.6891,492.01,231.4
    Fully concurrent2.9102.6771,401.21,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.

Reviewer_PFQcOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposed TESSERAE, aiming to reduce the migration cost in GPU cluster scheduling for deep learning tasks. It formulates the migration problem as a graph-matching problem. Instead of actually migrating data, it remaps GPU IDs in different scheduling rounds. The node-level matching has higher priority for time saving. The Hungarian algorithm is applied to solve the migration plan. The experiments were conducted on a 8-node 32-GPU real cluster with a 120-job trace, and a simulated 128-GPU cluster with a 900-job trace. The extensive experiments were conducted to show that TESSERAE can achieve low average job completion time and few migrations.

Critical strengths
  1. As migration has become a major bottleneck with the growing size of deep learning models, it is critical to reduce migration cost for GPU cluster scheduling.
  2. The proposed method can greatly reduce time consumption, and it is compatible with a wide range of existing scheduling policies.
  3. Extensive experiments were conducted for evaluation.
Critical weaknesses
  1. The paper only considers the situation where a GPU holds at most two jobs, and the job size in the algorithm is only related to the number of GPUs occupied. More factors, such as memory size, should be considered.

  2. The experimental setup uses only one job generation setting, i.e., the probabilities of Small, Medium, Large, and Extra Large jobs are 0.72, 0.2, 0.05, and 0.03. More job generation probability settings and job arrival rates should be evaluated.

  3. The fidelity of the simulator is only verified on a relatively small cluster, which cannot ensure its fidelity on larger clusters. The experiments on larger clusters are expected.

  4. In the compatibility experiments, Gavel-FTF+TESSERAE is only evaluated in terms of fairness but not performance, and the fairness experiments are only conducted with Gavel-FTF.

Questions for authors
  1. Consider more information beyond the number of GPUs occupied, such as memory size, and situations where a GPU holds more than two jobs.

  2. Please verify the fidelity of the simulator on a larger cluster, or provide further explanation of its fidelity in large-cluster situations.

  3. Please evaluate different job generation probability settings and job arrival rates.

1 comment

We appreciate your thoughtful comments and provide our responses below.

Weaknesses:

  1. During offline profiling, we account for GPU memory constraints. If packing two jobs on the same GPU causes an out-of-memory error, we exclude that job pair from packing.

  2. Appendix D of the supplementary material reports results on a trace generated by Gavel’s trace generator. The table below reproduces the average JCTs (in hours).

    MethodTiresiasGavel
    Heuristic43.5832.84
    Tesserae37.3229.46
  3. Our simulator validation follows established practice in prior work: Gavel [1] and Sia [2] validated their simulators on clusters of 36 and 44 GPUs, respectively. While resource constraints limit our ability to validate at a larger scale, our validation scale is consistent with these studies.

Questions:

  1. Our evaluation uses only A100 GPUs with 40 GB of memory, so differences in GPU memory capacity do not arise in our setting. We leave the evaluation of heterogeneous GPU configurations to future work. Following Gavel [1], we restrict job packing to at most two jobs on the same set of GPUs and do not evaluate configurations with more than two colocated jobs. Our migration framework can also accommodate more than two jobs sharing the same set of GPUs. Given fixed packing groups, the framework remaps GPU assignments based on the jobs assigned to each GPU, regardless of how many jobs share those GPUs.

  2. Our simulator validation follows established practice in prior work: Gavel [1] and Sia [2] validated their simulators on clusters of 36 and 44 GPUs, respectively. While resource constraints limit our ability to validate at a larger scale, our validation scale is consistent with these studies.

  3. We use our simulator to evaluate the effects of job arrival rates and job generation probabilities, using the same experimental setup as in the paper: 900 jobs and 128 GPUs.

    First, we vary the job arrival rate using the workload from Figure 5 of the paper. The table below reports the average job completion time (JCT) in hours for each arrival rate. Tesserae consistently outperforms the heuristic across all evaluated arrival rates, reducing average JCT by up to 36.9%.

    Job Arrival rate406080100120
    Heuristic1.522.254.135.186.02
    Tesserae1.371.423.054.285.13

    Second, we vary the probabilities of generating jobs that require 1, 2, 4, and 8 GPUs. In the paper, these probabilities are set to 0.6, 0.3, 0.09, and 0.01, respectively, matching those used in Shockwave. The table below reports the average JCT for each probability distribution. The probabilities in each column correspond to 1-GPU, 2-GPU, 4-GPU, and 8-GPU jobs, respectively. Tesserae consistently outperforms the heuristic, achieving JCT speedups of 1.10x-1.50x across all evaluated distributions.

    Job Generation Probability0.6/0.3/0.09/0.010.75/0.2/0.04/0.010.45/0.40/0.13/0.020.25/0.40/0.25/0.100.25/0.25/0.25/0.25
    Heuristic4.133.265.519.0712.15
    Tesserae3.052.174.488.1411.07

[1] Narayanan, Deepak, et al. "{Heterogeneity-Aware} cluster scheduling policies for deep learning workloads." 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 2020. [2] Jayaram Subramanya, Suhas, et al. "Sia: Heterogeneity-aware, goodput-optimized ML-cluster scheduling." Proceedings of the 29th Symposium on Operating Systems Principles. 2023.

Reviewer_2qSrOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses redundant job migration in round-based GPU cluster scheduling. Even when resource requirements and placement structures are similar across consecutive rounds, unnecessary changes in GPU locality can trigger checkpointing, restoration, and startup overhead. To address this problem, Tesserae first solves a GPU-level weighted bipartite matching problem for each node pair, then a second matching problem across nodes, using the Hungarian algorithm at both levels. Edge costs reflect differences in job membership and are normalized by each job's GPU count. Node-level remapping preserves within-node consolidation. Experiments are conducted on 32 A100 GPUs, simulations scale to 128 GPUs and 900 jobs.

Critical strengths
  1. Eliminating redundant migrations after scheduling and placement avoids redesigning each scheduler's priorities or objective. This modular contribution is attractive for integration into existing cluster schedulers.
Critical weaknesses
  1. Expensive checkpointing and restart of large models motivate the paper, and §4 states that migration times are profiled for each job. However, the algorithm's cost depends on GPU count rather than those times. Avoiding more cheap migrations need not be preferable to avoiding one expensive migration. The gap between the objective and migration-cost awareness calls for total downtime, wasted GPU time, and a baseline weighted by measured migration duration.
  2. The largest Transformer model listed in the main text is GPT3-3B; by default, 90% of jobs use one or two GPUs and only 1% use eight GPUs. This does not establish effectiveness for large, multinode jobs with varied TP/PP layouts and long checkpoint times.
Questions for authors
  1. Does Algorithm 3 minimize normalized GPU-set differences or the job migration count in Definition 1? Under what assumptions are these equivalent? If they are not, can you quantify the gap against an exact integer program or exhaustive optimum?
  2. Why are profiled checkpoint, restore, and warmup times not included in the weights? How do total downtime, wasted GPU time, and JCT compare with a time-weighted formulation?
  3. For TP/PP jobs, how does remapping preserve logical ranks, model shards, and communication topology?
1 comment

Thank you for your thoughtful and constructive feedback.

Weaknesses:

  1. In this paper, our objective is to minimize the number of migrations rather than the total migration overhead. We agree that avoiding several inexpensive migrations may be less beneficial than avoiding a single expensive one. Our framework can readily incorporate migration costs, such as checkpointing and restart overhead or measured migration duration, into the edge weights of the migration graph. Specifically, each job’s contribution to an edge weight can be scaled by its migration cost, allowing the same graph-matching framework to account for differences in migration overhead.
  2. Due to limited resources, we conducted smaller-scale experiments to demonstrate the benefits of our approach. Scaling up to larger models and clusters is an exciting direction for future work.

Questions:

  1. Yes, Algorithm 3 seeks to minimize the number of job migrations as defined in Definition 1, but it does not always achieve the global optimum. Consider four jobs, A, B, C, and D, each requiring two GPUs. In round ii, A and B are placed on Node 0, while C and D are placed on Node 1. Suppose the next plan groups A with C and B with D. Our algorithm first performs job matching within each node and then performs node matching across the cluster. Given these groupings, it incurs two job migrations. However, if these groupings are not required by the plan’s constraints, retaining the original placement satisfies the same resource requirements with zero migrations.

  2. Our framework supports incorporating profiled checkpoint, restore, and warmup times into the graph’s edge weights. The original formulation uses migration count as a simplified proxy for migration cost. To evaluate the impact of time-weighted costs, we use the Shockwave trace from the paper and incorporate warmup and launch overheads into the graph’s edge weights. The resulting average JCTs (in hours) are:

    WorkloadsHeuristicTesserae (norm)Tesserae (time-weighted)
    Shockwave4.133.053.04

    These results show that Tesserae’s graph formulation can directly incorporate such measured costs as edge weights without changing the matching framework.

  3. For TP/PP jobs, remapping only changes the GPU ID mapping without restarting jobs, thereby preserving logical ranks and model shards. We do not explicitly account for communication topology, as GPU clusters on AWS and GCP generally have symmetric communication topologies. Our experiments similarly use 32 GPUs across eight nodes on NERSC’s Perlmutter system with a symmetric topology.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.