PaperlayerView exact revision on arXiv

Source-linked AI summary

CASSINI: Network-Aware Job Scheduling in Machine Learning Clusters

Sudarsanan Rajasekaran, Manya Ghobadi, Aditya Akella

arXiv:2308.00852v1cs.NIcs.DCcs.LG

TL;DR

ML schedulers tend to overlook training jobs’ communication patterns when placing workers, even though communication overhead can take a significant share of iteration time. CASSINI combines geometric modeling and an Affinity graph to coordinate time-shifts and interleave jobs sharing links. On a 24-server testbed, it improves average and tail completion times and reduces ECN-marked packets.

  • Problem

    State-of-the-art ML schedulers tend to ignore training jobs’ communication patterns when placing workers on GPUs, despite communication overhead taking a significant portion of iteration time as GPU counts increase.

    Source: §1 · p. 1

  • Method

    CASSINI integrates with existing schedulers, using a geometric compatibility metric and an Affinity graph to find time-shifts that interleave jobs’ communication on shared links.

    Source: §1 · p. 1

  • Results

    CASSINI improves average and tail job completion time by up to 1.6× and 2.5×, respectively, and reduces ECN-marked packets by up to 33×.

    Source: §7 · p. 12

  • Takeaways & Limitations

    CASSINI can augment existing ML schedulers without requiring switch/NIC reservations or priorities or changes to congestion-control protocols.

    Source: §1 · p. 1

    The unified-circle optimization can become non-scalable: using the LCM of many jobs’ iteration times leads to an exponential number of constraints.

    Source: §4.1 · p. 5

Abstract

from arXiv · show

We present CASSINI, a network-aware job scheduler for machine learning (ML) clusters. CASSINI introduces a novel geometric abstraction to consider the communication pattern of different jobs while placing them on network links. To do so, CASSINI uses an affinity graph that finds a series of time-shift values to adjust the communication phases of a subset of jobs, such that the communication patterns of jobs sharing the same network link are interleaved with each other. Experiments with 13 common ML models on a 24-server testbed demonstrate that compared to the state-of-the-art ML schedulers, CASSINI improves the average and tail completion time of jobs by up to 1.6x and 2.5x, respectively. Moreover, we show that CASSINI reduces the number of ECN marked packets in the cluster by up to 33x.

1 Introduction

CASSINI addresses schedulers’ tendency to ignore ML jobs’ communication patterns when placing workers. It combines time-shifting and network-aware placement to improve job completion times and reduce ECN-marked packets.

1 Introduction

  • Existing ML schedulers tend to ignore job communication patterns when placing workers on GPUs, despite communication overhead taking a significant share of training iteration time.The passage attributes this overhead to increasing GPU counts in distributed training studies.Source: §1 · p. 1
  • CASSINI integrates with existing ML schedulers to place jobs on network links while minimizing congestion, without requiring switch/NIC support or congestion-control changes.The stated examples of unnecessary switch/NIC support are reservations and priorities.Source: §1 · p. 1
  • A small time-shift can interleave compatible jobs’ computation and communication patterns, improving training time.CASSINI uses a compatibility metric to guide job placement and competition on network links.Source: §1 · p. 1
  • CASSINI models periodic job communication on circles and rotates them to find time-shifts that maximize interleaving on a link.For cluster-wide placement, an Affinity graph links jobs to traversed links and a graph traversal algorithm finds unique time-shifts that maintain compatibility across links.Source: §1 · p. 1
  • On a 24-server testbed with 13 representative DNN models, CASSINI improves job tail completion time by up to 2.2× versus Themis [35] and 2.5× versus Pollux [45], reducing cluster ECN-marked packets by up to 33×.Source: §1 · p. 1

2 Background and Motivation

Distributed DNN training produces recurring communication phases whose timing and bandwidth depend on parallelization strategy and hyperparameters. The section shows how shifting one job’s start can interleave phases on a shared link, while noting that perfect interleaving is not always possible.

2.1 Distributed DNN Training Traffic Pattern

  • The testbed uses one A100 GPU and a 50 Gbps RDMA NIC per server, with batch sizes chosen for over 80% GPU utilization and enabled intra-job pipelining.CASSINI is designed for large GPU clusters running data-, pipeline-, and/or model-parallel jobs.Source: §2.1 · p. 2
  • Data, pipeline, tensor, and hybrid parallelism produce distinct traffic patterns, from AllReduce and activation peaks to communication during forward and backpropagation.The examples include GPT-1, GPT-2, and GPT-3 jobs with different model and server configurations.Source: §2.1 · p. 2
  • Training iterations repeat their network demand when hyperparameters remain unchanged, and an iteration may contain multiple Up-Down phases whose demand depends on parallelization and hyperparameters.The section describes recurring patterns across common DNN models.Source: §2.1 · p. 2

2.2 Interleaving the Up and Down Phases

  • The section’s goal is to interleave the bandwidth demand of different jobs’ Up and Down phases by exploiting recurring network demand.This motivates shifting job starts when jobs share a link.Source: §2.2 · pp. 2–3
  • A 120-ms shift interleaves two VGG19 jobs’ Up and Down phases, accelerating both jobs’ 90th-percentile tail iteration time by 1.26×.Without the shift, each job receives roughly 22 Gbps; with interleaving, they do not compete during their respective Up phases.Source: §2.2 · p. 3
  • Perfect phase matching is not always possible: BERT and VGG19 have no suitable shift, while shifting VGG16 by 150 ms enables perfect interleaving with WideResNet101.The authors introduce compatibility rank to capture potential interleaving when perfect matching is unavailable.Source: §2.2 · p. 3

3 Geometric Abstraction

CASSINI maps recurring network-demand phases onto circles to reason about how jobs can share a link. It overlays and rotates these representations to assess compatibility, including for jobs with different iteration times and complex parallelism patterns.

3 Geometric Abstraction

  • CASSINI rolls each job’s repeating network-demand trace onto a circle whose perimeter equals its iteration time, aligning recurring Up and Down phases by angle.The representation uses the recurring phases across training iterations to capture the job’s communication pattern.Source: §3 · p. 3
  • For jobs with unequal iteration times, CASSINI uses a unified circle with perimeter equal to their iteration-time LCM; 40- and 60-ms jobs yield 120 units.The example shows three periods of the 40-ms job and two of the 60-ms job on the shared circle.Source: §3 · pp. 3–4, Figure 3 · p. 4
  • The abstraction also represents model-parallel traffic with multiple arcs whose lengths and color intensities encode phase duration and bandwidth demand.The GPT-3 example has six Up-Down phases with different durations and bandwidth demands.Source: §3 · p. 4, Figure 4 · p. 4
  • Overlaying and rotating job circles seeks to minimize average excess bandwidth relative to link capacity, producing a compatibility score and a rotation angle for each job.The score is 1 when excess demand is zero and can become negative for highly incompatible job combinations.Source: §3 · pp. 3–5

4 Augmenting ML schedulers with CASSINI

CASSINI extends link-level compatibility scheduling to cluster placements by reconciling link-specific shifts into one per-job delay. It integrates placement selection and time-shift application into schedulers such as Themis.

4.1 CASSINI Affinity Graph

  • A job traversing multiple links can receive conflicting link-specific shifts, so CASSINI must assign it one delay without compromising compatibility on any link.Figure 5 illustrates the challenge of reconciling the shifts for a job shared across two links.Source: §4.1 · p. 5, Figure 5 · p. 5
  • Expanding link optimization across a cluster is not scalable: an LCM-sized unified circle can require exponentially many constraints.Source: §4.1 · p. 5
  • CASSINI models jobs and shared links as the two vertex sets of a bipartite Affinity graph, with edges indicating which jobs traverse which links.Source: §4.1 · p. 5
  • For loop-free Affinity graphs, graph traversal assigns unique job shifts while maintaining compatibility on all links; Theorem 1 guarantees correctness and uniqueness.The traversal proceeds across each connected subgraph and assigns a job shift when that job is visited.Source: §4.1 · pp. 5–6

4.2 Putting It All Together

  • CASSINI augments Themis by evaluating candidate placements for link compatibility and selecting the top candidate while preserving finish-time fairness.Themis can return candidate placements with the same finish-time fairness but different worker placements; candidates are ranked by average compatibility across their links.Source: §4.2 · pp. 6–7
  • CASSINI discards candidates whose Affinity graphs contain loops, then sends selected job shifts to server agents for application at the next iteration.Agents measure and adjust shift drift; evaluations found adjustments were rare.Source: §4.2 · p. 7

5 Evaluations

CASSINI is evaluated on a 24-server cluster across diverse DNN workloads and traces, with comparisons covering performance, congestion, compatibility, server configurations, and scheduling overhead. Across these settings, the results show improved iteration times and fewer congestion marks, while also examining when compatibility and time-shift precision matter.

5.1 Methodology And Setup

  • The evaluation uses a 24-server A100/RDMA testbed, 13 DNN models, three trace types, and profiled link-utilization patterns.The traces cover Poisson arrivals, dynamic arrivals into an active cluster, and snapshots with all jobs present at experiment start.Source: §5.1 · pp. 7–9

5.2 Performance Gains

  • Figure 9’s iteration-time CDF shows Th+CASSINI improves average and 99th-percentile tail iteration times by 1.4× and 1.5× versus Themis.It achieves similar performance to the Ideal benchmark.Source: Figure 9 · p. 8, §5.2 · p. 9

5.3 CASSINI Reduces Congestion

  • Compared with Themis, Th+CASSINI improves average and 99th-percentile tail iteration times by 1.5× and 2.2×; versus Pollux, Po+CASSINI improves them by 1.6× and 2.5×.The dynamic-trace stress test triggers DLRM and ResNet50 arrivals while other jobs are running.Source: §5.3 · p. 9
  • For DLRM, Themis and Pollux produce 27× and 33× more average ECN marks, respectively, than their CASSINI-augmented counterparts.CASSINI-augmented schedulers maintain fewer ECN marks per iteration across the tested models.Source: §5.3 · p. 9

5.4 Impact of Model Parallelism

  • In model-parallel workloads, Th+CASSINI improves average and 99th-percentile tail iteration times by 1.2× and 1.6×, respectively, versus Themis.Themis places some non-compatible pairs on shared links, while Th+CASSINI places compatible pairs there; similar gains are observed for Pollux and Po+CASSINI.Source: Figure 11 · p. 10, §5.4 · p. 10

5.5 Impact of Partial Compatibility

  • Figure 12’s link-utilization comparison shows that gains begin to diminish at compatibility score 0.6, and CASSINI avoids placing low-score pairs on the same link.High compatibility enables interleaving; strict interleaving is unnecessary when a job’s network demand is not significant.Source: Figure 12 · p. 10, §5.5 · p. 10

5.6 Impact of Multiple GPUs per Server

  • In the two-GPU-per-server experiment, Th+CASSINI improves average and 99th-percentile tail iteration times by 1.4× and 1.9× versus Themis.The example shows CASSINI placing DLRM with compatible ResNet50 rather than non-compatible XLM when each needs three GPUs.Source: Figure 13 · p. 11, §5.6 · p. 11

5.7 Adjusting Time-Shifts and Overhead

  • At 5° angle precision, CASSINI achieves 100% time-shift accuracy with low optimization overhead, while automatic adjustments remain below two per minute.Adjustments are triggered when communication starts deviate by more than five percent of the ideal iteration time.Source: Figure 15 · p. 11, Figure 14 · p. 11, §5.7 · p. 11

6 Related Work

Related schedulers address compute placement, resource sharing, or communication within a job, but the section distinguishes CASSINI by considering network demands across jobs. It also identifies extensions beyond a prior workshop paper’s single-link idea.

Compute scheduling approaches

  • Schedulers such as Themis and Pollux place workers close together to reduce network sharing, but do not account for interleaving communication patterns across jobs.CASSINI complements these approaches by considering compute resources and different jobs’ communication demands, and is designed as a pluggable module.Source: §6 · p. 11

Multi-resource sharing

  • Muri’s interleaving applies only to jobs sharing the same resource group, whereas CASSINI can interleave jobs on different GPUs; Synergy does not treat network bandwidth as a resource.CASSINI is designed to augment both Muri and Synergy.Source: §6 · pp. 11–12

Communication-aware scheduling

  • ByteScheduler, Syndicate, TACCL, BytePS, and CLOPT optimize communication within a job, while CASSINI addresses network sharing across jobs.CASSINI’s approach is described as orthogonal to these within-job techniques.Source: §6 · p. 12

Difference with prior workshop paper

  • Compared with the prior workshop paper, CASSINI adds cluster-level interleaving, model-parallel support, an Affinity graph, and a concrete scheduler without changing or assuming a congestion-control protocol.The workshop paper relied on an unfair congestion-control protocol and addressed compatibility at a single-link level.Source: §6 · p. 12

7 Conclusion

CASSINI is designed to augment existing cluster schedulers with network-aware placement for multiple ML jobs. The evaluations report improved completion times and fewer ECN-marked packets.

7 Conclusion

  • CASSINI integrates with existing cluster schedulers, ranks GPU placements by compatibility, and improves average and tail job completion times by up to 1.6× and 2.5× while reducing ECN-marked packets by up to 33×.The compatibility score ranks placements when jobs compete for network links.Source: §7 · p. 12

A Proof of Theorem 1

Theorem 1 establishes that Algorithm 1 assigns unique time shifts that satisfy the link-level correctness constraints for connected, loop-free Affinity graphs, and extends these guarantees to graphs with multiple disconnected components.

A Proof of Theorem 1

  • For every pair of jobs sharing a link, the assigned time-shift difference equals the relative time-shift in CASSINI’s optimization formulation for that link.The proof checks this constraint for each link, whose geometric abstraction has perimeter p_l.Source: A Proof of Theorem 1 · p. 16
  • BFS visits each job once, so Algorithm 1 computes and assigns exactly one time-shift value to every job.The proof establishes this uniqueness claim by induction alongside correctness.Source: A Proof of Theorem 1 · p. 16
  • The proof establishes correctness and uniqueness for connected, loop-free Affinity graphs, then extends both guarantees to multiple disconnected subgraphs.Each disconnected subgraph is solved separately, with no correctness constraints across subgraphs.Source: A Proof of Theorem 1 · p. 16

B.1 Topology

The testbed uses A100-equipped servers connected through a Tofino switch configured to emulate a 2:1 over-subscribed topology.

B.1 Topology

  • The testbed servers are ASUS ESC4000A-E10 machines, each with one A100 Nvidia GPU and one Mellanox ConnectX5 NIC.The NICs connect to a Tofino switch.Source: §B.1 · p. 17
  • A Tofino switch emulates 13 logical switches for the testbed.Source: §B.1 · p. 17
  • The emulated topology contains 48 bidirectional links and is 2:1 over-subscribed.Source: §B.1 · p. 17

B.2 DNN Models

The evaluation uses 13 popular DNN models, with batch sizes and model sizes adjusted to reflect scheduling conditions and parallelization strategy.

B.2 DNN Models

  • The experiments include 13 DNN models spanning VGG, ResNet, WideResNet, BERT-family models, GPT models, and DLRM.The listed models are VGG11, VGG16, VGG19, ResNet50, WideResNet101, BERT, RoBERTa, XLM, CamemBERT, GPT1, GPT2, GPT3, and DLRM.Source: §B.2 · p. 17
  • Batch sizes are reported as ranges because worker counts and hyperparameters change during scheduling epochs.The experiments select batch sizes according to hyperparameters used in prior work.Source: §B.2 · p. 17
  • Different instances of the same model are distinguished by suffixes, and model sizes are adjusted according to parallelization strategy.For example, GPT2-A and GPT2-B use different batch sizes and hidden sizes.Source: §B.2 · p. 17

C Number of ECN Marked Packets

Figure 19 reports per-iteration ECN-marked packet counts for ResNet and CamemBERT; ResNet generally has fewer marks, consistent with its smaller model size and lower AllReduce bandwidth demand.

C Number of ECN Marked Packets

Loading 2308.00852v1…