PaperlayerView exact revision on arXiv

Source-linked AI summary

RingStitch: Demand-Aware Optical Stitching for Fragmented TPU Clusters

Huiru Ao, Fan Yang, Binglei Wang, Bo Liu, Jialong Li

arXiv:2609.37627v1cs.NI

TL;DR

Multi-tenant TPU-style clusters can have enough aggregate idle chips for a job yet strand them under rack-local or full-rack placement. RingStitch treats fragments as schedulable and stitches them local-first into compact, low-cost rings; simulations report matched utilization, blocking, and waiting time against aggregate-capacity and network-unaware approaches while reducing ring cost.

  • Problem

    Local and full-rack allocation can leave partial rack capacity unusable even when aggregate idle chips suffice, while naive aggregation can increase communication cost.

    Source: §I · p. 1

  • Method

    RingStitch invokes optical stitching when local placement fails but aggregate residual capacity suffices, selecting compact fragment-aware rack sets and ordering them into low-cost rings.

    Source: §I · p. 1, §IV · p. 2

  • Results

    Across workloads and load levels, RingStitch matches Capacity-only Stitching and Network-unaware Best-Fit in utilization, blocking, and waiting time while consistently reducing cross-rack ring cost.

    Source: E. Takeaways · p. 5

  • Takeaways & Limitations

    The results support fine-grained optical defragmentation for multi-tenant AI clusters, recovering stranded capacity with lower modeled ring cost than naive cross-rack placement.

    Source: §VII · p. 6

Abstract

from arXiv · show

Large-scale AI training clusters increasingly use optical circuit switching (OCS) to reconfigure rack-level interconnects and create elastic accelerator slices. In multi-tenant TPU-style clusters, however, small and medium jobs often leave partial free capacity stranded inside racks. Although the aggregate free capacity may be sufficient for a new job, it cannot be used by local placement or coarse full-rack stitching. This paper presents RingStitch, an OCS-based defragmentation scheduler that turns fragmented rack capacity into schedulable resources. RingStitch follows a local-first policy, stitches compact cross-rack fragments only when needed, and orders the selected racks into a low-cost logical ring. Simulations on a TPU 8t-like SuperPod model show that RingStitch improves schedulability over local and full-rack baselines.

I. INTRODUCTION

Rack-level allocation can strand partial capacity even when aggregate idle chips suffice, and naive cross-rack aggregation can raise communication cost. RingStitch uses local-first, fragment-aware optical stitching and topology-aware ring ordering; the motivating cases distinguish feasibility from placement quality.

I. INTRODUCTION

  • Local-only and full-rack allocation strand partial capacity, while naive cross-rack aggregation can scatter jobs across distant racks and inflate communication cost.A job may fit in aggregate but in neither one rack nor fully free racks.Source: §I · p. 1
  • Prior ML-cluster schedulers address sharing and placement, but do not model OCS as a placement-time resource for communication-aware stitching.Source: §I · p. 1
  • RingStitch treats partial rack capacity as schedulable, invoking stitching only when local placement fails and aggregate residual capacity suffices.It selects compact, fragment-aware rack sets, allocates fragments first, and orders racks into a low-cost logical ring.Source: §I · p. 1

II. MOTIVATION

  • The motivating cases separate feasibility from quality: residual fragments can meet demand, while topology and post-placement fragmentation distinguish better placements.Cases A–B show aggregate residual capacity meeting demand when no single or fully free rack suffices; Case C favors nearby racks for lower ring cost, and Case D preserves two 12-chip blocks by using 7- and 8-chip fragments.Source: §II · pp. 1–2, Figure 1 · p. 2

III. SYSTEM MODELING AND SCHEDULING SEMANTICS

The model represents an OCS cluster through rack capacities and fixed rack geometry, then defines jobs and feasible placements over those residual resources. It distinguishes rack-local feasibility from aggregate-capacity feasibility and queues jobs that cannot be placed under the current policy.

A. Cluster and Rack Abstraction

  • A TPU-style cluster is modeled as N racks of C chips on a fixed three-dimensional torus, with residual capacities dynamic and rack coordinates and distances static.The global scheduler chooses participating racks and chip allocations, abstracting away chip-level placement within each rack.Source: A. Cluster and Rack Abstraction · p. 2

B. Job and Placement Model

  • Each job has a chip demand, arrival time, and execution time; placement selects racks and allocations that satisfy the job's demand within rack residual capacities.Jobs are gang-scheduled, receiving all chips before starting and retaining them until completion.Source: B. Job and Placement Model · p. 2, A. Cluster and Rack Abstraction · p. 2
  • The target fragmentation regime has no rack with enough chips but sufficient aggregate residual capacity; jobs without a policy-feasible placement are deferred.Source: B. Job and Placement Model · p. 2

C. OCS Ring-Cost Model

A cross-rack placement is realized as a closed logical ring, whose cost depends on the rack ordering. The model’s closed-tour convention counts both directions for a two-rack ring and excludes contention and execution-time effects.

C. OCS Ring-Cost Model

D. Online Scheduling Semantics

RingStitch handles jobs with a local-first policy, then uses cross-rack stitching when local placement fails but aggregate residual capacity is sufficient. Online placement is event-driven and nonpreemptive, with simplified OCS configuration assumptions.

D. Online Scheduling Semantics

  • At each arrival or completion, queued jobs are considered in arrival order; infeasible jobs remain queued while later feasible jobs may start.Admitted jobs are nonpreemptive and release their chips after execution time t_j.Source: D. Online Scheduling Semantics · p. 2
  • The simulator treats OCS configuration as instantaneous and omits port constraints, failures, and concurrent-link contention.These abstractions isolate rack-level placement and topology-aware stitching effects.Source: D. Online Scheduling Semantics · p. 2

IV. DESIGN

  • RingStitch is a local-first policy that recovers aggregate residual capacity while controlling rack count, ring cost, and post-placement fragmentation.Source: §IV · p. 2

A. Overview

  • For each job, RingStitch tries rack-local best-fit first, defers when aggregate residual capacity is insufficient, and otherwise evaluates bounded cross-rack candidates.It allocates chips fragment-first, computes a low-cost ring, scores candidates lexicographically, and configures the selected ring.Source: A. Overview · pp. 2–3, Figure 2 · p. 3

B. Hybrid Candidate Generation

RingStitch bounds candidate generation by applying four greedy heuristics to racks with positive residual capacity, stopping each once it meets job demand and removing infeasible or duplicate sets.

B. Hybrid Candidate Generation

  • Each heuristic stops when selected capacity reaches demand, leaving at most four feasible, unique rack-set candidates without exhaustive subset enumeration.Source: B. Hybrid Candidate Generation · p. 3
  • Small-fragment-first consumes smaller residual blocks first, while fewest-racks-first takes larger blocks to limit ring participants.Source: B. Hybrid Candidate Generation · p. 3
  • Best-fit greedily seeks a close capacity fit, while local-neighbor-first adds racks nearest to the selected set on the torus.Best-fit does not solve a global subset-sum problem.Source: B. Hybrid Candidate Generation · p. 3

C. Allocation, Ring Ordering, and Scoring

For each candidate, RingStitch constructs a fragment-first allocation and ring order, then selects among candidates using a strict lexicographic objective.

C. Allocation, Ring Ordering, and Scoring

  • Racks are processed in increasing residual capacity for fragment-first allocation, which exhausts small residual blocks when possible and preserves larger blocks for future jobs.Source: C. Allocation, Ring Ordering, and… · p. 3
  • For up to eight racks, RingStitch enumerates ring permutations for an exact minimum; larger sets use a feasible nearest-neighbor order that is not necessarily optimal.Source: C. Allocation, Ring Ordering, and… · p. 3
  • Candidate scoring prioritizes fewer racks, then realized ring cost, then fragmentation cost; it never adds a rack solely to improve either cost.The fragmentation penalty is largest for small positive leftovers and zero for fully consumed residual blocks.Source: C. Allocation, Ring Ordering, and… · p. 3
  • After selection, RingStitch commits the chosen chip allocation and its previously computed ring order.Source: C. Allocation, Ring Ordering, and… · p. 4

V. EVALUATION

The evaluation uses a discrete-event simulator to assess utilization, blocking and waiting, and cross-rack communication cost.

V. EVALUATION

  • A discrete-event simulator tracks rack-level residual capacity, job arrivals and completions, and OCS-aware placement decisions.Source: §V · p. 4
  • The evaluation asks whether RingStitch improves utilization, reduces blocking and waiting, and limits cross-rack communication cost.Source: §V · p. 4
  • The evaluation examines three outcome dimensions: utilization, blocking and waiting, and communication cost.Source: §V · p. 4

A. Methodology

The evaluation uses a simulated 150-rack, 9,600-chip TPU 8t-like cluster and four workload mixes spanning varied fragmentation and stitching pressure.

A. Methodology

  • The simulated cluster has 150 racks with 64 chips each, embedded in a 5 × 5 × 6 3D torus; offered load ranges from 60% to 95%.Jobs arrive according to a Poisson process and have size-dependent log-normal durations.Source: A. Methodology · p. 4
  • Workloads A–D range from production-inspired large slices to fragmented mixes and a phased workload that creates residual fragments before cross-rack demand rises.Workloads B and C emphasize 40–56-chip jobs; C adds just-over-one-rack demands, while D applies long jobs before many cross-rack jobs.Source: A. Methodology · p. 4
  • Each configuration is repeated with 50 base random seeds, using common arrival traces across schedulers within each workload and load condition.Each run uses a 50-hour warm-up, 200-hour measurement window, and 50-hour drain phase.Source: A. Methodology · p. 4

B. Baselines

The evaluation compares local, full-rack, and fragment-aware schedulers across utilization, blocking, waiting time, and ring communication cost. RingStitch recovers fragmented capacity while retaining the admission behavior of aggregate-capacity policies and lowering modeled communication cost.

B. Baselines

  • The baselines are Local First-Fit, Local Best-Fit, Full-Rack Stitching, Capacity-only Stitching, and Network-unaware Best-Fit.Cross-rack schedulers share a ring-ordering procedure: exact enumeration for up to eight racks, then a nearest-neighbor heuristic.Source: B. Baselines · p. 4

C. Metrics

  • The evaluation measures utilization, chip-hour-weighted blocking, average and P95 waiting time, and mean 3D-torus ring cost among admitted cross-rack jobs.Rack-local placements are excluded from communication overhead because they construct no cross-rack ring.Source: C. Metrics · p. 4

D. Evaluation Results

  • At 95% load, RingStitch utilization is 94.5% in Workload B, 94.1% in C, and 82.1% in D, matching the fragment-aware baselines.In Workloads B and C, it exceeds Full-Rack Stitching by 5.0 and 4.4 percentage points, respectively.Source: D. Evaluation Results · p. 4
  • At 95% load in Workload B, RingStitch lowers demand-weighted blocking from 6.9% to 0.4% versus Full-Rack Stitching.The blocking comparison covers Workloads A–D; the figure reports demand-weighted blocking ratio.Source: D. Evaluation Results · p. 4, Figure 5 · p. 5
  • At 95% load in Workload B, RingStitch records 0.2/0.8 hours average/P95 waiting, versus 2.2/15.4 for Full-Rack Stitching.In Workload D, the corresponding values are 3.2/13.8 hours for RingStitch and 6.4/18.5 for Full-Rack Stitching.Source: Table II · p. 5, D. Evaluation Results · p. 5
  • At 95% load in Workload B, RingStitch’s average ring cost is 10.26, versus 12.78 for Capacity-only Stitching and 12.20 for Network-unaware Best-Fit.Full-Rack Stitching can have lower conditional communication cost in Workloads B–D, but admits a different job set alongside lower utilization, higher blocking, and longer waits.Source: D. Evaluation Results · p. 5

E. Takeaways

RingStitch recovers partial rack capacity and achieves lower modeled ring cost than topology-unaware cross-rack placement. The related work situates it among optical infrastructure and cluster schedulers, while distinguishing its placement-time defragmentation focus.

E. Takeaways

  • Across workloads and load levels, RingStitch matches fragment-aware policies in utilization, blocking, and waiting time while consistently reducing cross-rack ring cost.The conclusion characterizes this as reducing fragmentation-induced blocking with lower modeled ring cost than naive cross-rack placement.Source: E. Takeaways · p. 5, §VII · p. 6

VI. RELATED WORK

  • Prior optical systems address flexible topology, network architecture, routing, or traffic scheduling; RingStitch uses OCS for placement-time defragmentation –, –,, [21].The related work also distinguishes RingStitch from optical AI infrastructure that allocates complete racks or hardware blocks [1],,,.Source: §VI · p. 5
  • GPU-cluster schedulers optimize completion time, fairness, goodput, heterogeneity, or sharing –; network-aware placement and MoE load balancing address other scheduling concerns [17], [22].These works do not model OCS as a resource for stitching partial rack fragments into communication-aware slices.Source: §VI · pp. 5–6

VII. CONCLUSION

  • RingStitch selects compact, fragment-aware rack sets and stitches them into low-cost logical OCS rings for multi-tenant TPU-style clusters.The paper presents fine-grained defragmentation as a practical direction for optical reconfiguration in multi-tenant AI clusters.Source: §VII · p. 6
Loading 2609.37627v1…