Architecture & Measurement-Design Analysis

Crux: GPU-Efficient Communication Scheduling for Deep Learning Training

Source: Cao, J.; Guan, Y.; Qian, K.; Gao, J.; Xiao, W.; Dong, J.; Fu, B.; Cai, D.; Zhai, E. ACM SIGCOMM 2024, August 4-8, Sydney, NSW, Australia, 15 pages. DOI: 10.1145/3651890.3672239 Trace dataset (released): https://github.com/alibaba/alibaba-lingjun-dataset-2023 Authors: Alibaba Cloud (Cao and Guan contributed equally; Zhai is corresponding author). Reader: Direct PDF read via PyMuPDF (gemini-reader free-tier quota exhausted; codex-reader skipped to save tokens; full text extracted to /tmp/crux_full.txt). Analyst: Vishwakarma Date: 2026-05-04

Table of Contents

1. Evaluation Harness Architecture (the "instrument")
2. System-Under-Test Architecture (the "specimen")
3. Design-Space Diagram (axes swept; axes held fixed)
4. The GPU-Intensity Reduction — Survey's Central Theorem as a Diagram
5. Algorithm / Control Flow Diagrams (path selection, priority assignment, priority compression)
6. Crux Implementation Architecture (CoCoLib + Daemon + Transport)
7. Quantitative Results — Empirical Findings by Regime
8. Configuration-Regime Trade-off Tables
9. Bottlenecks & Insights Surfaced by the Measurements
10. Limitations of the Methodology
11. Analogy

1. Evaluation Harness Architecture (the "instrument")

The harness is a two-tier comparator: a 96-GPU physical testbed for end-to-end measurements with real PyTorch / TensorFlow / X-DeepLearning workloads, and a custom packet-and-flow simulator driven by an open production trace (2,000+ GPUs, 5,000+ jobs, two weeks from Alibaba's Lingjun cluster, August 2023). Crux is unusual among collective-communication papers in that the SUT is the cluster scheduler itself — Crux observes inter-job contention and rewires path/priority decisions, not collective algorithm shape. The harness therefore times cluster-wide GPU utilization and per-job JCT, never per-collective latency. Microbenchmark validation (Section 4.4) is run separately on a 1,500-case enumeration simulator that exhaustively computes the global optimum for small instances (≤20 hosts, 5 jobs, 3 priority levels) so each Crux sub-algorithm can be scored against ground truth.

+--------------------------------------------------------------------+
|                  Crux Measurement Harness                          |
|                                                                    |
|  +---------------------+    +-----------------------------------+  |
|  | Workload Driver     |--->| Model Bag (11 models)             |  |
|  | (multi-tenant       |    |  GPT-3 variant (24 layers, h=1024)|  |
|  |  co-execution; ALL  |    |  BERT, ResNet, NMT, Multi-Interest|  |
|  |  jobs run together  |    |  + 5 variants                     |  |
|  |  in shared cluster) |    |  + 2 in-house (CTR, NLP)          |  |
|  +---------+-----------+    +-----------------+-----------------+  |
|            |                                  |                    |
|            v                                  v                    |
|  +--------------------------------------------------------------+  |
|  |     Scheduler-Switch Layer (5 inter-job baselines + Crux)    |  |
|  |                                                              |  |
|  |   General coflow:    Sincronia                               |  |
|  |   Intra-job:         TACCL* (adapted to inter-job by authors)|  |
|  |   Inter-job time:    CASSINI                                 |  |
|  |   Crux ablations:    Crux-PA, Crux-PS-PA, Crux-full          |  |
|  +--------------------------------------------------------------+  |
|            |                                                        |
|            v                                                        |
|  +--------------------------------------------------------------+  |
|  |     Two-Tier Evaluation Bus                                  |  |
|  |                                                              |  |
|  |   TIER A: Real testbed (96 A100 GPUs, 12 hosts, RoCEv2)      |  |
|  |     - co-locate {GPT, BERT, ResNet} mixes                    |  |
|  |     - measure cluster GPU utilization + per-job JCT          |  |
|  |                                                              |  |
|  |   TIER B: Trace-driven simulator                             |  |
|  |     - replays 2 weeks of Lingjun production trace            |  |
|  |     - computation: per-iteration time obtained on real GPUs  |  |
|  |     - communication: alpha-beta model                        |  |
|  |     - 8 priority levels                                      |  |
|  |     - two topologies: two-layer Clos / three-layer double    |  |
|  |                                                              |  |
|  |   TIER C (validation only): 1,500-case enumerator            |  |
|  |     - <=20 hosts, <=5 jobs, 3 priority levels                 |  |
|  |     - global optimum by exhaustive search                    |  |
|  |     - ablates each Crux sub-algorithm in isolation           |  |
|  +--------------------------------------------------------------+  |
|            |                                                        |
|            v                                                        |
|  +--------------------------------------------------------------+  |
|  |     Result Aggregator                                        |  |
|  |                                                              |  |
|  |     - Cluster GPU utilization (the headline metric)          |  |
|  |     - Per-job JCT (normalized vs standalone "Ideal")         |  |
|  |     - Real-time GPU-intensity heatmap of network links       |  |
|  |       (Figure 24: dark = high-intensity job traffic)          |  |
|  +--------------------------------------------------------------+  |
+--------------------------------------------------------------------+
^ Fig 1: Crux harness — three measurement tiers stacked. Tier A is
  the headline (96-GPU real testbed); Tier B scales the claim
  (2,000+ GPU trace replay); Tier C grounds the claim against
  exact optima (small-case enumeration).

Two harness choices stand out. First, the metric is cluster GPU utilization, not single-job throughput — Crux explicitly chooses unfairness as a side effect of utilization optimization, prioritizing GPU-intensive jobs at the cost of low-intensity ones. The harness is therefore engineered to surface that exact trade-off: every comparison plot shows both cluster utilization and a per-job JCT bar, so reviewers can see the cost paid. Second, the harness uses three different "scales of truth" — a small-case enumerator for algorithmic optimality, a real testbed for production realism, and a 2,000-GPU trace replay to scale the claim — and reports each independently. This is the same triangulation pattern used in NCCL-X and HPCC, but applied to scheduler design rather than collective design.

Methodology specifics extracted from Sections 4.4, 5, and 6.1:

The absence of per-collective NCCL telemetry is deliberate: Crux operates on the flow layer (UDP source ports, RoCEv2 DSCP queues), not inside NCCL. The harness therefore has no view into algorithm/protocol/nChannels — and conversely, those knobs cannot affect the metric Crux is optimizing for, because Crux's lever (path + priority) is upstream of NCCL's lever (collective implementation).

2. System-Under-Test Architecture (the "specimen")

The SUT is a multi-tenant production GPU training cluster with a three-tier physical hierarchy: storage / hosts / network. Hosts hold 8 GPUs each over PCIe and NVLink, NICs sit on PCIe and connect into a multi-layer Clos network. Crux runs as a per-host control plane (Crux Daemon, CD) plus per-host data plane (Crux Transport, CT), driving every active DLT job's path and priority decisions through standard ECMP (UDP source-port hashing) and DSCP queue mappings.

+----------- Production Cluster (illustrative): 12 hosts, 96 GPU ----+
|                                                                    |
|                     [ Aggr1 ] ... [ Aggr8 ]    8 Aggr switches     |
|                       /\            /\                             |
|                      /  \          /  \         (2x100 Gbps each   |
|                     /    \        /    \         to ToR layer)     |
|                  [ ToR1 ] ... [ ToR6 ]          6 ToR switches     |
|                    | |  |       | |  |                             |
|                    | |  +-------+ |  |          (8x100 Gbps each   |
|                    | |            |  |           to host layer)     |
|                  +---+----+    +--+--+---+                         |
|                  | Host 1 |...| Host 12 |     12 hosts             |
|                  +---+----+    +---------+                          |
|                      |                                              |
|         +------------+------------------+                           |
|         |                               |                           |
|     +---+---+  +-------+ +-------+ +-------+                       |
|     |  CPU  |  |  NIC  | |  NIC  | |  NIC  |   4x 200 Gbps NICs    |
|     +---+---+  +---+---+ +---+---+ +---+---+                       |
|         |          |         |         |       PCIe 4.0 x16 fabric |
|     +---+----------+---------+---------+---+                       |
|     |        PCIe Switch / Root Complex      |                     |
|     +---+----+----+----+----+----+----+----+---+                  |
|         |    |    |    |    |    |    |    |                       |
|       +-+--+-+--+-+--+-+--+-+--+-+--+-+--+-+--+                    |
|       |G0 |G1 |G2 |G3 |G4 |G5 |G6 |G7 |     8x A100 GPUs           |
|       +---+---+---+---+---+---+---+---+                            |
|         \                                 /                         |
|          +-- NVLink mesh (intra-host) -- +                          |
|                                                                     |
|     Note: every TWO GPUs share one NIC link via PCIe                |
|     (G0&G1 -> NIC0, G2&G3 -> NIC1, etc.)                            |
+---------------------------------------------------------------------+
^ Fig 2: SUT — 96-GPU testbed. The *dual* PCIe contention surface
  (intra-host: GPU pairs share a NIC) and *multi-path* network
  (each host has 4 NICs into a 2-layer Clos) is precisely why
  inter-job contention has TWO geometries to attack: PCIe links
  between GPUs in the same host (Fig. 3b in the paper) and Clos
  paths between switches (Fig. 3a in the paper).

The architectural property that drives the entire paper is shared-bottleneck multi-tenancy: when two jobs land on the same physical link (PCIe or inter-switch), they collide because ECMP's 5-tuple hash cannot distinguish their flows by importance. Without Crux, the only mitigation is luck — different jobs happening to hash to different ports. With Crux, the hash is replaced by a deliberate UDP-source-port choice (driven by ibv_modify_qp on the RoCEv2 QP), and the queue is replaced by a deliberate DSCP class. The hardware does the same forwarding; what changes is which queue and which path each flow lands in.

+-------------- Two Geometries of Inter-Job Contention --------------+
|                                                                    |
|  GEOMETRY A: Network-path contention                               |
|                                                                    |
|              [ ToR1 ]----link----[ Aggr1 ]                         |
|                |                                                    |
|             contention!  (Job 1 + Job 2 both hash here via ECMP)   |
|                |                                                    |
|         +------+------+                                             |
|         | host of J1  |                                             |
|         | host of J2  |                                             |
|         +-------------+                                             |
|                                                                     |
|  GEOMETRY B: Intra-host PCIe / NVLink contention                   |
|                                                                     |
|         +-------------------+                                       |
|         |   Host with J1+J2+J3  |                                  |
|         |                   |                                       |
|         |   GPU-GPU NVLink (J1)                                    |
|         |   PCIe x16 link  (J2 + J3 share)  <- contention!         |
|         |                                                           |
|         +-------------------+                                       |
+--------------------------------------------------------------------+
^ Fig 3: The two geometries Crux schedules around. Most contention
  in production is geometry A (ECMP hash collision in the Clos);
  geometry B arises from job-scheduler fragmentation when one job
  occupies only part of a host.

In the 2-week production trace, 36.3% of jobs (occupying 51% of GPUs) experienced contention at some point — the majority on inter-host network paths (geometry A), a minority on intra-host PCIe links (geometry B). A representative 64-GPU GPT job co-located with a 16-GPU BERT job suffered an 11.0% iteration-time inflation (1.53s -> 1.70s) and a 9.5% cluster GPU-utilization drop, simply from hash collisions on ToR-Aggr links.

3. Design-Space Diagram (axes swept; axes held fixed)

Crux's evaluation forms a 5-dimensional sweep. For each cell, the metric is cluster-wide GPU utilization plus per-job JCT.

                   DESIGN SPACE (5 axes + held-fixed)
  +----------------------------------------------------------------+
  |                                                                |
  |  Axis 1: SCHEDULER (6 levels)                                  |
  |    {Sincronia, TACCL*, CASSINI,                                |
  |     Crux-PA, Crux-PS-PA, Crux-full}                            |
  |                                                                |
  |  Axis 2: TOPOLOGY (3 levels in evaluation)                     |
  |    {Real testbed (12-host 2-layer Clos),                       |
  |     Sim two-layer Clos (173 ToR + 16 Aggr),                    |
  |     Sim double-sided (6 ToR + 12 Aggr + 32 Core)}              |
  |                                                                |
  |  Axis 3: WORKLOAD MIX (multiple compositions)                  |
  |    Production trace replay (5,000+ jobs)                       |
  |    Synthetic mixes:                                            |
  |      n*BERT-8GPU + GPT-32GPU  (n in {2,3,4})                   |
  |      2*ResNet-8GPU + 2*BERT-16GPU + GPT-48GPU                  |
  |      n*ResNet-4GPU + BERT-16GPU  (n in {1,2,3})  [PCIe case]   |
  |      ResNet-8GPU + BERT-nGPU  (n in {8,16,24})    [PCIe case]  |
  |                                                                |
  |  Axis 4: CONTENTION GEOMETRY (2 levels)                        |
  |    {Network-path contention, PCIe contention}                  |
  |                                                                |
  |  Axis 5: JOB SCHEDULER LAYER (3 levels for §6.4)               |
  |    {None, Muri, HiveD}  (composable with Crux)                 |
  |                                                                |
  |  Held FIXED:                                                   |
  |    - Number of priority levels = 8 (commodity NIC/switch limit)|
  |    - Communication library: CoCoLib (Crux's own)               |
  |    - Transport: RoCEv2                                         |
  |    - GPU: A100 (in real testbed); not varied in sim            |
  |    - Path-selection refresh granularity: per job arrival/exit  |
  |    - Profiling window (W_j, t_j measurement): 30 s             |
  |    - Reference-job selection: most-network-traffic job         |
  |    - NCCL knobs (algo, proto, nChannels, numThreads, chunk):   |
  |      not swept; not exposed; orthogonal to Crux's lever         |
  |    - Storage / dataloader traffic: assumed isolated by         |
  |      compute/storage separation (production architecture)      |
  +----------------------------------------------------------------+
^ Fig 4: 5-axis design space. The held-fixed line surfaces the
  scope: Crux operates on path + priority (the FLOW layer); NCCL's
  internal collective knobs are explicitly outside its scope. The
  scheduler axis sweeps Crux against three orthogonal baselines
  representing the three communication-scheduler families
  (general coflow, intra-job, inter-job).

Two absences define the methodological scope. First, Crux holds NCCL's internal configuration constant — the comparison is between flow-level scheduling strategies, not collective-level implementations. This is why TACCL (the closest "intra-job collective synthesizer" baseline) had to be adapted by the authors into TACCL*, an inter-job variant, before it could be benchmarked at all: TACCL synthesizes per-collective routing within a single job; Crux schedules across many jobs. The two operate on different axes. Second, storage / dataloader traffic is assumed isolated via the production compute/storage separation architecture; Crux explicitly does not model checkpointing or dataset-loading bursts. This is acknowledged in Section 7.1 as a limitation of the t_j measurement.

4. The GPU-Intensity Reduction — Survey's Central Theorem as a Diagram

The intellectual core of Crux is Theorem 1 (Section 3.2): in the limit, maximizing cluster GPU utilization U_T over time period T reduces to maximizing the cumulative GPU-intensity F_T of jobs whose flows are transmitted on each link. This converts an NP-Complete max-multi-commodity-flow problem with weighted-utilization objective into a per-link greedy on a single scalar — GPU intensity I_j = W_j / t_j.

+-------------------------------------------------------------------+
|         The GPU-Intensity Reduction Pipeline                      |
|                                                                   |
|   Original goal:          Maximize U_T                            |
|                           (sum of computation done on all GPUs    |
|                            over time period T)                    |
|                                                                   |
|              |                                                     |
|              v   Theorem 1 (Appendix A): lim |T|->inf F_T/U_T = 1 |
|              v                                                     |
|                                                                    |
|   Reduced goal:           Maximize F_T                             |
|                           = sum over links e of                    |
|                             (integral over T of f_e(t) dt)         |
|                           where f_e(t) = I_h(t) if link e is busy  |
|                                                                    |
|              |                                                     |
|              v   Equivalence via bottleneck-link argument         |
|              v   (other links treated as infinite bandwidth)      |
|                                                                    |
|   Operational rule:       For each link e, prioritize the         |
|                           job with the highest GPU intensity.     |
|                                                                    |
|              |                                                     |
|              v   GPU intensity I_j = W_j / t_j                    |
|              v                                                     |
|                                                                    |
|   Practical algo:         (1) Path selection: route GPU-intensive |
|                               jobs onto distinct paths             |
|                           (2) Priority assignment: high priority  |
|                               to high-intensity jobs               |
|                           (3) Priority compression: map N         |
|                               unique priorities to K (=8) levels  |
|                                                                    |
+-------------------------------------------------------------------+
^ Fig 5: The reduction pipeline. The fact that an NPC objective
  collapses to a scalar greedy on each link (in the limit) is the
  paper's load-bearing claim — every Crux algorithm in Section 4
  is engineering around this single reduction.

The diagrammatic interpretation of GPU intensity (paper's Fig. 9) is also a useful way to read F_T. Each running job is drawn as a rectangle whose width is its flow transmission duration and whose height is its GPU intensity I_j. The area under the highest-intensity rectangle that "owns" each link at each instant is F_T. Maximizing F_T is therefore identical to packing the tallest rectangles onto each link's timeline — which is exactly what priority assignment achieves. The reference job (the one generating the most network traffic) anchors the absolute scale of priorities; correction factors k_j adjust other jobs' priorities for differences in iteration length and overlap behavior (Examples 1 and 2 in Section 4.2).

                f(t) = I_h(t)
                  ^
                  |
        I_1  +----+---+      +----+
                  |   |      |    |     job 1 (highest intensity)
        I_2  +----+   +------+    +----+
                                       |  job 2 (medium intensity)
        I_3  +----+                    +----+
                                              | job 3 (low intensity)
              0   +----+----+----+----+----+--+--->  t
                                                          T

   F_T = (area under f(t)) = sum of I_j * (time job j held link e0)
^ Fig 6: F_T as the area packed by the link's owners over time.
  Crux chooses h(t) — i.e., which job's flow is on the link at
  each instant — by maximizing the height (intensity) at every t.

5. Algorithm / Control Flow Diagrams

Crux's design (Section 4) decomposes into three sub-algorithms operating in sequence: (1) GPU-intensity-based path selection, (2) priority assignment with DLT correction factors, and (3) priority compression onto 8 hardware levels.

5.1 Crux's End-to-End Scheduling Pipeline

   START (new job arrives, OR existing job completes/rescales)
       |
       v
  (1) PROFILING (only for new job)
        - assign new job a unique highest priority temporarily
        - measure W_j (GPU work per iter) over 30 s window
        - measure t_j (max link traversal time per iter) via NIC/PCIe
          hardware monitoring
        - apply Fourier transform on traffic time-series to recover
          iteration period
       |
       v
  (2) PATH PROBING (only for new job)
        - for each (src host, dst host) pair, send INT-instrumented
          probing packets with varying UDP source port
        - record per-hop info; build candidate-path table for each
          job's communication pattern
       |
       v
  (3) RECOMPUTE I_j FOR ALL JOBS
        - new I_j = W_j / t_j  (Eq. 2)
        - rank all active jobs by I_j (descending)
       |
       v
  (4) PATH SELECTION (Section 4.1)
        - for each job j, in DECREASING order of I_j:
            -- enumerate all candidate paths
            -- pick the LEAST-CONGESTED path given paths already
               assigned to earlier (higher-I_j) jobs
        - high-intensity jobs separated onto distinct paths;
          low-intensity jobs may collide (lower regret)
       |
       v
  (5) PRIORITY ASSIGNMENT (Section 4.2)
        - select reference job j* = argmax_j(network traffic)
        - set k_{j*} = 1
        - for every other job j, compute correction factor k_j by
          comparing iteration time and overlap pattern with j*
            -- Example 1: shorter-iter job gets higher k
            -- Example 2: less-overlap job gets higher k
        - assign P_j = k_j * I_j  (Eq. 3)
        - sort P_j to give each job a UNIQUE priority rank
       |
       v
  (6) PRIORITY COMPRESSION (Section 4.3)
        - build Communication-Contention DAG D = (V_D, E_D):
            -- V_D = jobs
            -- E_D = (j1->j2) iff jobs share a network link AND
                    P_j1 > P_j2; weight w_{j1,j2} = I_{j1}
        - compute approximate Max K-Cut of D via dynamic programming
          over m=10 random topological orders (Algorithm 1)
        - map K subsets to K=8 hardware priority levels
       |
       v
  (7) DEPLOY DECISIONS via Crux Transport (CT)
        - ibv_modify_qp on each RoCEv2 QP to set:
            -- UDP source port (path)
            -- IP traffic class (DSCP -> NIC/switch queue)
        - intra-host: CD maintains semaphores per PCIe link to block
          lower-priority traffic when high-priority job is using it
       |
       v
  (8) WAIT for next job event (arrival or completion)
       Total recompute budget: <1 minute per event
       |
       +------> back to (1)
^ Fig 7: Crux's scheduling control flow. Steps (1)-(2) run only
  for new jobs; steps (3)-(7) run on every job event.

5.2 Path Selection (Algorithm sketch, Section 4.1)

  function PATH_SELECT(jobs, topology):
      sort jobs by I_j DESCENDING                # high intensity first
      assigned_paths = {}
      link_load = empty
      for j in jobs:                             # greedy, one-pass
          best_path = argmin over candidate_paths(j) of
                       max_e_in_path(link_load[e])
          assigned_paths[j] = best_path
          for e in best_path:
              link_load[e] += traffic_share(j, e)
      return assigned_paths
^ Fig 8: Path selection — greedy least-congested-path, jobs
  considered in I_j order. The geometric effect: high-intensity
  jobs reserve uncongested paths; low-intensity jobs may share.

5.3 Priority Compression as Max-K-Cut on a DAG (Section 4.3)

  Communication-Contention DAG D:
       node     = job
       edge j1->j2 = j1 and j2 share at least one network link AND
                     P_j1 > P_j2 (assigned priority rank from §4.2)
       weight w(j1,j2) = I_{j1}    # GPU-utilization loss if j1 and
                                    # j2 land in the same K-level
                                    # (since j1 loses; without same-
                                    # level collision, only j2 loses)

  Goal: K-partition V_D into V_1 > V_2 > ... > V_K such that no
        edge goes from V_i to V_j with i < j (priority-monotone),
        AND total weight of CUT edges (edges across partitions)
        is MAXIMIZED.

  This is Max-K-Cut on a DAG -- intractable in general, but:
       - A topological order {a_1, ..., a_n} of D induces an
         "interval cut" {a_1..a_{i_1}}, ..., {a_{i_{K-1}}+1..a_n}
       - Max-K-Cut on the SEQUENCE is solvable in O(n^2) via:
           f(i,k) = max_{1 <= j < i}  f(j, k-1) + C_{j,i}
         where C_{j,i} = sum of edge weights from {a_1..a_j} to
                         {a_{j+1}..a_i} in the original DAG
       - Quadrangle Inequality lets the inner max collapse to O(1),
         giving O(n^2) total per topological order
       - Approximate the global optimum by sampling m=10 random
         topological orders (BFS-based) and taking the best cut
^ Fig 9: Crux's priority-compression formulation. The Max-K-Cut
  on DAG -> Max-K-Cut on a topological-order sequence reduction
  is the algorithmic move that makes 5,000-job priority
  compression tractable in seconds.

5.4 Algorithm 1 (Priority Compression — verbatim from paper)

Algorithm 1: Priority Compression
  Input:  D = <V_D, E_D>  (Communication Contention DAG)
  Output: OutputCut       (a K-Cut for DAG D)

  for cases <- 1 to m:                                 # m = 10
      {a_1, a_2, ..., a_n} = RandomTopoOrder(D)        # BFS-based

      # --- preprocess matrix C ---
      for i <- 1 to n:
          for k <- 1 to K:
              S[i,k] <- S[i-1,k] + S[i,k-1]
                         - S[i-1,k-1] + w(a_i, a_k)
      for i <- 1 to n:
          for j <- i+1 to n:
              C[i,j] <- S[i,j] - S[i,i]

      # --- compute f(n, K) by DP ---
      for i <- 1 to n:
          for k <- 1 to K:
              f(i,k) <- max over  g(i-1,k) <= j < i  of
                        f(j, k-1) + C[j,i]
              g(i,k) <- argmax (same)
              Cut(i,k) <- Cut(g(i,k), k-1)
                          U {a_{g(i,k)+1}, ..., a_i}

      if f(n, K) > MaxCut:
          MaxCut    <- f(n, K)
          OutputCut <- Cut(n, K)

  return OutputCut
^ Fig 10: Crux's priority-compression algorithm verbatim.

The g(i,k) trick is the quadrangle-inequality optimization referenced in the paper; it lets the inner max range monotonically with i, reducing each (i,k) state from O(n) to O(1) work.

6. Crux Implementation Architecture (CoCoLib + Daemon + Transport)

The deployable Crux is a software stack inserted between the DLT framework and the transport layer, replacing standard NCCL/Gloo/MPI calls with the Converged Communication Library (CoCoLib).

+--------------------------------------------------------------------+
|  DLT Frameworks                                                    |
|  +------------+  +-------------+  +-------------------+            |
|  |  PyTorch   |  | TensorFlow  |  |  X-DeepLearning   |            |
|  +------+-----+  +------+------+  +-----------+-------+            |
|         \              |              /                            |
|          v             v             v                              |
|  +--------------------------------------------------------------+  |
|  |  Converged Communication Library (CoCoLib)                  |  |
|  |  AllReduce | AllToAll | AllGather | Send/Recv               |  |
|  |  (drop-in collectives)                                       |  |
|  +-------------------------------+------------------------------+  |
|                                  |                                  |
|       +--------------------------+----------------+                 |
|       |                                           |                 |
|       v                                           v                 |
|  +-------------------+                     +---------------------+  |
|  |  Crux Daemon (CD) |  <----- shared ---> |  Crux Transport(CT) |  |
|  |  per-host process |  memory             |  per-job library    |  |
|  |                   |                     |                     |  |
|  | - collect topo +  |                     | - executes path/    |  |
|  |   job info        |                     |   priority decisions|  |
|  | - compute I_j,k_j |                     | - calls             |  |
|  | - run §4.1-4.3    |                     |   ibv_modify_qp     |  |
|  | - leader-CD only  |                     |   to set UDP src    |  |
|  |   makes decisions |                     |   port + IP TC      |  |
|  +---------+---------+                     +----------+----------+  |
|            |                                          |             |
|            v                                          v             |
|  +--------------------------------------------------------------+  |
|  |  Crux Transport Backends                                     |  |
|  |    TCP   |   RoCEv2 (verbs)   |   InfiniBand   |   DPDK     |  |
|  +-------------------------------+------------------------------+  |
|                                  |                                  |
|                                  v                                  |
|  +--------------------------------------------------------------+  |
|  |  Hardware (NIC + Switch fabric, ECMP, DSCP queues, PCIe)    |  |
|  +--------------------------------------------------------------+  |
+--------------------------------------------------------------------+
^ Fig 11: Crux software stack. CoCoLib replaces the user's
  collective library; CD runs the algorithm; CT executes the
  decisions via verbs. Note: Crux REPLACES NCCL/Gloo at the
  collective-API surface — it is not a plug-in tuner inside NCCL.
  Total Crux LoC: 7,000.

Three deployment details surface from Section 5:

• Leader CD per job. Within each job, only one CD makes decisions; others mirror them. Inter-CD synchronization is <0.01% of cluster bandwidth.
• Path probing uses INT (in-band network telemetry). Crux varies the 16-bit UDP source port until probing packets reach all candidate ECMP paths; INT records per-hop info for each path. INT is "not imperative" (calculation from the hash algorithm is an alternative).
• Profiling exemption. When a new job arrives, Crux temporarily assigns it the unique-highest priority during the 30-second profiling window so its W_j and t_j measurements are not contaminated by contention. After profiling, the job's priority is recomputed based on the just-measured I_j.

The architecture deliberately requires no modification to DLT model code — replacing the original communication library (NCCL or Gloo) with CoCoLib is the only user-side change. This is the same plug-in surface as a standard collective library; the difference is that Crux's CD/CT pair runs inter-job scheduling logic that NCCL and friends do not have.

7. Quantitative Results — Empirical Findings by Regime

7.1 Headline real-testbed results (96-GPU, Section 6.2)

The two highest-utilization-gain regimes (PCIe contention with multiple ResNets vs one BERT) reach +14.8% utilization — the paper's headline number. JCT improvements stack in the same direction: GPU-intensive jobs (GPT, BERT against ResNet) get -7% to -33% JCT; low-intensity jobs (ResNet) pay +1% to +3% — a small price.

7.2 Trace-driven simulation (5,000+ jobs, Section 6.3)

(GPU utilization, normalized to 1.0; values verbatim from Figure 23.)

Crux-full outperforms Sincronia by +23 percentage points on Clos (0.39 -> 0.62) and +7 points on double-sided (0.43 -> 0.50). Against the strongest baseline (TACCL*) the gain is +13 / +4 points respectively. The double-sided topology is harder to optimize because its three-layer design provides more redundant paths but also more places for hash collisions; the Clos is where Crux's path-selection lever has the most room.

7.3 Ablation across Crux components (Figure 23)

Crux-PA: priority assignment only. Crux-PS-PA: path selection + priority assignment. Crux-full: + priority compression to 8 levels.

• Adding path selection (Crux-PA -> Crux-PS-PA on Clos): 0.51 -> 0.62 = +11 percentage points. This is the largest single component gain.
• Adding priority compression (Crux-PS-PA -> Crux-full): 0.62 -> 0.62. Compression introduces near-zero loss when the K-cut algorithm is well-designed — the paper claims this validates the Max-K-Cut formulation.

7.4 Composability with job schedulers (Section 6.4)

Crux is additive on top of state-of-the-art job schedulers (Muri, HiveD). Even a topology-aware scheduler like HiveD leaves +11 percentage points of utilization unrecovered; communication contention persists because job schedulers do not control flow paths or priorities.

7.5 Microbenchmark optimality (Section 4.4)

On 1,500 enumerated small cases where the global optimum is exactly computable, each Crux sub-algorithm averages within 3% of optimal. Sincronia, TACCL*, and Varys baselines fall further from optimum (the paper shows CDFs of relative error in Fig. 16 but does not give exact mean values for baselines).

7.6 Trace dataset findings (Section 2.2)

• 36.3% of jobs experience contention; 51% of GPUs affected.

• 10% of jobs occupy ≥128 GPUs; largest job 512 GPUs.

• Peak: 30+ concurrent jobs, 1,000+ active GPUs.
• Most contention on inter-host network paths (geometry A); minority on intra-host PCIe (geometry B).
• A representative GPT+BERT collision: 11.0% iteration-time inflation, 9.5% utilization drop.

7.7 Per-job sacrifice statistics (Section 7.2)

The lowest-priority jobs see at most a 55.5% throughput decrease but no job is starved. The paper attributes this to the periodic-bursty traffic pattern of DLT: link idleness exists in the gaps, so even low-priority jobs find communication windows.

8. Configuration-Regime Trade-off Tables

8.1 Scheduler-family choice

For the inter-job multi-tenant problem, Crux wins. Its lever (path + priority) and metric (utilization) match the cluster-provider objective. NCCL-internal tuning (DynamICCL territory) is orthogonal: even if NCCL chose perfectly inside each job, contention between jobs over shared links is invisible to NCCL's lever and would still leave 23 percentage points of utilization on the table.

8.2 Path-selection strategy

For DynamICCL, prefer to leave path selection to Crux-class systems. NCCL's path is determined by the QP setup and ECMP outside NCCL's view; pushing that decision into NCCL would require redesigning the transport layer. Crux's separation — flow path is the cluster scheduler's job, collective shape is NCCL's job — is the correct layer split.

8.3 Priority-assignment basis

The two examples from Section 4.2 are the load-bearing motivation: two jobs with identical GPU intensity can have different optimal priorities depending on iteration length and overlap pattern. The correction factor k_j is Crux's mechanism to capture both effects through a single scalar adjustment, anchored on a reference job.

8.4 Priority-compression strategy

The critical insight is that two priority-distinct jobs that do not contend (do not share network links) lose nothing from being mapped to the same hardware priority level. Crux's Max-K-Cut formulation explicitly preserves contending pairs across cuts and freely collapses non-contending pairs — the paper's microbenchmark shows this introduces "near-zero" loss compared to PS-PA without compression.

8.5 Topology and contention-geometry coverage

The paper's coverage of intra-host scheduling is shallower than its inter-host coverage — Crux uses semaphores in the daemon to gate PCIe traffic, with no equivalent mechanism for NVLink (which is more bandwidth-elastic). This is consistent with the trace observation that PCIe contention is rare relative to network-path contention.

9. Bottlenecks & Insights Surfaced by the Measurements

9.1 The reduction to a single scalar (GPU intensity) is the load-bearing claim

The paper's central engineering bet is that I_j = W_j / t_j is sufficient to rank jobs for scheduling priority. This is not obvious — it ignores tensor-parallel vs data-parallel mix, optimizer state size, and per-iteration phase structure beyond a coarse overlap ratio. Theorem 1 makes it rigorous in a single-link limit; the rest of the paper engineers around the gaps. The Section 4.2 examples (Examples 1 and 2) are explicit acknowledgments that a single I_j misses iteration-time and overlap differences, which is why Crux multiplies it by a correction factor k_j to recover those. The lesson is that one scalar plus one correction factor is enough to capture a surprising amount of multi-tenant DLT behavior — but only after Theorem 1 establishes the equivalence.

9.2 Path selection contributes more than priority assignment

The Clos-topology ablation shows priority assignment alone (Crux-PA) at 0.51 and adding path selection (Crux-PS-PA) jumping to 0.62 — an 11-point bump from path selection vs only 3-point gap from PA over the strongest baseline (TACCL* at 0.49). Hash-collision avoidance through deliberate UDP-source-port choice is the single biggest lever in Crux. The downstream priority assignment and compression make sure that when contention does occur, it favors the right job.

9.3 Priority compression is essentially free when graph-aware

Crux's Max-K-Cut DAG formulation reduces 5,000 distinct priorities to 8 hardware levels with effectively no loss (Crux-PS-PA 0.62 -> Crux-full 0.62). The reason — articulated in Section 4.3 and the example — is that two jobs that don't share links can collapse to the same priority for free. This is the same observation that makes coflow scheduling tractable: only contending coflows need ordering; non-contending ones can be batched.

9.4 The reference-job approximation is the chief algorithmic compromise

Section 7.1 states explicitly: "the reference job should be all possible combinations of jobs which have communication contention with the given job, rather than one job." The principled solution requires exponential enumeration; Crux ships the linear approximation (single most-traffic-heavy reference job). The 97% optimality on small cases suggests the gap is small in practice, but for clusters with deeply heterogeneous traffic patterns the approximation could degrade.

9.5 Storage / dataloader traffic is an unmodeled noise source

The t_j measurement (max link traversal time per iteration) can be polluted by checkpointing, dataset loading, or any storage-related burst. Modern compute/storage separation reduces the impact, but Section 7.1 acknowledges this as an unhandled failure mode. An RL-based extension (or any future Crux v2) would need to add a storage-traffic feature to the state vector to recover from this regime.

9.6 The 36% contention rate is the motivating discovery

Without the trace observation that 36.3% of jobs experience inter-job contention (occupying 51% of cluster GPUs), no scheduler-design effort is justified. The dataset release (alibaba-lingjun-dataset-2023) is therefore Crux's most reusable artifact — any future inter-job scheduler can be evaluated against the same workload distribution and rate of contention.

9.7 The orthogonality claim is empirically validated

Section 6.4 shows Crux + Muri or Crux + HiveD beats either alone. The job scheduler does GPU placement; Crux handles the residual flow contention. This is the cleanest empirical evidence of layer separation in the paper: two control planes operating on different decision variables (GPU allocation vs flow path/priority) produce additive gains.

9.8 The intra-host PCIe semaphore is an underspecified mechanism

The paper says "CDs maintain semaphores for PCIe links, and block PCIe communication of lower-priority jobs when higher-priority jobs use the PCIe links." This is enforced via inter-process shared memory — but the paper does not disclose the granularity (per-flow? per-collective?) or the latency cost of semaphore acquisition. For workloads where intra-host PCIe contention dominates (small clusters, single-host multi-job), the semaphore implementation could be a bottleneck.

10. Limitations of the Methodology

The most consequential limitation is methodological rather than algorithmic: Crux is evaluated against three baselines (Sincronia, TACCL*, CASSINI) drawn from the three families of communication schedulers. It is not evaluated against a combination of those families, nor against a learning-based alternative (RL, contextual bandit). Whether Crux's hand-engineered I_j-based prioritization could be improved by learning is left open.

11. Analogy

Crux is the air-traffic-control tower of a multi-airline hub. The cluster is the airport; each DLT job is an airline (with its own gates, ground crews, and passenger throughput); the network links and PCIe links are the runways and taxiways shared across all airlines. Without Crux, airlines compete for the same runway by chance — first-come-first-served on a random-hash queue (ECMP). With Crux, the tower assigns runways and queue priority based on how many passengers each airline carries per minute of runway use — a heavy-bodied A380 with 850 passengers (high GPU intensity, GPT-class) gets a clean uncontested taxi route and the front of the takeoff queue, while a regional jet with 50 passengers (low GPU intensity, ResNet-class) accepts a slightly longer wait because its delay costs the airport less revenue. The correction factor k_j is the tower's adjustment for flight-pattern characteristics: a short-hop shuttle (short iteration time) is given priority over a long-haul intercontinental flight (long iteration time) of the same passenger count, because completing more shuttle flights per hour fills more seats overall — exactly Example 1. The priority compression to 8 levels is the FAA's edict that the tower must speak to aircraft on only 8 radio frequencies; Crux's Max-K-Cut DAG is the algorithm that decides which flights can share a frequency without colliding (because they never want the same runway at the same time) and which must be kept on separate channels. Crux's choice to leave NCCL's internal collective algorithm untouched is the choice to leave aircraft-internal cabin operations to the airlines themselves — the tower decides which runway and when; the airline decides how to load passengers, what meal to serve, and which engine throttle profile to use on takeoff. Two control planes, two layers, two metrics: GPU utilization at the airport, JCT inside each airline. The paper's single most important insight is that those two control planes can be additive — and the 11-point utilization gain Crux adds on top of HiveD's 25-point job-placement gain is the proof.