Outperforming Multiserver SRPT at All Loads

Izzy Grosof, Daniela Hurtado-Lange · 2025

Read Outperforming Multiserver SRPT at All Loads by Izzy Grosof, Daniela Hurtado-Lange (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-25963.txt.

Introduction

Izzy Grosof and Daniela Hurtado-Lange introduce a scheduling rule that beats a famous benchmark at every load. The setting is a queue with several servers, where jobs of known size arrive over time. SRPT, short for shortest remaining processing time, serves the job closest to done. It is known to be near optimal when the system is almost full. Yet no rule had beaten its multi server version anywhere.

Grosof and Hurtado-Lange propose a variant that, in specific cases, serves large jobs before small ones to keep servers better used. That counterintuitive move lowers the mean response time for later jobs. They prove the gain for all loads and job size patterns, then test a simpler practical version in simulation.

Catalog record

CREATORIzzy Grosof, Daniela Hurtado-Lange
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE123 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-25963

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Outperforming Multiserver SRPT at All Loads Izzy Grosof, Daniela Hurtado-Lange Abstract . A well-designed scheduling policy can unlock significant performance improvements with no additional resources. Multiserver SRPT (SRPT- k k ) is known to achieve asymptotically optimal mean response time in the heavy traffic limit, as load approaches capacity. No better policy is known for the M/G/ k k queue in any regime. We introduce a new policy, SRPT-Except- k + 1 k+1 & Modified SRPT (SEK-SMOD), which is the first policy to provably achieve lower mean response time than SRPT- k k . SEK-SMOD outperforms SRPT- k k across all loads and all job size distributions. The key idea behind SEK-SMOD is to prioritize large jobs over small jobs in specific scenarios to improve server utilization, and thereby improve the response time of subsequent jobs in expectation. Our proof is a novel application of hybrid worst-case and stochastic techniques to relative analysis, where we analyze the deviations of our proposed SEK-SMOD policy away from the SRPT- k k baseline policy. Furthermore, we design Practical-SEK (a simplified variant of SEK-SMOD) and empirically verify the improvement over SRPT- k k via simulation. 1. Introduction The question of reducing wait times with limited resources is ubiquitous in operations and engineering. In particular, strategic scheduling is known to be an effective way to substantially reduce the average time a job spends in the system (and, consequently, the customer waiting time) without incrementing the number of servers. This effectiveness has been observed in various practical applications. In ( Bray et al. 2016 ) , the authors study delays in cases handled by a courthouse in Italy. Specifically, they design a case-level scheduling policy in which judges estimate the number of hearings needed for each case and schedule all hearings in advance, prioritizing those for cases nearing completion. Compared to the old scheduling policy (where judges scheduled each hearing after completing the previous one), the courthouse reduced average case duration by approximately 12% without increasing resources or the number of judges. Similar scheduling policies have been implemented in multiple courthouses afterward, with comparable results. See, for example, ( Azaria et al. 2023 ; Azaria et al. 2024 ) . In computer systems, designing algorithms that minimize response time without adding more resources is essential, as the number of CPUs and GPUs available is typically constant and costly to increase. For example, one can think of a single machine with a fixed number of cores and a limited budget to process tasks. Moreover, this single machine accurately estimates the sizes of arriving tasks. Hence, it can use this information to schedule strategically. For the rest of this paper, we mainly consider this example as an immediate application. Some examples of the importance of scheduling in computer systems with limited resources are the research in ( Kulkarni and Fuller 2011 ; Zhuravlev et al. 2012 ) . One of the most popular scheduling policies in the literature is First-Come-First-Served (FCFS), where the jobs are processed in order of arrival. This policy is simple to implement and is often considered fair. Due to its simplicity, its analysis is tractable, and has been studied for decades ( Loulou 1973 ; Köllerström 1974 ; Köllerström 1979 ; Grosof et al. 2022 ) . However, FCFS does not utilize servers strategically: both long and short jobs receive the same priority. Hence, it does not perform well in terms of response time. If one prioritizes shorter jobs over longer ones, the mean response time decreases significantly. Specifically, one can schedule jobs according to the amount of work remaining to complete them, and preemptively process jobs with the Shortest-Remaining-Processing-Time (SRPT) first. For decades, SRPT has been the gold standard for scheduling jobs in single-server queues, as it minimizes the mean response time ( Schrage 1968 ) . However, optimal scheduling for multiple-server systems is much less understood. A generalization of SRPT to systems with k servers (called SRPT- k ) is studied in ( Grosof et al. 2019b ) , where the k jobs with the least remaining processing time are scheduled. If there are fewer than k jobs available, some of the servers are idle. As expected, SRPT- k performs great in terms of the mean response time. However, it has only been proven to minimize this metric in heavy traffic. A long-lasting open question in the literature is the existence of a scheduling policy that outperforms SRPT- k . In this paper, we answer positively with our policy SRPT-Except- k+1 & Modified SRPT (SEK-SMOD). The contributions of this paper are: (1) We devise and introduce the SEK-SMOD policy, which is defined in reference to a coupled SRPT- k system, in Section 3.1 . (2) We prove that SEK-SMOD achieves a smaller mean response time compared to SRPT- k under all loads, all job size distributions, and all numbers of servers k\geq 2 ( Theorem 4.1 ). (3) We develop a proof method based on a strategic combination of worst-case scenarios and stochastic analysis, as well as relative analysis. We discuss the proof philosophy in Section 1.2 , the proof outline in Section 4.1 , and give the proof in Section 5 (stochastic analysis) and Section 6 (worst case analysis). (4) We propose the Practical SEK policy (a simplified variant of the SEK-SMOD policy) and empirically demonstrate that it outperforms SRPT- k , via simulation, in Section 7 . 1.1. Challenges in beating SRPT-k It is well known in the literature that SRPT minimizes the mean response time in single-server queues with known job sizes ( Schrage 1968 ) , for any load. Further, the multiserver SRPT- k policy has recently been proven to minimize the mean response time in heavy traffic ( Grosof et al. 2019b ) . SRPT- k also minimizes total response time for all jobs in a no-arrivals (batch) setting. The proof is available in ( Graham et al. 1979 ) , by combining prior results ( Conway et al. 1967 ; McNaughton 1959 ) . As a consequence, a scheduling policy that performs better than SRPT- k needs to focus on moderate load. An important pathway for improving upon SRPT- k is rearranging the order in which jobs are served to improve future parallelism. SRPT- k finishes the smallest jobs first, leaving only a few large jobs. As a result, it reaches states where it cannot fully utilize its servers sooner than other policies. Taking advantage of future parallelism requires a global view of the state of the system: Is the system close to empty, with just a few jobs left, or are plenty of jobs present? In contrast, existing multiserver scheduling analysis has overwhelmingly focused on index policies, where each job is evaluated in isolation to produce an index, and the k jobs of best index are served. Existing analyses for multiserver index policies include FCFS- k ( Loulou 1973 ; Köllerström 1974 ; Köllerström 1979 ; Grosof et al. 2022 ) , class-based priority policies ( Sleptchenko et al. 2005 ) , SRPT- k and related index policies ( Grosof et al. 2019b ) , M-Gittins- k and M-SERPT- k ( Scully et al. 2021 ) , and Gittins- k ( Scully et al. 2020

Read the complete text