Asymptotically Optimal Scheduling of Multiple Parallelizable Job Classes

References

• Agrawal K, Leiserson CE, He Y, Hsu WJ (2008) Adaptive work-stealing with parallelism feedback. ACM Trans. Comput. Systems 26(3):1–32.Google Scholar
• Agrawal K, Li J, Lu K, Moseley B (2016) Scheduling parallel DAG jobs online to minimize average flow time. Krauthgamer R, ed. Proc. Twenty-Seventh Annual ACM-SIAM Sympos. Discrete Algorithms (SODA 2016) (Society for Industrial and Applied Mathematics, Philadelphia), 176–189. Google Scholar
• Atar R (2012) A diffusion regime with nondegenerate slowdown. Oper. Res. 60(2):490–500.Link, Google Scholar
• Ayesta U, Prabhu B, Righter R (2020) Scheduling in a single-server queue with state-dependent service rates. Probab. Engrg. Inform. Sci. 34(4):507–521.Google Scholar
• Berg B, Dorsman J, Harchol-Balter M (2018) Towards optimality in parallel scheduling. Proc. ACM Measurement Analysis Comput. Systems 1(2):1–30.Google Scholar
• Berg B, Vesilo R, Harchol-Balter M (2020a) heSRPT: Parallel scheduling to minimize mean slowdown. Performance Evaluation 144:102–147.Google Scholar
• Berg B, Harchol-Balter M, Moseley B, Wang W, Whitehouse J (2020b) Optimal resource allocation for elastic and inelastic jobs. Proc. 32nd ACM Sympos. Parallelism Algorithms Architectures (ACM, New York), 75–87.Google Scholar
• Berg B, Whitehouse J, Moseley B, Wang W, Harchol-Balter M (2022) The case for phase-aware scheduling of parallelizable jobs. ACM SIGMETRICS Performance Evaluation Rev. 49(3):65–66.Google Scholar
• Bertsimas D, Paschalidis IC, Tsitsiklis JN (1994) Optimization of multiclass queueing networks: Polyhedral and nonlinear characterizations of achievable performance. Ann. Appl. Probab. 4(1):43–75.Google Scholar
• Blumofe RD, Leiserson CE (1999) Scheduling multithreaded computations by work stealing. J. ACM 46(5):720–748.Google Scholar
• Chen J, Jindel S, Walzer R, Sen R, Jimsheleishvilli N, Andrews M (2016) The memsql query optimizer: A modern optimizer for real-time analytics in a distributed database. Proc. VLDB Endowment 9(13):1401–1412.Google Scholar
• Delgado P, Didona D, Dinu F, Zwaenepoel W (2018) Kairos: Preemptive data center scheduling without runtime estimates. Proc. ACM Sympos. Cloud Comput. (ACM, New York), 135–148.Google Scholar
• Duran S, Ayesta U, Verloop I (2022) On the Whittle index of Markov modulated restless bandits. Queueing Systems 102(3–4):373–430.Google Scholar
• Edmonds J (1999) Scheduling in the dark. Proc. 31st Annual ACM Sympos. Theory Comput. (ACM, New York), 179–188.Google Scholar
• Eryilmaz A, Srikant R (2012) Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Systems 72(3):311–359.Google Scholar
• Grosof I, Harchol-Balter M, Scheller-Wolf A (2020) Stability for two-class multiserver-job systems. Preprint, submitted October 1, https://arxiv.org/abs/2010.00631.Google Scholar
• Grosof I, Harchol-Balter M, Scheller-Wolf A (2022a) WCFS: A new framework for analyzing multiserver systems. Queueing Systems 102(1–2):143–174.Google Scholar
• Grosof I, Scully Z, Harchol-Balter M (2018) SRPT for multiserver systems. Performance Evaluation 127:154–175.Google Scholar
• Grosof I, Scully Z, Harchol-Balter M, Scheller-Wolf A (2022b) Optimal scheduling in the multiserver-job model under heavy traffic. Proc. ACM Measurement Analysis Comput. Systems 6(3):1–32.Google Scholar
• Gupta V, Walton N (2019) Load balancing in the nondegenerate slowdown regime. Oper. Res. 67(1):281–294.Link, Google Scholar
• Gupta A, Acun B, Sarood O, Kalé LV (2014) Towards realizing the potential of malleable jobs. Proc. IEEE 21st Internat. Conf. High Performance Comput. (IEEE Computer Society, Washington, DC), 1–10.Google Scholar
• Halfin S, Whitt W (1981) Heavy-traffic limits for queues with many exponential servers. Oper. Res. 29(3):567–588.Link, Google Scholar
• Harchol-Balter M (2013) Performance Modeling and Design of Computer Systems: Queueing Theory in Action (Cambridge University Press, Cambridge, UK).Google Scholar
• Harchol-Balter M (2022) The multiserver job queueing model. Queueing Systems 100(3):201–203.Google Scholar
• Hill MD, Marty MR (2008) Amdahl’s law in the multicore era. Computer 41:33–38.Google Scholar
• Hong Y, Wang W (2022) Sharp waiting-time bounds for multiserver jobs. Proc. Twenty-Third Internat. Sympos. Theory Algorithmic Foundations Protocol Design Mobile Networks Mobile Comput. (ACM, New York), 161–170. Google Scholar
• Jayaram Subramanya S, Arfeen D, Lin S, Qiao A, Jia Z, Ganger GR (2023) Sia: Heterogeneity-aware, goodput-optimized ML-cluster scheduling. Flinn J, Seltzer MI, Druschel P, Kaufmann A, Mace J, eds. Proc. 29th Sympos. Operating Systems Principles (ACM, New York), 642–657. Google Scholar
• Leis V, Boncz P, Kemper A, Neumann T (2014) Morsel-driven parallelism: A NUMA-aware query evaluation framework for the many-core age. Dyreson C, ed. Proc. 2014 ACM SIGMOD Internat. Conf. Management Data (ACM, New York), 743–754.Google Scholar
• Lin M, Wierman A, Zwart B (2010) The average response time in a heavy-traffic SRPT queue. ACM SIGMETRICS Performance Evaluation Rev. 38(2):12–14.Google Scholar
• Lin S-H, Paolieri M, Chou C-F, Golubchik L (2018) A model-based approach to streamlining distributed training for asynchronous sgd. 2018 IEEE 26th Internat. Sympos. Modeling Anal. Simulation Comput. Telecomm. Systems (MASCOTS) (IEEE Computer Society, Washington, DC), 306–318.Google Scholar
• Liu X, Ying L (2020) Steady-state analysis of load-balancing algorithms in the sub-Halfin–Whitt regime. J. Appl. Probab. 57(2):578–596.Google Scholar
• Qiao A, Choe SK, Subramanya SJ, Neiswanger W, Ho Q, Zhang H, Ganger GR, Xing EP (2021) Pollux: Co-adaptive cluster scheduling for goodput-optimized deep learning. 15th USENIX Sympos. Operating Systems Design Implementation (OSDI 2021) (USENIX Association, Berkeley, CA).Google Scholar
• Scully Z, Grosof I, Harchol-Balter M (2020a) The Gittins policy is nearly optimal in the M/G/k under extremely general conditions. Proc. ACM Measurement Analysis Comput. Systems 4(3):1–29.Google Scholar
• Scully Z, Grosof I, Harchol-Balter M (2020b) Optimal multiserver scheduling with unknown job sizes in heavy traffic. ACM SIGMETRICS Performance Evaluation Rev. 48(2):33–35.Google Scholar
• Storm PJ, Borst S (2023) Diffusion-level universality of many-server systems with concurrent service. Oper. Res. Lett. 51(3):212–219.Google Scholar
• Tumanov A, Zhu T, Park JW, Kozuch MA, Harchol-Balter M, Ganger GR (2016) Tetrisched: Global rescheduling with adaptive plan-ahead in dynamic heterogeneous clusters. Cadar C, Pietzuch PR, Keeton K, Rodrigues R, eds. Proc. Eleventh European Conf. Comput. Systems (ACM, New York), 1–16.Google Scholar
• Van Mieghem JA (1995) Dynamic scheduling with convex delay costs: The generalized cμ rule. Ann. Appl. Probab. 809–833.Google Scholar
• Varma SM, Castro F, Maguluri ST (2023) Power-of-d choices load balancing in the sub-Halfin Whitt regime. Stochastic Systems 15(4):291–336. Google Scholar
• Vernica R, Carey MJ, Li C (2010) Efficient parallel set-similarity joins using mapreduce. Proc. ACM SIGMOD Internat. Conf. Management Data (ACM, New York), 495–506.Google Scholar
• Wagner B, Kohn A, Neumann T (2021) Self-tuning query scheduling for analytical workloads. Proc. Internat. Conf. Management Data (ACM, New York), 1879–1891.Google Scholar
• Wang W, Maguluri ST, Srikant R, Ying L (2022) Heavy-traffic insensitive bounds for weighted proportionally fair bandwidth sharing policies. Math. Oper. Res. 47(4):2691–2720.Link, Google Scholar
• Weng W, Wang W (2020) Achieving zero asymptotic queueing delay for parallel jobs. Proc. ACM Measurement Analysis Comput. Systems 4(3):1–36.Google Scholar
• Xu K (2023) Drift method: From stochastic networks to machine learning. Accessed September 3, 2023, https://web.stanford.edu/kuangxu/papers/driftmethod.pdf.Google Scholar
• Zhu Y, Jiang Y, Wu W, Ding L, Teredesai A, Li D, Lee W (2014) Minimizing makespan and total completion time in MapReduce-like systems. IEEE INFOCOM 2014-IEEE Conf. Comp. Comm. (IEEE, Piscataway, NJ), 2166–2174.Google Scholar