Delay Asymptotics and Bounds for Multi-Task Parallel Jobs
Delay Asymptotics and Bounds for Multi-Task Parallel Jobs
复制标题
多任务并行作业的延迟渐近和界限
DOI：
10.1145/3308897.3308901
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Srikant, R.
中科院分区：
文献类型：
--
作者：
Wang, Weina;Harchol-Balter, Mor;Jiang, Haotian;Scheller-Wolf, Alan;Srikant, R.
我们研究了由多个并行任务组成的作业的延迟，这是编码存储系统中数据文件检索和并行计算等广泛应用中的关键性能指标。在此问题中，每个作业只有在其所有任务都完成时才会完成，因此作业的延迟是其任务延迟的最大值。尽管这一问题受到了广泛的关注，但由于分析工作延迟需要描述任务延迟之间复杂的相关性，因此很难对其进行严格的分析。我们首先考虑一个渐近区域，其中服务器数量n趋于无穷，并且作业中的任务数量k(n)允许随着n的增加而增加。我们在k(n) = o（n1/4）的条件下建立了任意k(n)个队列的渐近独立性。这极大地推广了文献中结果的渐近独立性类型，其中渐近独立性仅对固定常数数量的队列显示。由于我们的独立性结果，作业延迟收敛于独立任务延迟的最大值。接下来我们考虑非渐近状态。本文证明了对于任意n和任意k(n)且k(n)≤n的任务延迟的独立性给出了一个随机上界。我们证明的关键部分是我们开发的一种新技术，称为“泊松过采样”。我们的方法将作业延迟问题转化为相应的球箱问题。然而，与典型的球与箱之间存在负相关的问题相比，我们证明了我们的变量表现出正相关。本文的完整版本将在[28]中出现所有证明。
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(n1/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].