Global Simulation-Guided Dynamic Operator Scheduling for Efficient Multi-Tenant Model Serving

Weinan Liu

Zeyuan Ding

Dian Ding

wnliu@stu.xmu.edu.cn Xiamen University, Shanghai Innovation Institute Xiamen, Fujian, China

boris1013@sjtu.edu.cn Shanghai Jiao Tong University Shanghai, China

dingdian94@sjtu.edu.cn Shanghai Jiao Tong University Shanghai, China

Guangtao Xue gt_xue@sjtu.edu.cn Shanghai Jiao Tong University Shanghai, China

Yiming Zhang sdiris@gmail.com Xiamen University Xiamen, Fujian, China

Abstract Container-granularity scheduling leaves abundant short-lived idle slices within containers unexploited. Reallocating containers is too heavyweight to utilize such fine-grained opportunities under SLA constraints, and operator-level scheduling requires reasoning about dependencies, memory safety, and cluster-wide execution dynamics in real time. In this paper, we present SliceScheduler, a dynamic operatorlevel scheduling system for multi-tenant model serving. The key idea is to expose cluster-wide operator execution state and enable what-if reasoning over scheduling decisions. SliceScheduler consists of four key components. First, we introduce the Global Mapping Graph (GMG), a unified abstraction that captures operator dependencies, tensor shapes, resource mappings, and execution states, providing a real-time, clusterwide view with explicit resource semantics. Second, we build a global simulator on top of GMG to predict operator-level execution and memory evolution under candidate placements. Third, we design an incremental, simulation-based scheduling module that selects placements to exploit fragmented idle slices while avoiding memory violations and preserving SLA. Finally, we develop an operator executor that materializes scheduling decisions on GPUs and coordinates computation and cross-accelerator transfers. We implement SliceScheduler as a PyTorch backend and evaluate it using production trace replay. Experimental results show that SliceScheduler improves token throughput by 1.10–2.29× compared to existing approaches, while maintaining SLA violations within 9%. SliceScheduler demonstrates that operator-level scheduling is a practical and effective approach to improving GPU utilization for multi-tenant LLM serving.

1.0 0.8 0.6 0.4 0.2 0.0

p90:10870.7ms

Jiwu Shu shujw@tsinghua.edu.cn Tsinghua University Beijing, China

0

p99:17627.5ms

Lu Tang tanglu@xmu.edu.cn Xiamen University Xiamen, Fujian, China

p95:14266.7ms

Chengcheng Wan ccwan@sei.ecnu.edu.cn East China Normal University, Shanghai Innovation Institute Shanghai, China

Idle Time (CDF)

arXiv:2608.15762v1 [cs.OS] 16 Aug 2026

Global Simulation-Guided Dynamic Operator Scheduling for Efficient Multi-Tenant Model Serving

90% 92% 94% 96% 98% 100% Idle Slice Count (%)

Figure 1. CDF of idle-slice durations from replaying a production AI coding traces on a single-GPU model instances. Only idle slices longer than 10 ms and less than 20 s are included. Average GPU utilization is 64.0%, and idle slices shorter than p99 account for 95.6% of total idle time. Idle slices are mostly short-lived.

1

Introduction

To serve concurrent LLM inference requests from numerous users efficiently, large cloud companies typically provide GPU resources in a centralized way [19, 20, 24, 37, 41]. As the cost of AI infrastructures grows substantially, researchers have proposed various techniques to improve GPU utilization for LLM inference service (i.e., model serving) in multitenant clouds [3, 37, 47]. The current mainstream practice is to perform tenant-granularity scheduling [23, 29] on top of container orchestration systems such as Kubernetes [17]. Each LLM inference service is packaged into a container and submitted to a centralized scheduler, which can allocate GPU resources to the container and reallocate them on demand, e.g., when the containerized inference service has less requests during a long period of time. In modern Model-as-a-Service (MaaS) clouds, GPU resources are often underutilized [41]. This is primarily because tenant-granularity scheduling of containers does not 1

Conference’17, July 2017, Washington, Weinan DC, Liu, USA Zeyuan Ding, Dian Ding, Chengcheng Wan, Lu Tang, Guangtao Xue, Jiwu Shu, and Yiming Zhang

align with the characteristics of model serving workloads. To better understand this inefficiency, we analyze the workloads of our production model serving clusters. As shown in Figure 1, there are a large number of short, fine-grained idle slices (p50: 2551.11 ms, p90: 10887.64 ms, p99: 17790.31 ms), as the inference services do not operate at full load at all times. Unfortunately, container-level scheduling cannot utilize the idle slices due to strict service-level agreement (SLA) requirements of model serving. The key problem is that containers were originally designed for deployment [6] rather than for scheduling. Once the scheduler allocates GPUs to an inference service container, the container drives GPU execution, while the scheduler no longer has direct control over it. As a result, the idle slices within a container’s execution logically belong to that container, and the scheduler cannot directly reallocate them to others. Container resource reallocation requires preemption and rescheduling, which typically involves checkpointing, re-queuing (under gang scheduling [42]), runtime cold start, and state restoration. This overhead is too high to operate at the time scale of second-level idle slices. Essentially, the container abstraction isolates the scheduler from GPU execution, limiting its visibility into and control over the numerous short-lived idle slices across the cluster. To allow the scheduler to directly control GPU execution, scheduling must move below the container level to finergrained execution units in inference services. Operators, such as kernels, ATen [9] ops, and LLM layers, readily fit into short-lived idle slices, making them natural scheduling units. This enables an inference service to no longer be tied to a fixed set of containers/GPUs; instead, its execution can be spread across the cluster. Although operator-level scheduling has been widely adopted in prior graph-based job schedulers [1, 2, 8, 22, 45], where jobs are represented as graphs and nodes (operators) are mapped to resources, applying operator-level scheduling to multi-tenant model serving remains challenging. To achieve this, the scheduler must track short-lived, fragmented idle slices in real time during inference execution, and schedule operators into them without violating the SLA. This brings the following three challenges. Challenge 1: Lack of operator resource requirement undermines memory safety. Prior graph-based schedulers model dependencies among graph nodes, but do not capture the operator-level resource requirement of individual operators. Specifically, they do not explicitly model the input/output memory footprint of each operator, which can cause an operator placement to trigger HBM out-of-memory (OOM). Dependency information alone is insufficient to ensure memory-safe scheduling on fragmented GPU resources. Challenge 2: Lack of temporal execution prediction limits scheduling effectiveness. Existing graph-based schedulers map graph nodes to resources to optimize specific objectives (e.g., data locality), but lack the capability to predict how

inference execution evolves over time at cluster scale. Static operator-resource mapping is insufficient, as short-lived idle slices emerge dynamically between operator executions and require the scheduler to reason not only about static operator placement but also about evolving execution states. This paper presents SliceScheduler, an efficient operatorlevel scheduler that dynamically schedules operators (layers) into idle slices to improve GPU utilization without violating SLA constraints. The key idea of SliceScheduler is to expose cluster-wide, fine-grained operator execution state to the scheduler so that scheduling decisions can be simulated and assessed before being applied in a real multi-tenant model serving cluster. SliceScheduler address the aforementioned challenges with the following designs. First, we propose Global Mapping Graph (GMG), a clusterwide representation of active operators with their dependencies, tensor shapes, and resource mappings. Since each operator’s tensor shape can be inferred before execution, operators in the GMG have explicit resource requirements. This allows the GMG to capture HBM occupancy across the cluster, together with tensor residency and operator dependency. Operators are inserted to and removed from the GMG over time, providing a real-time view of the cluster state. Second, we design a global simulator on top of GMG that predicts how operator executions evolve across the cluster under a given scheduling decision. Operator execution is predictable, as operator latency is largely determined by compute-intensive kernel implementations with stable execution times for a given shape [46]. Similarly, tensor transfer is also predictable. Leveraging this predictability, together with the dependencies and resource mappings in GMG, we can precisely simulate future cluster states. Third, based on GMG and global simulation, we propose dynamic operator-level scheduling for multi-tenant inference services. Users submit inference requests as computation graph instances with priority, which are inserted into the GMG. SliceScheduler plans and evaluates candidate operator scheduling policies via parallel what-if simulations, selecting the one that avoids OOM and achieves the best predicted completion time and resource efficiency. Finally, we design an operator executor to materialize selected scheduling decisions on GPUs. We first consider singleGPU execution by introducing an operator queue, and then extend to cross-GPU tensor transfers to explicitly model data movement between GPUs. Tensor transfers are managed by an arbitration algorithm, which enables SliceScheduler to coordinate distributed computation and communication under a unified runtime. Together, these mechanisms provide the execution foundation for cluster-wide operator scheduling. We evaluate SliceScheduler by replaying production traces. The results show that SliceScheduler can opportunistically insert offline workloads into second-level idle slices left by online workloads, while achieving load balancing across the cluster. Compared with the online-only and GPU-sharing 2

SliceScheduler : Global Simulation-Guided Dynamic Operator Scheduling

Count

1000

Conference’17, July 2017, Washington, DC, USA

Trace 0 Trace 1 Trace 2 Trace 3

500

0

7

15 Time (s)

22

30

(a) Execution timeline of a high-priority online instance during trace replay (blank slices refers to idle).

0 00:00 03:00 06:00 09:00 12:00 15:00 18:00 21:00 24:00

Time (HH:MM)

0

Total Time (s)

(a) Request volume, aggregated over 10-minute intervals.

1000

Trace 0 Trace 1 Trace 2 Trace 3

22

30

Figure 3. An illustrative co-location example @ 1 GPU.

0 00:00 03:00 06:00 09:00 12:00 15:00 18:00 21:00 24:00

Time (HH:MM)

diurnal patterns. All four traces share same peak periods during 08:00–12:30, 14:00–18:00, and 19:00–23:59. Using TTFT and TPOT of the traces, we conservatively compute the model-instance compute time within each 10minute window, as shown in Figure 2 (b). Most windows have compute time below 600 s (i.e., window duration), indicating that the model instance is far from fully utilized in most times. Even during peak periods, the demand remains uneven across traces: while one trace may impose more than 600 s of aggregate compute demand in a window, another may still remain below it. This means that, at the same time, some instances can be overloaded while others are underutilized, revealing opportunities for cross-instance load balancing. To further understand the headroom, we replay the trace on a Llama3 8B [30] instances deployed on one A16 GPU. As shown in Figure 1, the average GPU utilization is 64.0%, and the execution contains a large number of idle slices. Their durations have a median of 2551.11 ms, a 90th percentile of 10887.64 ms, and a 99th percentile of 17790.31 ms. Idle slices shorter than the 99th-percentile duration account for 95.6% of total idle time, showing that idle slices are substantial in aggregate. This provides performance enhancement opportunity by utilizing such resource fragmentation. Next, we conduct a small co-location experiment with two Llama3 8B [30] instances on a single A16 GPU: a highpriority online instance and a low-priority offline instance. During trace replay, the online instance exhibits substantial idle slices. We then opportunistically place requests from the offline instance into those gaps. As shown in Figure 3, this converts part of the online instance’s idle time into useful work. With the SLA maintained, the throughput of tokens is improved by 1.25×. It suggests that fine-grained idle slices left by online services can in principle be reclaimed by lowpriority work, motivating a scheduling abstraction finer than containers.

Figure 2. Four one-day production traces from an AI-coding service.

baselines, SliceScheduler improves token throughput by 1.10×– 2.29× and Service Level Objective (SLO) attainment by ∼9%. We further show that dynamic operator-level scheduling is practical: the global simulator sustains an average throughput of ∼176 simulated operators per millisecond, achieving about four orders of magnitude higher throughput than prior approaches [40]. We make following contributions: • We introduce GMG, an operator-level abstraction for multi-tenant model serving that enables global simulation of operator execution and HBM occupancy. • We design SliceScheduler, a dynamic operator-level scheduler for multi-tenant model serving, and propose a simulation-based scheduling algorithm. • We implement SliceScheduler as a PyTorch [10] backend, and validate the effectiveness of dynamic operator scheduling on real-world workloads.

Background & Motivation

Modern multi-tenant model serving clusters mainly adopt container-level scheduling [17, 20, 24, 41]. However, production traces show that there are many short-lived idle slices that such scheduling fail to utilize. This section first characterizes these idle patterns and then explains the main challenges in utilizing them. 2.1

15 Time (s)

(b) Requests from a low-priority offline instance could utilize idle slices (yellow slices).

(b) Conservative model-instance computation time in each 10-minute interval.

2

7

Trace Characterization

We collect two-week AI coding traces from an industrial company. Each request record includes its arrival timestamp, context length, output length, time to first token (TTFT), and time per output token (TPOT). From this trace, we select four representative days and analyze them as four one-day traces. As shown in Figure 2 (a), the workload exhibits clear

2.2

Why Container-Level Scheduling Cannot Exploit Fine-Grained Idle Slices

The traces above show substantial fine-grained idle slices in online ML services. Note that, these idle slices does not 3

Conference’17, July 2017, Washington, Weinan DC, Liu, USA Zeyuan Ding, Dian Ding, Chengcheng Wan, Lu Tang, Guangtao Xue, Jiwu Shu, and Yiming Zhang

simply reflect misprovisioning. Services are often provisioned near saturation for SLA reasons, yet still generate transient idle slices due to bursty demand. Existing container-level schedulers fail to exploiting idle slices for two reasons: coarsegrained control and exclusive resource ownership.

However, such approaches still do not address the kind of fragmentation we face. One line of GPU sharing partitions compute and HBM statically [33], reserving a fraction of each GPU for low-priority jobs. This enables steady co-location, but it is fundamentally a fixed spatial partitioning scheme: it does not capture the transient idle slices generated by the high-priority workload during execution. Another line allows multiple jobs to share a GPU without static HBM partitioning [34, 44]. Such approaches are most effective when co-located training jobs have overlapping but manageable memory-demand patterns. In modern Large Language Model (LLM) serving, however, model weights and runtime state tend to stay resident in HBM, making memory pressure, swapping, and performance interference much more likely during peak demand. More importantly, these methods remain poorly suited to exploiting idle slices that is fragmented across multiple GPUs and containers. This is because online services typically occupy most of the HBM, leaving only small residual memory regions scattered across different GPUs for lower-priority jobs. To exploit such fragments, the low-priority job itself must be decomposable into fine-grained pieces and spread across multiple GPUs, potentially crossing container boundaries. At the same time, as cluster scale grows, the total amount of idle slices may increase, but idle slices on different GPUs rarely align in time. To validate this, we replay the four representative one-day traces mentioned above on four model instances. Surprisingly, no more than 20% of the idle time overlaps across the four traces. The more GPUs the lowpriority job needs to cover, the less likely they are to become idle simultaneously. Consequently, if a low-priority job is still deployed as a GPU-sharing container, it often requires multiple GPUs to be concurrently available in order to make progress on its end-to-end computation. This significantly limits the amount of idle slices it can exploit and increases the likelihood of interfering with existing online workloads. Even if such methods can run a job on a small number of GPUs, the job still cannot exploit idle slices on other GPUs in the cluster.

2.2.1 Coarse-Grained Control. Container orchestration systems were originally designed for application deployment rather than direct control of accelerator execution [6]. A scheduler selects a node that satisfies a container’s resource request, after which the target node pulls the image, initializes the runtime environment, launches the application process, and lets the process drive the assigned GPUs. In other words, container schedulers control resource usage only indirectly through the application runtime, rather than directly managing GPU compute units or HBM. This design naturally binds a container to a fixed set of accelerators for a relatively long period after launch. To handle longer-timescale load variation in ML workloads, prior systems introduce elasticity [27, 38], which reclaims resources through preemption and rescheduling. But elasticity is expensive: the application must first checkpoint, and then go through rescheduling, gang-scheduling [42] delays, image pulling, environment initialization, and checkpoint loading. In practice, the end-to-end overhead is often on the order of minutes. As a result, elasticity is useful mainly for long-timescale reallocation. For example, prior work uses it to search for better configurations for long-running training jobs [38], or to exploit diurnal variation by shrinking online services at night and reallocating resources to other workloads [27]. Such mechanisms are ill-suited to our scenario. For online services with frequent second-scale idle slices, simply reducing the number of GPUs directly hurts SLA attainment; conversely, using elasticity to let low-priority jobs opportunistically fill these idle slices is impractical because the rescheduling overhead is far too high. At a deeper level, the mismatch comes from the unit of control. A container scheduler does not move a few kernels or a small region of HBM; it migrates and reconstructs an entire application runtime and execution environment. Therefore, container-level control is fundamentally too heavyweight to track and exploit fine-grained execution gaps on accelerators.

2.3

Requirements for Exploiting Fine-Grained Idle Slices

Exploiting fine-grained idle slices requires more than moving below containers. The system must answer four questions. How to design resource semantics that capture operatorlevel hardware requirements? Operator shapes are sufficient for this purpose. Given an operator’s shape, its execution time on a particular accelerator is largely predictable. Likewise, given tensor shapes, transfer latency across accelerators is also predictable. Therefore, we uses the GMG as a unified abstraction of cluster state, and every operator inserted into GMG carries explicit shape information. How to reconstruct the execution timeline and reason about cluster evolution? With operator dependencies, the

2.2.2 Exclusive Resource Ownership. A second challenge is that these fine-grained idle slices still logically belong to the original containers. Even when an online service does not fully utilize GPU compute or HBM at every moment, these slices remain allocated to that container. Since we cannot modify users’ applications, we cannot expect them to voluntarily expose or coordinate these fine-grained resources for use by other workloads. Prior works like GPU sharing [39, 44] recognize that exclusive GPU ownership can lead to low utilization on a single device, and thus seek to co-run multiple jobs on one GPU. 4

SliceScheduler : Global Simulation-Guided Dynamic Operator Scheduling

completion of one operator will trigger its successors, causing cluster execution state to evolve over time. Thus we design an event-driven global simulator that advances execution along operator dependencies. How to design the whole scheduling mechanism? GMG serves as the core abstraction maintained by the master. Serving applications express computation graph execution. Then we build an independent scheduling module that works together with GMG. During scheduling, the module constructs global simulators and uses them to generate operator-granularity scheduling policies. How to design an operator executor that realizes scheduled execution? We first design operator execution on a single accelerator, and then extend it to tensor transfer across accelerators. Finally, we introduce the tensor transfer arbitration to coordinate tensor movement among all accelerators in the cluster. Together, these requirements point to a scheduling layer that is (i) the GMG for cluster-wide state abstraction with operator shape, (ii) a global simulator, (iii) a scheduling module, and (iv) an operator executor. The rest of this paper presents such a design.

3

Figure 4. Overview of SliceScheduler. The system centers on the Global Mapping Graph (GMG), which serves as a unified abstraction of computation, placement, and runtime state. Built on top of GMG, the Global Simulator predicts execution dynamics, the Scheduling Module performs simulation-based placement decisions, and the Operator Executor executes operators and transfers on accelerators. Runtime feedback continuously updates GMG and estimators, enabling a closedloop, prediction-driven scheduling system.

SliceScheduler Design

To tackle these problems, we propose SliceScheduler, an efficient operator-level scheduler that can dynamically schedule low-priority operators into high-priority operators’ idle slices and significantly improve GPU utilization without violating SLA constraints. 3.1

Conference’17, July 2017, Washington, DC, USA

whose operators are inserted as unscheduled. From this evolving state, SliceScheduler performs (2) Scheduling and simulation by selecting a batch of operators and invoking the scheduling module, which constructs global simulators to evaluate candidate placements via what-if simulation. After selecting a placement, SliceScheduler proceeds with (3) Issuing by updating operator-to-accelerator mappings in GMG, marking operators as issued, and dispatching them together with required transfers to the executors. During execution, accelerators process operators via dependency-driven queues while handling (4) Transfer arbitration to coordinate crossaccelerator tensor transfers. As operators and transfers complete, SliceScheduler performs (5) Feedback by reporting runtime information back to the master, marking operators as done, and updating performance estimators to improve future simulation and scheduling decisions.

System Overview

Overview. As shown in Fig. 4, SliceScheduler decomposes cluster-scale scheduling into four tightly coupled layers: state abstraction, prediction, decision, and execution. At the core is the Global Mapping Graph (GMG), which provides a consistent cluster-wide view of operators, dependencies, tensor shapes, and their placement on accelerators. This global abstraction is necessary for making coherent scheduling decisions. However, scheduling depends not only on the current state, but also on its future evolution. To this end, SliceScheduler builds the Global Simulator on top of GMG, which reconstructs execution behavior and predicts operator execution and tensor transfer timelines under candidate placements. Based on these predictions, the Scheduling Module selects placements through incremental what-if simulation, enabling fast yet globally informed decisions. Finally, the Operator Executor realizes these decisions on accelerators, while feeding runtime feedback back to GMG and the estimators. SliceScheduler consists of a centralized master and a set of accelerators that execute operators. The master maintains the GMG as a global state abstraction, where serving applications perform (1) Registration and instantiation by registering graph templates and instantiating graph instances

3.2

Global Mapping Graph

Existing systems lack a unified abstraction that captures both computation structure and resource states at operator granularity, making it difficult to reason about scheduling decisions globally. GMG unifies computation structure, placement, execution state, and scheduling metadata into a single abstraction. Graph structure. The core of SliceScheduler is the Global Mapping Graph (GMG). As shown in Figure 5, GMG consists of a Shape DAG and an Accelerator Set. In the Shape DAG, each node represents an operator annotated with its tensor shape and executor state, and each edge represents a data 5

Conference’17, July 2017, Washington, Weinan DC, Liu, USA Zeyuan Ding, Dian Ding, Chengcheng Wan, Lu Tang, Guangtao Xue, Jiwu Shu, and Yiming Zhang

specific locations, such as accelerator HBM. It enables incremental scheduling by allowing new graph instances to be attached to retained intermediate states. 3.3

Global Simulator

The global simulator predicts how operator execution evolves across the cluster under different scheduling decisions.

Figure 5. GMG maps operators to accelerators. It describes the global status of tasks and the cluster, as well as the computation progress of all tasks.

3.3.1 Transfer & Operator Estimator. To support fast simulation, SliceScheduler maintains a set of lightweight linear estimators for tensor transfer and operator execution. Transfer estimator. For each accelerator pair, SliceScheduler maintains a linear estimator for transfer latency:

dependency. Operator nodes are mapped to accelerators in the Accelerator Set. The executor state of an operator indicates whether it is unscheduled, issued, or done. Execution lifecycle. We design the computation pattern as a register-once, instantiate-many-times workflow. A serving application first registers a graph template with SliceScheduler, and then repeatedly instantiates this template for subsequent executions. All graph instances derived from the same template share the same graph topology, while the shapes of individual operators may vary across instances. For each new execution instance, the application specifies its inputs by referencing existing operators in GMG. The registered template contains symbolic shape information, allowing SliceScheduler to infer the shape of every operator in the instance from the input shapes. After shape inference, the instantiated graph is inserted into GMG as a set of unscheduled operators. As execution proceeds, GMG evolves continuously. When an operator is issued to a specific accelerator, GMG records its placement and issuing information and marks it as issued. When the operator finishes execution, GMG marks it as done and releases the associated resource accounting. GMG is therefore not a static task description. Instead, it is a clusterwide dynamic view that continuously evolves with execution and tracks the cluster state at operator granularity. Scheduling metadata. SliceScheduler maintains several key metadata for scheduling. First, when a graph template is registered, SliceScheduler creates an empty operator estimator (§3.3.1) for every operator in the template. Each time an operator finishes execution, its observed execution time is fed back to the corresponding estimator, which is updated continuously over time. Second, GMG has its own global timestamp to track the real world time, with each node holding its timestamp to be issued and done. Together with inter-operator dependencies, these timestamps provide the starting point for temporal prediction of the global simulator. Third, each node stores the shapes of its output tensors. These shapes are used to estimate the operator’s execution time, its HBM occupancy during execution, and the latency of subsequent cross-accelerator tensor transfers. Finally, each node maintains checkpoint metadata that identifies which intermediate results are persistently retained at

𝑡 = 𝛼 · 𝑠𝑖𝑧𝑒 + 𝑐, where 𝑠𝑖𝑧𝑒 is the tensor size, 𝛼 reflects the inverse of effective bandwidth, and 𝑐 captures fixed transfer overhead. Operator estimator. For each pair of accelerator type and operator in graph template, SliceScheduler maintains a linear estimator that predicts execution time from operator shape. The input features are symbolic shape variables and shapederived terms that capture both compute cost and tensor sizes. For example, for a batched matrix multiplication operator with shape parameters (𝑏, 𝑚, 𝑛, 𝑘), where 𝑏 denotes batch size and 𝑚, 𝑛, and 𝑘 denote matrix dimensions, SliceScheduler uses 𝑡 = 𝛽 1 (𝑏𝑚𝑛𝑘) + 𝛽 2 (𝑏𝑚𝑘) + 𝛽 3 (𝑏𝑘𝑛) + 𝛽 4 (𝑏𝑚𝑛) + 𝛽 5, where 𝑏𝑚𝑛𝑘 captures the dominant compute cost, 𝑏𝑚𝑘 and 𝑏𝑘𝑛 correspond to the sizes of the two input tensors, 𝑏𝑚𝑛 corresponds to the size of the output tensor, and 𝛽 5 captures shape-independent constant overhead. The scheduler continuously collects performance feedback from the operator executor and incorporates them into the corresponding estimators online. As more samples are fed back, the estimators become more accurate. These estimators provide the low-level latency input needed by the global simulator. 3.3.2 Simulator Construction. GMG provides all information about the current cluster state, which enables the construction of a global simulator. Because GMG records the mapping from operators to accelerators, the system knows which issued operators are assigned to each accelerator. This allows the simulator to reconstruct the set of operators currently present in every accelerator. The next step is to infer which operator is currently executing on each accelerator. An issued operator becomes ready once all of its predecessors are done and their outputs are already available in the local HBM. Its ready time is determined by the completion times of local predecessors, and by the arrival times of their transferred outputs for predecessors on other accelerators. Each queue (§3.5.1) is designed to execute at most one operator at a time. Therefore, the operator currently in execution is the issued operator with the earliest 6

SliceScheduler : Global Simulation-Guided Dynamic Operator Scheduling

Conference’17, July 2017, Washington, DC, USA

Figure 6. An example of the construction and simulation of the global simulator. ready time. Once the start time of an operator is known, its completion time can be immediately predicted using the operator estimator. This provides the timing information needed to drive subsequent timeline evolution. Moreover, the simulator can infer tensor residency in HBM. For any ready operator, all of its predecessor outputs must already be available on the accelerator to support the execution of the ready operator. For the operator currently executing, its output must also have been allocated in HBM. Based on these ready and executing operators, the simulator can determine which tensors reside in HBM on each accelerator to infer current HBM usage. Accordingly, given a GMG snapshot at any time, the system can reconstruct the contents of every accelerator queue at that instant, including execution state and HBM occupancy. This further shows that GMG is equivalent to a consistent snapshot of the entire cluster at that moment.

then advances these queues event by event to infer how the cluster evolves over time. This mechanism enables SliceScheduler to assess a candidate operator placement without actually deploying it on the real cluster. SliceScheduler creates a copy of the current GMG, applies the placement to this copy, and then constructs a global simulator based on it. Using this simulator, SliceScheduler derives a placement score from statistics on the simulated completion time of the relevant operators. In essence, it performs a what-if simulation. 3.4

Scheduling Module

SliceScheduler employs an independent scheduling module to orchestrate the execution of batches of unscheduled graph instances. The total number of issued operators is limited to prevent excessive overhead of global simulation. Therefore, it adopts a small-batch incremental scheduling strategy, and frequently invoked in response to both the insertion of new graph instances and runtime feedback. In each scheduling round, the scheduling module calls the incremental simulation-based scheduling algorithm to collect the operators to be scheduled and generate their placement.

3.3.3 Event-Driven Simulation. After reconstructing all accelerator queues from GMG, the simulator advances their states to predict how the cluster evolves over time. It maintains a unified simulated timeline across all accelerators. Specifically, the simulator keeps track of all the running operators in the cluster, together with their predicted completion times. At each step, it selects the earliest-complete operator as the completion event and advances simulated timeline to the complete-time. The simulator then applies the cascading effects of this event. When this operator finishes, one ready operator among those marked as issued in the same queue starts executing. For each newly started operator, the simulator invokes the corresponding estimator to predict its completion time and inserts it into the operator running set. The simulation then proceeds to the next event. By iterating in this manner, the simulator predicts, at operator granularity, both the cluster-wide execution timeline and the evolution of HBM usage over time. Summary. As illustrated in Figure 6, the global simulator operates in two steps. It first reconstructs, from GMG, the operators and dependencies on each accelerator and builds a corresponding queue for each accelerator in the simulator. It

3.4.1 Scheduling Frontiers. To support incremental decisions, SliceScheduler maintains two frontiers on GMG. The scheduled frontier contains operators in state issued or done that have at least one unscheduled successor; these operators act as checkpoints that reside on accelerators for later scheduling. The unscheduled frontier contains operators in state unscheduled whose predecessors are either absent or already issued or done. All their predecessors lie on the scheduled frontier. Together, these frontiers define the current scheduling boundary on GMG. 3.4.2 Incremental Simulation-Based Scheduling. The input to each scheduling round is the current GMG, the unscheduled frontier, and the budget on the number of issued operators. The output is a small batch of operators together with their placement. The key constraint is responsiveness: since SliceScheduler may be invoked frequently, each round must remain lightweight enough that scheduling does not 7

Conference’17, July 2017, Washington, Weinan DC, Liu, USA Zeyuan Ding, Dian Ding, Chengcheng Wan, Lu Tang, Guangtao Xue, Jiwu Shu, and Yiming Zhang

Algorithm 1: Incremental Simulation-Based Scheduling Input: Current GMG, unscheduled frontier 𝐹𝑢 , issued-operator budget 𝐵 Output: Operators to schedule and their placement 1 if number of issued operators in GMG ≥ 𝐵 then 2 return 3 4

Figure 7. An example of a computation graph partition and accelerator assignment. “Compute” refs to as “Comp”.

if 𝐹𝑢 is empty then return

/* Batch Collection. 𝑜𝑝 ← highest-priority operator in 𝐹𝑢 ; 6 B ← CollectConnectedGraph(𝑜𝑝, 𝐵);

*/

/* Simulation-Based Placement. bestScore ← +∞; 8 bestPlacement ← ∅; 9 foreach 𝑝 in CandidatePartitions in parallel do 10 𝐺𝑀𝐺 ′ ← Clone(𝐺𝑀𝐺); 11 ApplyPlacement(𝐺𝑀𝐺 ′, B, 𝑝); 12 sim ← BuildGlobalSimulator(𝐺𝑀𝐺 ′ ); 13 feasible, score ← Simulate(𝑠𝑖𝑚, B); 14 if feasible = true then 15 RecordCandidateResult(𝑝, score);

*/

This scheduling algorithm naturally captures both data locality and SLA priorities. If early operators of a request run on one set of accelerators, and later ones run on another, the required cross-accelerator tensor transfers are explicitly added to the simulated timeline. This raises the predicted completion time of downstream operators. Thus, placements that break locality are automatically disfavored. The algorithm also protects high-priority SLAs: because high-priority operators are more likely to be collected first from the unscheduled frontier, under heavy load low-priority ones may not be collected at all. Meanwhile, the scheduler achieves fine-grained load balancing: when a partition is heavily loaded, its placement becomes less attractive or is ruled out during simulation. Consequently, SliceScheduler does not merely preempt low-priority work on a local accelerator; it performs dynamic scheduling so the entire cluster prioritizes high-priority SLAs.

5

7

16 17

bestPlacement ← BestRecordedCandidateResult(); return B,bestPlacement

3.5

Operator Executor

Finally, the operator executor conducts the inference. We design tensor transfers as regular operators in the per-accelerator queue, and their execution is gated by transfer arbitration.

become a bottleneck. To achieve this, SliceScheduler combines batch collection and simulation-based placement, as summarized in Algorithm 1. Batch collection. SliceScheduler first selects the highestpriority operator from the unscheduled frontier, and then follows its successors to collect a small connected batch of graph instances. As serving requests often form dependency chains across graph instances, this process naturally focuses each round on one high-priority request of a model instance. The batch size is capped to keep scheduling overhead low. Simulation-based placement. Given the collected batch, SliceScheduler evaluates candidate placements over a set of pre-defined accelerator partitions. For each graph template, the mapping of its operators to each candidate partition is also pre-defined. This is possible because inference graphs are regularly decomposable: once a partition is chosen, the internal operator-to-accelerator mapping is fixed. SliceScheduler applies each candidate placement to a cloned GMG, builds a global simulator, and runs what-if simulation in parallel. Placements that lead to OOM are discarded. Among the remaining candidates, SliceScheduler selects the one that minimizes the simulated average operator completion time. After SliceScheduler calls the algorithm to get a placement, SliceScheduler writes the chosen placement back to GMG, issues the corresponding operators to the operator executor, marks them as issued, and updates both frontiers.

3.5.1 Per-Accelerator Operator Queue. Each accelerator maintains a local operator queue as its device-side runtime. The queue executes operators according to data dependencies rather than issuing order. In this way, a computation graph can be partitioned across multiple accelerators (as shown in Figure 7), while each accelerator independently drives the operators placed on it. Each queued operator records the readiness of its input operands and execution state. When an operator is inserted into the queue, it is marked as ready if it has no inputs; otherwise, its input slots are initialized as not ready and the operator remains blocked. Another execution state is activated, which is used to determine whether an operation is permitted to execute. The accelerator keeps listening the ready set. Whenever the device is available, it selects one ready and activated operator and executes it. Each queue runs at most one operator at a time. After an operator completes, its output will be propagated to dependent operators. For each successor, the corresponding input slot is marked ready; once all of its input slots are ready, the successor becomes ready as well. 3.5.2 Tensor Transfer Arbitration. Graph partitioning in SliceScheduler creates remote dependencies, where an operator on one accelerator consumes a tensor produced on another. 8

SliceScheduler : Global Simulation-Guided Dynamic Operator Scheduling

Such dependencies require explicit tensor movement across accelerators. A naive design would let queues invoke point-to-point primitives as soon as source tensors become available. However, these primitives are typically blocking, non-preemptible, and mismatched send/recv ordering across devices can easily create circular waits. Therefore, SliceScheduler does not allow queues to autonomously start cross-accelerator transfers. Instead, SliceScheduler coordinates such transfers through arbitration-managed transfers and an arbitration algorithm.

capture its computation graph. The captured graph is then registered with SliceScheduler as a graph template, and instantiated. In this way, SliceScheduler can be integrated into existing PyTorch-based serving applications with minimal changes to application code. The SliceScheduler master runs on the host CPU and implements cluster-wide scheduling and transfer coordination. Its operator executor is implemented on top of LibTorch [13], and runs on the accelerator side to execute operators and carry out tensor transfers.

Cross-accelerator transfers. Each cross-accelerator transfer is decomposed into three operators: Intent, Recv, and Send. When the source tensor becomes available, the Intent operator notifies SliceScheduler of the pending transfer request. Once the transfer is admitted, SliceScheduler activates Recv on the destination accelerator to allocate the receive buffer. After the buffer is successfully prepared, Recv triggers Send on the source accelerator to initiate the actual data movement. When the reception completes, Recv reports completion back to SliceScheduler. We enforce this Recv-before-Send ordering, as destinationside buffer allocation may temporarily fail and require retries. By delaying Send until Recv succeeds, the sender only invokes the communication primitive when the destination is ready.

5

Evaluation

5.1

Experimental Setup

Hardware. We deploy and evaluate SliceScheduler on a single multi-GPU server. The server is equipped with two Intel Xeon Platinum 8468 CPUs [21] (96 CPU cores in total), 1600 GB of host memory, and eight NVIDIA A16 GPUs [35], each with 64 GB of GPU memory. We use GPU IDs 0 through 7 throughout the evaluation. Baselines. We compare SliceScheduler against an StaticOnline baseline and three GPU-sharing baselines. • Static-Online: Four model instances serve the four online traces separately, each pinned to a fixed GPU pair: (0,1), (2,3), (4,5), and (6,7). • Subset-Share: Priority-aware sharing [44] on a fixed GPU subset. It launches an additional low-priority offline instance on a fixed 4-GPU subset (i.e., GPUs (0,1,2,3)). It opportunistically delays low-priority GPU operators to expose idle slices for other. • Dual-Share: Interference-aware sharing [39]. It launches two additional low-priority offline instances on two 4GPU subsets (i.e., GPUs (0,1,2,3) and (4,5,6,7)). It spreads offline requests across multiple fixed GPU subsets to reduce interference. • Full-Share: Full-server fixed-scope sharing. It launches only one additional low-priority offline instance across all eight GPUs. This single offline workload attempts to exploit idle slices over all the GPUs.

Arbitration algorithm. To coordinate tensor transfers at cluster scope, SliceScheduler maintains a communication graph, separate from GMG, whose vertices represent accelerators and whose edges represent pending transfer intents. When an Intent operator executes, SliceScheduler inserts the corresponding edge into the graph. Because pending transfers may share the same source, share the same destination, or compete for the same communication link, SliceScheduler cannot activate every intent immediately. Instead, it selects a conflict-free set of transfers that can proceed concurrently. For each selected edge, SliceScheduler starts the transfer procedure by activating the destination-side Recv. When receiving a completion feedback, SliceScheduler removes the corresponding edge and releases the associated resources. This arbitration is event-driven. It is triggered by the arrival of a new Intent and the completion feedback of an existing transfer. At each trigger, SliceScheduler re-examines the communication graph and selects a new set of activatable edges. In this way, SliceScheduler avoids deadlocks caused by accelerator-local negotiation while allowing non-conflicting point-to-point transfers to proceed in parallel.

4

Conference’17, July 2017, Washington, DC, USA

We implement these baselines ourselves to capture the key designs for prior works, because existing GPU sharing systems are not always publicly available and often differ substantially in workload assumptions and runtime mechanisms Metrics. We use the following metrics. • Request throughput: average number of requests processed per second during execution. • Token throughput: average number of output tokens generated per second. • TTFT (time to first token): the elapsed time from the moment a request arrives to the moment the first output token is produced; it therefore includes both queuing delay and prefill computation time.

Implementation

We implement SliceScheduler in three layers: the serving application interface, the SliceScheduler master, and the operator executor. At the interface level, we integrate SliceScheduler into PyTorch as a custom backend. Specifically, when a module is executed for the first time, we use TorchDynamo [11] to 9

Conference’17, July 2017, Washington, Weinan DC, Liu, USA Zeyuan Ding, Dian Ding, Chengcheng Wan, Lu Tang, Guangtao Xue, Jiwu Shu, and Yiming Zhang

Table 1. Execution time for running 1,000 prefills. Relative overhead is computed against Direct Execution.

• SLO attainment: the p90 TTFT of the Static-Online as the threshold: it is the fraction of online requests whose TTFT is below this threshold. • GPU Utilization: the fraction of a time window occupied by operator-execution slices on the GPU. • Simulation throughput: The number of operators simulated per millisecond in the simulator.

Execution Mode Direct Execution SliceScheduler Eager Execution

Inference workloads. We adapt the official Llama3-8B model [31] to run with SliceScheduler. The online inference workload is driven by four representative one-day traces introduced in §2.1, which emulate the dynamic request patterns in deployment. We replay the trace segment from 19:00 to 19:30, which is a representative interval with both busy and idle periods. For offline inference, we issue one request per second, each with an input length of 2048 tokens and a fixed output length of 15 tokens. This setting represents a practical lightweight offline inference workload in production. Operator granularity. A single inference/training graph execution typically involves thousands to tens of thousands of ATen ops [9]. If each ATen op were treated as a scheduling unit, the scheduling overhead would be prohibitive. Therefore, we coarsen the scheduling granularity by merging the forward or backward computation of each layer into one operator, and use layers as the scheduling unit in SliceScheduler. 5.2

Time (s) 23.39 23.37 25.27

Relative Overhead 0.0% 8%

whole cluster. While the GPU-sharing baselines already incorporate priority-aware [44] co-location, their fixed resource scope still limits their ability to preserve online performance under fragmented idle slices. In contrast, SliceScheduler combines priority-aware scheduling with cluster-wide operatorlevel remapping, allowing it to better protect high-priority online requests even in the presence of offline workloads. At the same time, SliceScheduler achieves higher throughput and GPU utilization than all baselines, with the gains mainly coming from the throughput contributed by offline work and from opportunistic inserting offline requests into idle slices. Compared with Full-Share, SliceScheduler improves request throughput by 49%. The main reason is that, although Full-Share also allows an offline workload to span the whole machine, SliceScheduler additionally performs automatic load balancing, which increases the duration of overlapping idle slices across multiple GPUs and thus improves the effective utilization of multi-GPU offline execution. Compared with Subset-Share and Dual-Share, SliceScheduler improves throughput by about 9%–37%. The reason is that existing GPU sharing approaches [39, 44] typically colocated low-priority work on a fixed GPU scope, whereas SliceScheduler performs cluster-wide dynamic scheduling and can therefore exploit idle slices from a much larger resource pool.

Online/Offline Co-location Throughput

To evaluate the effectiveness of dynamic scheduling in exploiting idle slices, we assess SliceScheduler in an online/offline co-location setting. In this setting, SliceScheduler runs with both online and offline requests admitted to the system. The online inference workload generates idle slices, while the offline workload attempts to fill these slices and convert them into useful throughput. We assign a higher execution priority to operators from the online workload than to those from the offline workload. Figure 8 shows the results. Overall, SliceScheduler improves SLO attainment by about 9% over all baselines, increases request throughput by 9%–129%, improves token throughput by 10%–129%, and raises GPU utilization by 17%–38%. GPU utilization is generally low in this experiment because the selected trace segment is relatively light, and the admitted offline workload is intentionally lightweight as well. Nevertheless, the observed SLO improvement shows that the trace still contains periods of substantial contention. We next demonstrate that, by admitting additional offline workload into these fragmented slack periods, SliceScheduler can further improve utilization while preserving online performance. Importantly, these throughput gains do not come at the expense of online service quality. Compared with all baselines, This improvement comes from breaking container-level isolation and enabling finer-grained load balancing across the

5.3

Overhead of SliceScheduler

We evaluate the overhead introduced by the SliceScheduler. To minimize the actual computation time and thereby make system overhead more visible, we run 1000 prefill executions with a context length of 1 on a single GPU and measure the total execution time. We consider three execution modes. (i) Direct Execution executes the inference graph directly and controls the GPU without any intermediate system layer; it therefore serves as the overhead baseline. (ii) SliceScheduler executes the same inference graph through the SliceScheduler scheduling layer on a single GPU. (iii) Eager Execution runs the workload directly from the user program. Table 1 shows the results. The execution time of SliceScheduler is almost identical to that of Direct Execution, indicating that the operator scheduling layer adds negligible runtime overhead beyond the direct execution path. For reference, SliceScheduler is 8% faster than Eager Execution, 10

0.54

0.82 0.89

1.12 1.23

Full-Share

20 10

0

8.08

12.35 13.44

Subset-Share 16.82 18.51

SLO

1

Token / s

Requests / s

Static-Online

0 (a) Request throughput.

Conference’17, July 2017, Washington, DC, USA

Dual-Share

SliceScheduler 98.9%

1.0 90.0% 90.7% 89.9% 90.4%

Utilization

SliceScheduler : Global Simulation-Guided Dynamic Operator Scheduling

0.8 (b) Token throughput.

56.5% 0.6 41.9% 44.1% 48.2% 40.7% 0.4 0.2 0.0

(c) SLO attainment.

(d) GPU utilization.

 

5HDO (VWLPDWHG

Table 2. Average training time per one iteration of Llama3-8B on dual GPUs and simulation error rate.

  

Method Real Ours SimAI

5HDO (VWLPDWHG

Sim. Time (ms)

 .% 0% 0% 0% EZ EZ EZ EZ EZ (a) Execution-time samples and pre- (b) Transfer-bandwidth samples and dictions for representative operators. predictions for representative tensor sizes. 

Figure 9. Prediction accuracy of the operator and transfer estimators.

mainly because it avoids Python interpreter overhead in eager mode [14]. Overall, these results show that SliceScheduler remains close to the lower-level execution path while adding little extra cost of its own. 5.4

Time (s) 1.910 1.945 1.517

40 30 20 10 0

2000

4000

6000

Number of Operators (a) Global simulator

Sim. Time (ms)

7LPHPV



%DQGZLGWK*%V

Figure 8. Performance comparison of SliceScheduler and baselines.

Error Rate 1.83% 20.58%

10000 7500 5000 2500 0

200

400

600

Number of Operators (b) SimAI

Figure 10. Simulation time versus simulated operators for our global simulator and SimAI. "Sim." refers to "Simulation".

Accuracy and Throughput of Global Simulator We observe that operator execution time is highly stable across iterations, and tensor-transfer bandwidth is also relatively stable. The coefficient of variation is 0.62% for operator samples and 1.63% for transfer samples. As a result, the predictions produced by these estimators are strongly correlated with the measured execution time. The mean absolute percentage error of the operator and transfer estimators is 0.32% and 0.92%, respectively. These results validate the use of linear regression to predict both operator execution time and tensor-transfer cost.

To evaluate whether our simulator can effectively support dynamic scheduling, we focus on simulation accuracy and throughput. To the best of our knowledge, we are the first fast cluster-wide simulator designed for dynamic scheduling in multi-tenant AI clusters. Therefore, we adopt SimAI [40] as our baseline, which is the most closely-related state-of-the-art solution. Since SimAI is primarily designed for training workloads, we use the Llama3-8B training computation graph to evaluate both SimAI and our global simulator. We first statically map the training graph onto two GPUs with a pipeline parallelism configuration of 𝑃𝑃 = 2, and run it for 256 iterations to allow the estimators to collect runtime data, including operator execution time, tensor transfer time and the end-to-end pertraining time. Using these collected data, we construct an empty global simulator, putting the same statically mapped training graph into the simulator’s execution queue. When the simulator executes, we collect the simulation throughput and the simulated execution time of each training iteration.

5.4.2 End-to-end accuracy. Table 2 summarizes the actual and predicted end-to-end execution time of one training iteration. Our global simulator achieves an average error rate of only 1.83%, showing that operator-granularity simulation can accurately characterize the cluster-wide execution of operators. In comparison, SimAI has an average error rate of 20.58%. The reason is that it does not use estimators that continuously learn from runtime feedback, while SliceScheduler incrementally refines both operator and transfer performance estimators during execution.

5.4.1 SliceScheduler estimator accuracy. Figure 9 compares real and estimated execution times for backward operators in the upper half layers, as well as real and estimated transfer latencies for several representative tensors.

5.4.3 Simulation throughput. We measured the simulation throughput of our global simulator. 11

Conference’17, July 2017, Washington, Weinan DC, Liu, USA Zeyuan Ding, Dian Ding, Chengcheng Wan, Lu Tang, Guangtao Xue, Jiwu Shu, and Yiming Zhang

of 𝑡 = 0.1, the above analysis yields 𝑁 ≈ 62. This suggests SliceScheduler can scale to clusters with up to about 64 GPUs. In practice, we tune the scheduling volume 𝑣 and prediction horizon 𝑙 offline. The average operator granularity is controlled by empirically grouping LLM layers into scheduling units. Adding the number of accelerators, SliceScheduler can estimate the number of operators simulated in each scheduling round. This estimate is then used to cap the number of issued operators maintained in GMG, ensuring SliceScheduler remains practical for small to medium-scale clusters.

For the global simulator, we accumulate different numbers of un-simulated operators and then run the simulation to measure the simulation time, from which we derive the simulation throughput. As shown in Figure 10 (a), the simulator processes on average ∼176.8 operators per millisecond. For SimAI, we also simulate models of different sizes to obtain the equivalent number of simulated operators and the corresponding simulation time. As shown in Figure 10 (b), SimAI processes on average ∼0.065 operators per millisecond. Thus, the global simulator achieves about four orders of magnitude higher simulation throughput than SimAI. This improvement stems from the different goals of the two simulators: our simulator de-emphasizes traffic scheduling, which significantly reduces simulation complexity. 5.5

6

Related Work

Job scheduling and elasticity. Cluster schedulers such as Kubernetes [17], Ray [32], and Firmament [15] schedule application processes or containers in the cluster. Such systems operate at the granularity of processes rather than the code directly executed on GPUs, making the scheduling unit too heavyweight to exploit large numbers of transient idle slices. To handle changing workload demand, prior work introduces elasticity mechanisms [4, 12, 27, 28, 38, 48] to re-assign resources to the job. However, due to the heavyweight of the scheduling payload, elasticity incurs substantial overhead. As a result, these approaches are ill-suited to the highly transient and fine-grained idle slices targeted by SliceScheduler. GPU sharing. A large body of work improves utilization by allowing multiple jobs to share one GPU [7, 18, 33, 34, 39, 44]. However, they primarily operate within the scope of a single GPU or a fixed GPU subset, and do not fully exploit the complementary idle slices distributed across GPUs at cluster scale. As a result, handling fragmented idle slices across the cluster requires global scheduling. SliceScheduler complements GPU-sharing approaches by introducing operator-level, cluster-wide scheduling to reclaim such idle slices. Simulation. Prior simulators mainly target either local hardware behavior or large-scale distributed execution. Microarchitectural simulators [5, 25] provide cycle-level modeling of processors and GPU kernels, but they focus on intraoperator behavior and are far too slow for cluster-scale scheduling. At a higher level, distributed and network simulators [40, 43] model AI workloads on large clusters. However, their simulation time can still be on the order of hours for realistic workloads, and they do not explicitly reason about HBM occupancy or out-of-memory conditions. In contrast, the SliceScheduler global simulator is designed for dynamic scheduling: it performs fast operator-level simulation while explicitly tracking both execution time and HBM usage. LLM Serving. They typically combine local and global scheduling. Local schedulers [16, 26] manage requests within a fixed model deployment to meet SLA targets, while global schedulers [36] distribute requests across deployments for load balancing. However, global schedulers usually operate at coarse granularity and rely on low-frequency utilization signals. SliceScheduler bridges these two levels: it combines

Scalability of Dynamic Scheduling

To understand the limits of simulation-based dynamic scheduling, we analyze the scalability of SliceScheduler. The benefit of SliceScheduler comes from prediction horizon — a longer prediction window helps identify fine-grained load imbalance and improves placement quality. However, it also increases the number of operators to simulate and thus the cost of each scheduling round. If scheduling takes too long, the cluster keeps executing while the centralized scheduler is still running what-if simulation, making scheduling itself a bottleneck. SliceScheduler must therefore balance decision quality against scheduling timeliness. We focus on four dimensions: • Operator granularity (𝑔): The average execution time of one scheduling unit on an accelerator. Finer granularity means more operators must be scheduled and simulated within the same amount of execution time. • Scheduling volume (𝑣): The total execution time of the operators selected in one scheduling round. • Prediction horizon (𝑙): The future time window simulated in one scheduling round, normalized by the scheduling volume. A larger horizon improves foresight but increases simulation cost. • Scheduling timeliness (𝑡): The ratio between the number of operators executed by the cluster during the scheduling time, and the number of operators scheduled in one round. Smaller is better. When this ratio approaches or exceeds 1, the scheduler becomes a bottleneck and the benefit of dynamic scheduling quickly diminishes. Let the number of accelerators be 𝑁 , the simulation throughput be 𝑠, the operator granularity be 𝑔, the prediction horizon be 𝑙, the scheduling volume be 𝑣, and the scheduling timeli𝑙+1 ness be 𝑡. Therefore, scheduling timeliness is 𝑡 = 𝑁𝑠𝑔 . In our experiment setup, we merge every 8 of the 32 layers of Llama3-8B into one operator. Given an average decode latency of ∼42.3 ms, the resulting operator granularity is 𝑔 = 10.575. Using the measured averaged simulation throughput 𝑠 = 176.8, a prediction horizon of 𝑙 = 3, and a target timeliness 12

SliceScheduler : Global Simulation-Guided Dynamic Operator Scheduling

cluster-wide coordination with fine-grained execution control, and directly uses executable operators, rather than requests or containers, as the scheduling unit. Graph-based scheduling. MapReduce [8] and Spark [45] pioneered graph-based execution by representing applications as computation DAGs and scheduling tasks according to data dependencies. Their abstractions are effective for coarsegrained data analytics workloads, but are not designed for fine-grained GPU execution in AI clusters. SliceScheduler similarly leverages graph structure, but uses GPU executable operators as the scheduling unit and explicitly reasons about accelerator placement, execution timing, and HBM usage.

7

Conference’17, July 2017, Washington, DC, USA Machine Learning on GPUs. In Proceedings of the ACM SIGOPS 31st Symposium on Operating Systems Principles (Lotte Hotel World, Seoul, Republic of Korea) (SOSP ’25). Association for Computing Machinery, New York, NY, USA, 1–17. doi:10.1145/3731569.3764818 [8] Jeffrey Dean and Sanjay Ghemawat. 2008. MapReduce: simplified data processing on large clusters. Commun. ACM 51, 1 (2008), 107–113. [9] The Linux Foundation. 2024. ATen. https://pytorch.org/cppdocs/ #aten [10] The Linux Foundation. 2024. PyTorch. https://pytorch.org/ [11] The Linux Foundation. 2024. torch.compiler. https://pytorch.org/ docs/stable/torch.compiler.html [12] The Linux Foundation. 2025. Torch Distributed Elastic. https://docs. pytorch.org/docs/stable/distributed.elastic.html [13] The Linux Foundation. 2026. PyTorch C++ API. https://docs.pytorch. org/cppdocs/ PyTorch C++ API. https: [14] The Linux Foundation. 2026. //research.google/blog/eager-execution-an-imperative-defineby-run-interface-to-tensorflow/ [15] Ionel Gog, Malte Schwarzkopf, Adam Gleave, Robert NM Watson, and Steven Hand. 2016. Firmament: Fast, centralized cluster scheduling at scale. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16). 99–115. [16] Ruihao Gong, Shihao Bai, Siyu Wu, Yunqian Fan, Zaijun Wang, Xiuhong Li, Hailong Yang, and Xianglong Liu. 2025. Past-Future Scheduler for LLM Serving under SLA Guarantees. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (Rotterdam, Netherlands) (ASPLOS ’25). Association for Computing Machinery, New York, NY, USA, 798–813. doi:10.1145/3676641.3716011 [17] Google. 2024. Kubernetes. https://kubernetes.io/ [18] Cheol-Ho Hong, Ivor Spence, and Dimitrios S Nikolopoulos. 2017. GPU virtualization and scheduling methods: A comprehensive survey. ACM Computing Surveys (CSUR) 50, 3 (2017), 1–37. [19] Qinghao Hu, Peng Sun, Shengen Yan, Yonggang Wen, and Tianwei Zhang. 2021. Characterization and prediction of deep learning workloads in large-scale gpu datacenters. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1–15. [20] Qinghao Hu, Zhisheng Ye, Zerui Wang, Guoteng Wang, Meng Zhang, Qiaoling Chen, Peng Sun, Dahua Lin, Xiaolin Wang, Yingwei Luo, et al. 2024. Characterization of large language model development in the datacenter. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24). 709–729. Intel® Xeon® Platinum 8468 Processor. [21] Intel. 2026. https://www.intel.com/content/www/us/en/products/sku/ 231735/intel-xeon-platinum-8468-processor-105m-cache2-10-ghz/specifications.html [22] Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly. 2007. Dryad: distributed data-parallel programs from sequential building blocks. SIGOPS Oper. Syst. Rev. 41, 3 (March 2007), 59–72. doi:10.1145/1272998.1273005 [23] Suhas Jayaram Subramanya, Daiyaan Arfeen, Shouxu Lin, Aurick Qiao, Zhihao Jia, and Gregory R Ganger. 2023. Sia: Heterogeneity-aware, goodput-optimized ML-cluster scheduling. In Proceedings of the 29th Symposium on Operating Systems Principles. 642–657. [24] Myeongjae Jeon, Shivaram Venkataraman, Amar Phanishayee, Junjie Qian, Wencong Xiao, and Fan Yang. 2019. Analysis of LargeScaleMulti-TenantGPU clusters for DNN training workloads. In 2019 USENIX Annual Technical Conference (USENIX ATC 19). 947–960. [25] Mahmoud Khairy, Zhesheng Shen, Tor M. Aamodt, and Timothy G. Rogers. 2020. Accel-sim: an extensible simulation framework for validated GPU modeling. In Proceedings of the ACM/IEEE 47th Annual International Symposium on Computer Architecture (Virtual Event) (ISCA ’20). IEEE Press, 473–486. doi:10.1109/ISCA45697.2020.

Conclusion

In this paper, we present SliceScheduler, an operator-level scheduling system for reclaiming fine-grained idle slices in multi-tenant AI clusters. By combining the Global Mapping Graph, an event-driven global simulator, simulation-based scheduling, and an operator executor, SliceScheduler improves cluster utilization while preserving online SLAs. Results show SliceScheduler achieves higher throughput and utilization than container-level and GPU-sharing baselines, while introducing negligible runtime overhead.

References [1] Cédric Augonnet, Samuel Thibault, Raymond Namyst, and PierreAndré Wacrenier. 2009. StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures. In Proceedings of the 15th International Euro-Par Conference on Parallel Processing (Delft, The Netherlands) (Euro-Par ’09). Springer-Verlag, Berlin, Heidelberg, 863–874. doi:10.1007/978-3-642-03869-3_80 [2] Cédric Augonnet, Samuel Thibault, Raymond Namyst, and PierreAndré Wacrenier. 2009. StarPU: A Unified Platform for Task Scheduling on Heterogeneous Multicore Architectures. In Proceedings of the 15th International Euro-Par Conference on Parallel Processing (Delft, The Netherlands) (Euro-Par ’09). Springer-Verlag, Berlin, Heidelberg, 863–874. doi:10.1007/978-3-642-03869-3_80 [3] Paul Barham, Aakanksha Chowdhery, Jeff Dean, Sanjay Ghemawat, Steven Hand, Daniel Hurt, Michael Isard, Hyeontaek Lim, Ruoming Pang, Sudip Roy, et al. 2022. Pathways: Asynchronous distributed dataflow for ml. Proceedings of Machine Learning and Systems 4 (2022), 430–449. [4] Zhengda Bian, Shenggui Li, Wei Wang, and Yang You. 2021. Online evolutionary batch size orchestration for scheduling deep learning workloads in GPU clusters. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1–15. [5] Nathan Binkert, Bradford Beckmann, Gabriel Black, Steven K. Reinhardt, Ali Saidi, Arkaprava Basu, Joel Hestness, Derek R. Hower, Tushar Krishna, Somayeh Sardashti, Rathijit Sen, Korey Sewell, Muhammad Shoaib, Nilay Vaish, Mark D. Hill, and David A. Wood. 2011. The gem5 simulator. SIGARCH Comput. Archit. News 39, 2 (Aug. 2011), 1–7. doi:10.1145/2024716.2024718 [6] Brendan Burns, Brian Grant, David Oppenheimer, Eric Brewer, and John Wilkes. 2016. Borg, Omega, and Kubernetes. Commun. ACM 59, 5 (April 2016), 50–57. doi:10.1145/2890784 [7] Patrick H. Coppock, Brian Zhang, Eliot H. Solomon, Vasilis Kypriotis, Leon Yang, Bikash Sharma, Dan Schatzberg, Todd C. Mowry, and Dimitrios Skarlatos. 2025. LithOS: An Operating System for Efficient 13

Conference’17, July 2017, Washington, Weinan DC, Liu, USA Zeyuan Ding, Dian Ding, Chengcheng Wan, Lu Tang, Guangtao Xue, Jiwu Shu, and Yiming Zhang 00047 [26] Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang, and Ion Stoica. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium on Operating Systems Principles. 611–626. [27] Jiamin Li, Hong Xu, Yibo Zhu, Zherui Liu, Chuanxiong Guo, and Cong Wang. 2023. Lyra: Elastic scheduling for deep learning clusters. In Proceedings of the Eighteenth European Conference on Computer Systems. 835–850. [28] Mingzhen Li, Wencong Xiao, Hailong Yang, Biao Sun, Hanyu Zhao, Shiru Ren, Zhongzhi Luan, Xianyan Jia, Yi Liu, Yong Li, et al. 2023. EasyScale: Elastic training with consistent accuracy and improved utilization on GPUs. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1–14. [29] Kshiteej Mahajan, Arjun Balasubramanian, Arjun Singhvi, Shivaram Venkataraman, Aditya Akella, Amar Phanishayee, and Shuchi Chawla. 2020. Themis: Fair and efficient GPU cluster scheduling. In 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20). 289–304. [30] Meta. 2026. Open-source AI Models for Any Application | Llama 3. https://www.llama.com/models/llama-3/ [31] Meta. 2026. The official Meta Llama 3 GitHub site. https://github. com/meta-llama/llama3 [32] Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I Jordan, et al. 2018. Ray: A distributed framework for emerging AI applications. In 13th USENIX symposium on operating systems design and implementation (OSDI 18). 561–577. [33] nvidia. 2025. MIG User Guide. https://docs.nvidia.com/datacenter/ tesla/mig-user-guide/index.html [34] nvidia. 2025. Multi-Process Service. https://docs.nvidia.com/deploy/ mps/index.html [35] Nvidia. 2026. A16 GPU : Take Remote Work to the Next Level. https://www.nvidia.com/en-us/data-center/products/a16-gpu [36] Nvidia. 2026. Scale and Serve Generative AI | NVIDIA Dynamo. https://www.nvidia.com/en-us/ai/dynamo/ [37] Yanghua Peng, Yixin Bao, Yangrui Chen, Chuan Wu, and Chuanxiong Guo. 2018. Optimus: an efficient dynamic resource scheduler for deep learning clusters. In Proceedings of the Thirteenth EuroSys Conference. 1–14. [38] Aurick Qiao, Sang Keun Choe, Suhas Jayaram Subramanya, Willie Neiswanger, Qirong Ho, Hao Zhang, Gregory R Ganger, and Eric P Xing. 2021. Pollux: Co-adaptive cluster scheduling for goodputoptimized deep learning. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21). [39] Foteini Strati, Xianzhe Ma, and Ana Klimovic. 2024. Orion: Interference-aware, fine-grained GPU sharing for ML applications. In Proceedings of the Nineteenth European Conference on Computer Systems. 1075–1092. [40] Xizheng Wang, Qingxu Li, Yichi Xu, Gang Lu, Dan Li, Li Chen, Heyang Zhou, Linkang Zheng, Sen Zhang, Yikai Zhu, Yang Liu, Pengcheng Zhang, Kun Qian, Kunling He, Jiaqi Gao, Ennan Zhai, Dennis Cai, and Binzhang Fu. 2025. SimAI: Unifying Architecture Design and Performance Tuning for Large-Scale Large Language Model Training with Scalability and Precision. In 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 25). USENIX Association, Philadelphia, PA, 541–558. https://www.usenix.org/ conference/nsdi25/presentation/wang-xizheng-simai [41] Qizhen Weng, Wencong Xiao, Yinghao Yu, Wei Wang, Cheng Wang, Jian He, Yong Li, Liping Zhang, Wei Lin, and Yu Ding. 2022. MLaaS in the wild: Workload analysis and scheduling in Large-Scale heterogeneous GPU clusters. In 19th USENIX Symposium on Networked

Systems Design and Implementation (NSDI 22). 945–960. [42] Inc. Wikimedia Foundation. 2025. Gang scheduling. https://en. wikipedia.org/wiki/Gang_scheduling [43] William Won, Taekyung Heo, Saeed Rashidi, Srinivas Sridharan, Sudarshan Srinivasan, and Tushar Krishna. 2023. ASTRA-sim2.0: Modeling Hierarchical Networks and Disaggregated Systems for Largemodel Training at Scale. In 2023 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 283–294. doi:10.1109/ISPASS57527.2023.00035 [44] Wencong Xiao, Shiru Ren, Yong Li, Yang Zhang, Pengyang Hou, Zhi Li, Yihui Feng, Wei Lin, and Yangqing Jia. 2020. AntMan: Dynamic scaling on GPU clusters for deep learning. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 533– 548. [45] Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauly, Michael J Franklin, Scott Shenker, and Ion Stoica. 2012. Resilient distributed datasets: A Fault-Tolerant abstraction for In-Memory cluster computing. In 9th USENIX symposium on networked systems design and implementation (NSDI 12). 15–28. [46] Shiwei Zhang, Lansong Diao, Chuan Wu, Zongyan Cao, Siyu Wang, and Wei Lin. 2024. HAP: SPMD DNN Training on Heterogeneous GPU Clusters with Automated Program Synthesis. In Conference on Computer Systems (EuroSys’ 24). [47] Lianmin Zheng, Zhuohan Li, Hao Zhang, Yonghao Zhuang, Zhifeng Chen, Yanping Huang, Yida Wang, Yuanzhong Xu, Danyang Zhuo, Eric P Xing, et al. 2022. Alpa: Automating inter-and Intra-Operator parallelism for distributed deep learning. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). 559– 578. [48] Pengfei Zheng, Rui Pan, Tarannum Khan, Shivaram Venkataraman, and Aditya Akella. 2023. Shockwave: Fair and efficient cluster scheduling for dynamic adaptation in machine learning. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). 703–723.

14

Related documents

• Global Simulation-Guided Dynamic Operator Scheduling for Efficient Multi-Tenant Model Serving#616902
• Global Simulation-Guided Dynamic Operator Scheduling for Efficient Multi-Tenant Model Serving#616402
• Virtualized Resources Scheduling in Multi-Tenant and Multi-Data Centers Based on Artificial Intelligence Algorithm: A Review#490922
• Towards Multi-Model LLM Schedulers: Empirical Insights into Offloading and Preemption#798900
• Towards Multi-Model LLM Schedulers: Empirical Insights into Offloading and Preemption#797486