Mar, 2015

大规模并行计算中高效 straggler 复制

PDF
TL;DR本文提供了一个分析云计算任务并行执行框架中任务复制对延迟和计算资源成本的权衡的框架，通过回答设计问题，如何在什么时候复制滞后的任务，启动多少副本等。我们的分析表明，对于某些执行时间分布，少量任务复制可以显著降低延迟和计算资源的成本，并提出一种基于任务执行时间的经验分布估计延迟和成本的算法。与 MapReduce 中使用的现有复制策略相比，使用 Google Cluster Trace 中的样本进行评估揭示了进一步的延迟和成本降低。
发现论文，激发创造
  • 通过延迟重新启动任务来缓解落后者问题

    本文分析了使用简单复制或擦除编码技术以减少中间结果 straggler 对任务执行时间的影响，通过代价和延迟的比较，发现擦除编码技术在处理长尾延迟任务时比简单复制技术更加有效，提供了实验证明。

    Oct, 2017

  • 高效的任务复制以实现并行计算中的快速响应时间

    本文研究大规模分布式计算中任务复制对响应时间和资源使用的影响，并提出了一些高效的算法来寻找最优的调度策略。

    Apr, 2014

  • 任务分配对带拖延的分布式计算系统的影响

    本文研究分布式计算中冗余任务分配和批处理对计算时间的影响，并发现在拥有固定任务数量的系统中，均匀复制非重叠批次的计算任务可以实现最小化的计算时间。

    Aug, 2018

  • 分布式优化和学习中的迟滞者减缓冗余技术

    本文提出了一种分布式优化框架，通过将数据编码为过完备表示，并动态地在每次迭代中舍弃整个计算中的掉队节点，从而减少了延迟和通信传输的负担，结果表明在数据被编码的情况下，对于几种流行的优化算法，包括梯度下降、L-BFGS、在数据并行性下的近端梯度以及在模型并行性下的坐标下降，当掉队者被视为纠删码时，它们都会收敛到原始问题的近似或精确解，收敛结果是确定性的，并且与掉队分布的尾部行为无关，本研究还提出了一种用于大规模数据编码的高效机制，以及证明了用等角紧框架作为编码矩阵的理想性质，并与未编码、异步和数据复制策略进行了比较。

    Mar, 2018

  • 云系统延迟降低的高效冗余技术

    在云计算系统中，确定冗余策略的适用条件和实现方式是降低时延和成本的关键。通过对任务服务时间分布的对数凹凸性进行研究，该文设计出一种通用的冗余策略，在最大化降低时延和最小化成本之间达到了很好的平衡。

    Aug, 2015

  • 数据编码在分布式优化中的缓解残留问题

    本文提出了一种直接在数据中嵌入冗余来处理缓慢任务的新方法，通过一些编码技巧将复制数据的策略转换到线性计算过程中，从而利用节点的任意变化在没有等待慢节点的情况下完成散列计算，并通过实验结果表明此方法的优势。

    Nov, 2017

  • 车联网边缘计算的分布式任务复制：性能分析与基于学习的算法

    本文提出了一种在车辆边缘计算系统中使用多个任务副本进行任务卸载，以减少任务卸载延迟的学习算法，并通过实验展示了该算法的良好性能。

    Feb, 2020

  • 分布式机器学习中的计算调度与延迟工人问题

    本文研究分布式学习中多个工作者的计算任务调度问题，提出了两种计算调度方案，以及基于计算和通信延迟的平均完成时间分析，实验证明所提出的方案有效且接近最优解。

    Oct, 2018

  • 分布式梯度方法的近似最优散乱者缓解

    本研究提出了一种名为批处理优惠券集合（BCC）的分布式计算方案，以减轻梯度法中流浪者的影响，该方案在随机弱者数量接近最优时具有鲁棒性，并证明了 BCC 方案的有效性，提高了 85.4％的运行时间。此外，该方案的泛化结果证明了其能够在异构工作节点上实现梯度下降算法以最小化完成时间。

    Oct, 2017

  • 减少计算负载的快速容错分布式 SGD

    该研究通过适应节点和运算负载调整方法，提高分布式随机梯度下降算法的收敛速度，显著降低计算负载，但略微增加通信负载。

    Apr, 2023