Delay asymptotics and bounds for multi-task parallel jobs

Weina Wang, Mor Harchol-Balter, Haotian Jiang, Alan Scheller-Wolf, Rayadurgam Srikant

Research output: Contribution to journalConference article

Abstract

We study delay of jobs that consist of multiple parallel tasks, which is a critical performance metric in a wide range of applications such as data file retrieval in coded storage systems and parallel computing. In this problem, each job is completed only when all of its tasks are completed, so the delay of a job is the maximum of the delays of its tasks. Despite the wide attention this problem has received, tight analysis is still largely unknown since analyzing job delay requires characterizing the complicated correlation among task delays, which is hard to do. We first consider an asymptotic regime where the number of servers, n, goes to infinity, and the number of tasks in a job, k ( n ) , is allowed to increase with n. We establish the asymptotic independence of any k ( n ) queues under the condition k ( n ) = o(n 1 / 4 ). This greatly generalizes the asymptotic-independence type of results in the literature where asymptotic independence is shown only for a fixed constant number of queues. As a consequence of our independence result, the job delay converges to the maximum of independent task delays. We next consider the non-asymptotic regime. Here we prove that independence yields a stochastic upper bound on job delay for any n and any k ( n ) with k ( n ) ≤ n. The key component of our proof is a new technique we develop, called “Poisson oversampling”. Our approach converts the job delay problem into a corresponding balls-and-bins problem. However, in contrast with typical balls-and-bins problems where there is a negative correlation among bins, we prove that our variant exhibits positive correlation. A full version of this paper will all proofs appears in [28].

Original languageEnglish (US)
Pages (from-to)2-7
Number of pages6
JournalPerformance Evaluation Review
Volume46
Issue number3
DOIs
StatePublished - Jan 25 2019
Event36th IFIP Performance Conference 2018 - Toulouse, France
Duration: Dec 5 2018Dec 7 2018

Fingerprint

Bins
Parallel processing systems
Servers

Keywords

  • Association of random variables
  • Asymptotic independence
  • Large systems
  • Parallel jobs

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Delay asymptotics and bounds for multi-task parallel jobs. / Wang, Weina; Harchol-Balter, Mor; Jiang, Haotian; Scheller-Wolf, Alan; Srikant, Rayadurgam.

In: Performance Evaluation Review, Vol. 46, No. 3, 25.01.2019, p. 2-7.

Research output: Contribution to journalConference article

Wang, W, Harchol-Balter, M, Jiang, H, Scheller-Wolf, A & Srikant, R 2019, 'Delay asymptotics and bounds for multi-task parallel jobs', Performance Evaluation Review, vol. 46, no. 3, pp. 2-7. https://doi.org/10.1145/3308897.3308901
Wang, Weina ; Harchol-Balter, Mor ; Jiang, Haotian ; Scheller-Wolf, Alan ; Srikant, Rayadurgam. / Delay asymptotics and bounds for multi-task parallel jobs. In: Performance Evaluation Review. 2019 ; Vol. 46, No. 3. pp. 2-7.
@article{40d6e3c0cce740f19f5cb28bace35ec8,
title = "Delay asymptotics and bounds for multi-task parallel jobs",
abstract = "We study delay of jobs that consist of multiple parallel tasks, which is a critical performance metric in a wide range of applications such as data file retrieval in coded storage systems and parallel computing. In this problem, each job is completed only when all of its tasks are completed, so the delay of a job is the maximum of the delays of its tasks. Despite the wide attention this problem has received, tight analysis is still largely unknown since analyzing job delay requires characterizing the complicated correlation among task delays, which is hard to do. We first consider an asymptotic regime where the number of servers, n, goes to infinity, and the number of tasks in a job, k ( n ) , is allowed to increase with n. We establish the asymptotic independence of any k ( n ) queues under the condition k ( n ) = o(n 1 / 4 ). This greatly generalizes the asymptotic-independence type of results in the literature where asymptotic independence is shown only for a fixed constant number of queues. As a consequence of our independence result, the job delay converges to the maximum of independent task delays. We next consider the non-asymptotic regime. Here we prove that independence yields a stochastic upper bound on job delay for any n and any k ( n ) with k ( n ) ≤ n. The key component of our proof is a new technique we develop, called “Poisson oversampling”. Our approach converts the job delay problem into a corresponding balls-and-bins problem. However, in contrast with typical balls-and-bins problems where there is a negative correlation among bins, we prove that our variant exhibits positive correlation. A full version of this paper will all proofs appears in [28].",
keywords = "Association of random variables, Asymptotic independence, Large systems, Parallel jobs",
author = "Weina Wang and Mor Harchol-Balter and Haotian Jiang and Alan Scheller-Wolf and Rayadurgam Srikant",
year = "2019",
month = "1",
day = "25",
doi = "10.1145/3308897.3308901",
language = "English (US)",
volume = "46",
pages = "2--7",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "3",

}

TY - JOUR

T1 - Delay asymptotics and bounds for multi-task parallel jobs

AU - Wang, Weina

AU - Harchol-Balter, Mor

AU - Jiang, Haotian

AU - Scheller-Wolf, Alan

AU - Srikant, Rayadurgam

PY - 2019/1/25

Y1 - 2019/1/25

N2 - We study delay of jobs that consist of multiple parallel tasks, which is a critical performance metric in a wide range of applications such as data file retrieval in coded storage systems and parallel computing. In this problem, each job is completed only when all of its tasks are completed, so the delay of a job is the maximum of the delays of its tasks. Despite the wide attention this problem has received, tight analysis is still largely unknown since analyzing job delay requires characterizing the complicated correlation among task delays, which is hard to do. We first consider an asymptotic regime where the number of servers, n, goes to infinity, and the number of tasks in a job, k ( n ) , is allowed to increase with n. We establish the asymptotic independence of any k ( n ) queues under the condition k ( n ) = o(n 1 / 4 ). This greatly generalizes the asymptotic-independence type of results in the literature where asymptotic independence is shown only for a fixed constant number of queues. As a consequence of our independence result, the job delay converges to the maximum of independent task delays. We next consider the non-asymptotic regime. Here we prove that independence yields a stochastic upper bound on job delay for any n and any k ( n ) with k ( n ) ≤ n. The key component of our proof is a new technique we develop, called “Poisson oversampling”. Our approach converts the job delay problem into a corresponding balls-and-bins problem. However, in contrast with typical balls-and-bins problems where there is a negative correlation among bins, we prove that our variant exhibits positive correlation. A full version of this paper will all proofs appears in [28].

AB - We study delay of jobs that consist of multiple parallel tasks, which is a critical performance metric in a wide range of applications such as data file retrieval in coded storage systems and parallel computing. In this problem, each job is completed only when all of its tasks are completed, so the delay of a job is the maximum of the delays of its tasks. Despite the wide attention this problem has received, tight analysis is still largely unknown since analyzing job delay requires characterizing the complicated correlation among task delays, which is hard to do. We first consider an asymptotic regime where the number of servers, n, goes to infinity, and the number of tasks in a job, k ( n ) , is allowed to increase with n. We establish the asymptotic independence of any k ( n ) queues under the condition k ( n ) = o(n 1 / 4 ). This greatly generalizes the asymptotic-independence type of results in the literature where asymptotic independence is shown only for a fixed constant number of queues. As a consequence of our independence result, the job delay converges to the maximum of independent task delays. We next consider the non-asymptotic regime. Here we prove that independence yields a stochastic upper bound on job delay for any n and any k ( n ) with k ( n ) ≤ n. The key component of our proof is a new technique we develop, called “Poisson oversampling”. Our approach converts the job delay problem into a corresponding balls-and-bins problem. However, in contrast with typical balls-and-bins problems where there is a negative correlation among bins, we prove that our variant exhibits positive correlation. A full version of this paper will all proofs appears in [28].

KW - Association of random variables

KW - Asymptotic independence

KW - Large systems

KW - Parallel jobs

UR - http://www.scopus.com/inward/record.url?scp=85061530046&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85061530046&partnerID=8YFLogxK

U2 - 10.1145/3308897.3308901

DO - 10.1145/3308897.3308901

M3 - Conference article

AN - SCOPUS:85061530046

VL - 46

SP - 2

EP - 7

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 3

ER -