abstract

Achieving Zero Asymptotic Queueing Delay for Parallel Jobs

Authors:

SIGMETRICS '21: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

Pages 25 - 26

https://doi.org/10.1145/3410220.3456268

Published: 06 June 2021 Publication History

Get Access

Abstract

Zero queueing delay is highly desirable in large-scale computing systems. Existing work has shown that it can be asymptotically achieved by using the celebrated Power-of-d-choices (Pod) policy with a probe overhead d = Ω(log N/1-λ), and it is impossible when d = O(1/1-λ), where N is the number of servers and λ is the load of the system. However, these results are based on the model where each job is an indivisible unit, which does not capture the parallel structure of jobs in today's predominant parallel computing paradigm.

This paper considers a model where each job consists of a batch of parallel tasks. Under this model, we propose a new notion of zero (asymptotic) queueing delay that requires the job delay under a policy to approach the job delay given by the max of its tasks' service times, i.e., the job delay assuming its tasks entered service right upon arrival. This notion quantifies the effect of queueing on a job level for jobs consisting of multiple tasks, and thus deviates from the conventional zero queueing delay for single-task jobs in the literature.

We show that zero queueing delay for parallel jobs can be achieved using the batch-filling policy (a variant of the celebrated Pod policy) with a probe overhead d = Ω(1/(1-λ)log k) in the sub-Halfin-Whitt heavy-traffic regime, where k is the number of tasks in each job and k properly scales with N (the number of servers). This result demonstrates that for parallel jobs, zero queueing delay can be achieved with a smaller probe overhead. We also establish an impossibility result: we show that zero queueing delay cannot be achieved if d = (o(log N/log k)). Simulation results are provided to demonstrate the consistency between numerical results and theoretical results under reasonable settings, and to investigate gaps in the theoretical analysis.

Supplementary Material

MP4 File (SIGMETRICS21-paralleljob.mp4)

presentation video

Download
186.83 MB

References

[1]

Xin Liu and Lei Ying. 2018. On achieving zero delay with power-of-d-choices load balancing. In Proc. IEEE Int. Conf. Computer Communications (INFOCOM). Honolulu, HI, USA, 297--305.

Digital Library

Google Scholar

[2]

Xin Liu and Lei Ying. 2019. On Universal Scaling of Distributed Queues under Load Balancing. arXiv:1912.11904 [math.PR] (2019).

Google Scholar

[3]

Xin Liu and Lei Ying. 2020. Steady-state analysis of load-balancing algorithms in the sub-Halfin--Whitt regime. J. Appl. Probab., Vol. 57, 2 (2020), 578--596.

Crossref

Google Scholar

[4]

Michael Mitzenmacher. 2001. The power of two choices in randomized load balancing. IEEE Trans. Parallel Distrib. Syst., Vol. 12, 10 (2001), 1094--1104.

Digital Library

Google Scholar

[5]

Nikita Dmitrievna Vvedenskaya, Roland L'vovich Dobrushin, and Fridrikh Izrailevich Karpelevich. 1996. Queueing system with selection of the shortest of two queues: An asymptotic approach. Problems of Information Transmission, Vol. 32, 1 (1996), 15--27.

Google Scholar

[6]

Wentao Weng and Weina Wang. 2020. Achieving Zero Asymptotic Queueing Delay for Parallel Jobs. Proc. ACM Measurement and Analysis of Computing Systems (POMACS), Vol. 4, 3, 1--36.

Digital Library

Google Scholar

[7]

Lei Ying, R. Srikant, and Xiaohan Kang. 2015. The power of slightly more than one sample in randomized load balancing. In Proc. IEEE Int. Conf. Computer Communications (INFOCOM). Kowloon, Hong Kong, 1131--1139.

Crossref

Google Scholar

Cited By

View all

Wang WXie QHarchol-Balter M(2022)Zero Queueing for Multi-Server JobsACM SIGMETRICS Performance Evaluation Review10.1145/3543516.345392449:1(13-14)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1145/3543516.3453924
Wang WXie QHarchol-Balter M(2021)Zero Queueing for Multi-Server JobsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34473855:1(1-25)Online publication date: 22-Feb-2021
https://dl.acm.org/doi/10.1145/3447385

Index Terms

Achieving Zero Asymptotic Queueing Delay for Parallel Jobs

Recommendations

Achieving Zero Asymptotic Queueing Delay for Parallel Jobs
POMACS

Zero queueing delay is highly desirable in large-scale computing systems. Existing work has shown that it can be asymptotically achieved by using the celebrated Power-of-d-choices (pod) policy with a probe overhead $d = ømegałeft(\fracłog N 1-łambda \...
Zero Queueing for Multi-Server Jobs
SIGMETRICS '21: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

Cloud computing today is dominated by multi-server jobs. These are jobs that request multiple servers simultaneously and hold onto all of these servers for the duration of the job. Multi-server jobs add a lot of complexity to the traditional one-server-...
Achieving Zero Asymptotic Queueing Delay for Parallel Jobs
SIGMETRICS '21

Zero queueing delay is highly desirable in large-scale computing systems. Existing work has shown that it can be asymptotically achieved by using the celebrated Power-of-d-choices (Pod) policy with a probe overhead d = Ω(log N/1-λ), and it is impossible ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGMETRICS '21: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

May 2021

97 pages

ISBN:9781450380720

DOI:10.1145/3410220

General Chair:
Longbo Huang
Tsinghua University, China
,
Program Chairs:
Anshul Gandhi
Stony Brook University, USA
,
Negar Kiyavash
EPFL, Switzerland
,
Jia Wang
AT&T Labs Research, USA

ACM SIGMETRICS Performance Evaluation Review Volume 49, Issue 1
SIGMETRICS '21
June 2021
80 pages
ISSN:0163-5999
DOI:10.1145/3543516
Editor:
Nidhi Hegde
Borealis AI
Issue’s Table of Contents

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2021

Check for updates

Author Tags

Qualifiers

Abstract

Conference

SIGMETRICS '21

Sponsor:

SIGMETRICS

SIGMETRICS '21: ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

June 14 - 18, 2021

Virtual Event, China

Acceptance Rates

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
82
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang WXie QHarchol-Balter M(2022)Zero Queueing for Multi-Server JobsACM SIGMETRICS Performance Evaluation Review10.1145/3543516.345392449:1(13-14)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1145/3543516.3453924
Wang WXie QHarchol-Balter M(2021)Zero Queueing for Multi-Server JobsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/34473855:1(1-25)Online publication date: 22-Feb-2021
https://dl.acm.org/doi/10.1145/3447385

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Achieving Zero Asymptotic Queueing Delay for Parallel Jobs

Zero Queueing for Multi-Server Jobs

Achieving Zero Asymptotic Queueing Delay for Parallel Jobs