heSRPT: Parallel Scheduling to Minimize Mean Slowdown
Preprint
Abstract
Modern data centers serve workloads which are capable of exploiting parallelism. When a job parallelizes across multiple servers it will complete more quickly, but jobs receive diminishing returns from being allocated additional servers. Because allocating multiple servers to a single job is inefficient, it is unclear how best to allocate a fixed number of servers between many parallelizable jobs. This paper provides the first optimal allocation policy for minimizing the mean slowdown of parallelizable jobs of known size when all jobs are present at time 0. Our policy provides a simple closed form formula for the optimal allocations at every moment in time. Minimizing mean slowdown usually requires favoring short jobs over long ones (as in the SRPT policy). However, because parallelizable jobs have sublinear speedup functions, system efficiency is also an issue. System efficiency is maximized by giving equal allocations to all jobs and thus competes with the goal of prioritizing small jobs. Our optimal policy, high-efficiency SRPT (heSRPT), balances these competing goals. heSRPT completes jobs according to their size order, but maintains overall system efficiency by allocating some servers to each job at every moment in time. Our results generalize to also provide the optimal allocation policy with respect to mean flow time. Finally, we consider the online case where jobs arrive to the system over time. While optimizing mean slowdown in the online setting is even more difficult, we find that heSRPT provides an excellent heuristic policy for the online setting. In fact, our simulations show that heSRPT significantly outperforms state-of-the-art allocation policies for parallelizable jobs.Keywords
All Related Versions
- Version 1, 2020-11-18, ArXiv
- Published version: Performance Evaluation, 144.
This publication has 26 references indexed in Scilit:
- Delay asymptotics and bounds for multitask parallel jobsQueueing Systems, 2019
- A Model-Based Approach to Streamlining Distributed Training for Asynchronous SGD2018
- Towards realizing the potential of malleable jobs2014
- Oblivious algorithms for multicores and networks of processorsJournal of Parallel and Distributed Computing, 2013
- The Complexity of Scheduling for p-Norms of Flow and StretchLecture Notes in Computer Science, 2013
- Join-Idle-Queue: A novel load balancing algorithm for dynamically scalable web servicesPerformance Evaluation, 2011
- Supporting Malleability in Parallel Architectures with Dynamic CPUSETsMapping and Dynamic MPI2010
- Greedy multiprocessor server schedulingOperations Research Letters, 2005
- Scheduling in the darkTheoretical Computer Science, 2000
- An approximation for the mean response time for shortest queue routing with general interarrival and service timesPerformance Evaluation, 1993