PDL ABSTRACT

SRPT for Multiserver Systems

Performance Evaluation, vol. 127-128, Nov. 2018, pp. 154-175. Also in 36th International Symposium on Computer Performance, Modeling, Measurements, and Evaluation (Performance 2018), Toulouse, France, December 2018.

BEST STUDENT PAPER AWARD!

Isaac Grosof, Ziv Scully, Mor Harchol-Balter

Carnegie Mellon University

http:\\www..pdl.cmu.edu

The Shortest Remaining Processing Time (SRPT) scheduling policy and its variants have been extensively studied in both theoretical and practical settings. While beautiful results are known for single-server SRPT, much less is known for multiserver SRPT. In particular, stochastic analysis of the M/G/k under SRPT is entirely open. Intuition suggests that multiserver SRPT should be optimal or near-optimal for minimizing mean response time. However, the only known analysis of multiserver SRPT is in the worst-case adversarial setting, where SRPT can be far from optimal. In this paper, we give the first stochastic analysis bounding mean response time of the M/G/k under SRPT. Using our response time bound, we show that multiserver SRPT has asymptotically optimal mean response time in the heavy-traffic limit. The key to our bounds is a strategic combination of stochastic and worst-case techniques. Beyond SRPT, we prove similar response time bounds and optimality results for several other multiserver scheduling policies.

FULL PAPER: pdf

 

 

 

© 2019. Legal Info.
Last updated 11 April, 2019