Is the GPU Half-Empty or Half-Full? Practical Scheduling Techniques for LLMs

• URL: http://arxiv.org/abs/2410.17840v2
• Date: Tue, 28 Jan 2025 09:09:32 GMT
• Title: Is the GPU Half-Empty or Half-Full? Practical Scheduling Techniques for LLMs
• Authors: Ferdi Kossmann, Bruce Fontaine, Daya Khudia, Michael Cafarella, Samuel Madden,
• Abstract summary: We survey scheduling techniques from the literature and from practical serving systems. We find that schedulers from the literature often achieve good performance but introduce significant complexity. In contrast, schedulers in practical deployments often leave easy performance gains on the table but are easy to implement, deploy and configure.
• Score: 3.7758841366694353
• License:
• Abstract: Serving systems for Large Language Models (LLMs) improve throughput by processing several requests concurrently. However, multiplexing hardware resources between concurrent requests involves non-trivial scheduling decisions. Practical serving systems typically implement these decisions at two levels: First, a load balancer routes requests to different servers which each hold a replica of the LLM. Then, on each server, an engine-level scheduler decides when to run a request, or when to queue or preempt it. Improved scheduling policies may benefit a wide range of LLM deployments and can often be implemented as "drop-in replacements" to a system's current policy. In this work, we survey scheduling techniques from the literature and from practical serving systems. We find that schedulers from the literature often achieve good performance but introduce significant complexity. In contrast, schedulers in practical deployments often leave easy performance gains on the table but are easy to implement, deploy and configure. This finding motivates us to introduce two new scheduling techniques, which are both easy to implement, and outperform current techniques on production workload traces.

Related papers

• Plan-over-Graph: Towards Parallelable LLM Agent Schedule [53.834646147919436]
  Large Language Models (LLMs) have demonstrated exceptional abilities in reasoning for task planning. This paper introduces a novel paradigm, plan-over-graph, in which the model first decomposes a real-life textual task into executable subtasks and constructs an abstract task graph. The model then understands this task graph as input and generates a plan for parallel execution.
  arXiv  Detail & Related papers  (2025-02-20T13:47:51Z)
• Autellix: An Efficient Serving Engine for LLM Agents as General Programs [59.673243129044465]
  Large language model (LLM) applications are evolving beyond simple chatbots into dynamic, general-purpose agentic programs. Existing LLM serving systems ignore dependencies between programs and calls, missing significant opportunities for optimization. We introduce Autellix, an LLM serving system that treats programs as first-class citizens to minimize their end-to-end latencies.
  arXiv  Detail & Related papers  (2025-02-19T18:59:30Z)
• Multi-Bin Batching for Increasing LLM Inference Throughput [19.652542432683234]
  Large language models (LL) grow in popularity improving the efficiency of their systems. requests is a critical step in scheduling jobs on servers. requests often have varying generation lengths, causing resource underutilization. We formalize this problem from a queueing-theoretic perspective, and aim to design a throughput control policy.
  arXiv  Detail & Related papers  (2024-12-03T03:16:12Z)
• Interactive and Expressive Code-Augmented Planning with Large Language Models [62.799579304821826]
  Large Language Models (LLMs) demonstrate strong abilities in common-sense reasoning and interactive decision-making. Recent techniques have sought to structure LLM outputs using control flow and other code-adjacent techniques to improve planning performance. We propose REPL-Plan, an LLM planning approach that is fully code-expressive and dynamic.
  arXiv  Detail & Related papers  (2024-11-21T04:23:17Z)
• Don't Stop Me Now: Embedding Based Scheduling for LLMs [22.099820814682513]
  Size-based scheduling algorithms like Shortest Remaining Process Time (SRPT) aim to reduce average request completion time. We propose a prediction-based SRPT variant with limited preemption designed to account for memory overhead in LLM systems.
  arXiv  Detail & Related papers  (2024-10-01T19:51:07Z)
• Efficient LLM Scheduling by Learning to Rank [19.33941579312897]
  We show that it is possible to predict the relative ranks of output lengths in a batch of requests, using learning to rank. We develop a novel scheduler for LLM inference and serving that can approximate the shortest-job-first (SJF) schedule better than existing approaches.
  arXiv  Detail & Related papers  (2024-08-28T13:35:54Z)
• Preble: Efficient Distributed Prompt Scheduling for LLM Serving [8.706905652975554]
  This paper proposes Preble, the first distributed LLM serving platform that targets and optimize for prompt sharing. We designed a distributed scheduling system that co-optimizes KV state reuse and computation load-balancing with a new scheduling algorithm and a hierarchical scheduling mechanism. Our evaluation of Preble with real workloads and request arrival patterns on two open-source LLMs shows that Preble outperforms the SOTA serving systems by 1.5X to 14.5X on average latency and 2X to 10X on p99 latency.
  arXiv  Detail & Related papers  (2024-05-08T06:30:58Z)
• Partitioning Distributed Compute Jobs with Reinforcement Learning and Graph Neural Networks [58.720142291102135]
  Large-scale machine learning models are bringing advances to a broad range of fields. Many of these models are too large to be trained on a single machine, and must be distributed across multiple devices. We show that maximum parallelisation is sub-optimal in relation to user-critical metrics such as throughput and blocking rate.
  arXiv  Detail & Related papers  (2023-01-31T17:41:07Z)
• Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling [18.286430978487388]
  We deal with a challenging scheduling problem on parallel machines with sequence-dependent setup times and release dates. We put the individual machine spans in non-ascending order and lexicographically minimise the resulting robustnesss. Our experimental results show that ASP is indeed a promising KRR paradigm for this problem and is competitive with state-of-the-art CP and MIP solvers.
  arXiv  Detail & Related papers  (2022-12-18T12:43:24Z)
• Multi-Job Intelligent Scheduling with Cross-Device Federated Learning [65.69079337653994]
  Federated Learning (FL) enables collaborative global machine learning model training without sharing sensitive raw data. We propose a novel multi-job FL framework, which enables the training process of multiple jobs in parallel. We propose a novel intelligent scheduling approach based on multiple scheduling methods, including an original reinforcement learning-based scheduling method and an original Bayesian optimization-based scheduling method.
  arXiv  Detail & Related papers  (2022-11-24T06:17:40Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  We consider the problem of scheduling in constrained queueing networks with a view to minimizing packet delay. We use a policy gradient based reinforcement learning algorithm that produces a scheduler that performs better than the available atomic policies.
  arXiv  Detail & Related papers  (2021-05-01T10:18:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.