...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Performance evaluation review >Delay Asymptotics and Bounds for Multi-Task Parallel Jobs
【24h】

Delay Asymptotics and Bounds for Multi-Task Parallel Jobs

机译：多任务并行作业的延迟渐近和界线

获取原文
获取原文并翻译 | 示例
   

获取外文期刊封面封底 >>

       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 f~((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].
机译：我们研究由多个并行任务组成的作业的延迟，这是广泛应用中的关键性能指标，例如编码存储系统中的数据文件检索和并行计算。在此问题中，每个作业仅在其所有任务都完成时才完成，因此作业的延迟是其任务延迟的最大值。尽管这个问题受到了广泛的关注，但是由于分析工作延迟需要表征任务延迟之间的复杂相关性，因此很难进行严格的分析，这很难做到。我们首先考虑一种渐近状态，其中服务器数量n达到无穷大，并且作业中的任务数量k〜（n）随n增加。我们建立了在条件k〜（n）= o（n〜（1/4））下任何k〜（n）个队列的渐近独立性。这在文献中极大地概括了渐近独立性类型的结果，其中仅对于固定的恒定数量的队列显示渐近独立性。作为我们独立性结果的结果，工作延迟收敛到最大的独立任务延迟。接下来我们考虑非渐近体制。在这里我们证明，对于任何n和任何f〜（（n））≤n的k〜（（n）），独立性都会产生随机的作业延迟上限。证明的关键部分是我们开发的一种新技术，称为“泊松过采样”。我们的方法将作业延迟问题转换为相应的球窝问题。但是，与典型的球和桶问题之间的负相关性相反，我们证明了我们的变体表现出正相关性。本文的完整版将在[28]中出现所有证明。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号