Leveraging Coding Techniques for Speeding up Distributed Computing
Leveraging Coding Techniques for Speeding up Distributed Computing
复制标题
DOI：
10.1109/glocom.2018.8647133
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Konstantinos Konstantinidis;A. Ramamoorthy
中科院分区：
文献类型：
--
作者：
Konstantinos Konstantinidis;A. Ramamoorthy
大规模的簇运行MapReduce，Spark等。通常处理PB级或更多订单上的数据。这些方法的理念是将整个作业分为在不同服务器上执行的较小任务。这称为地图阶段。接下来是一个数据改组阶段，在服务器之间交换适当的数据。最终减少阶段，完成计算。先前的工作探索了一种通过在计算与通信折衷下进行操作来减少总体执行时间的机制。具体而言，这个想法是运行放置在明智选择的服务器上的地图任务的冗余副本。洗牌阶段利用节点的位置并利用编码的传输。这种方法的主要缺点是，它要求将原始作业分为许多在系统参数中成倍增长的地图任务。这是有问题的，因为我们证明分裂工作过得太细微，实际上可能会对整个执行时间产生不利影响。在这项工作中，我们表明可以同时获得低沟通负载，同时确保不需要太细微的工作。我们的方法发现了这个问题与一类称为可分离设计的组合结构之间的深厚关系。我们提出了在亚马逊EC2簇上获得的实验结果，该簇的分布算法，即Terasort。我们在基线方法上的加速度提高了4.69倍，而与当前的最新状态相比，我们获得了超过2.6倍的进步。
Large scale clusters running MapReduce, Spark etc. routinely process data that are on the orders of petabytes or more. The philosophy in these methods is to split the overall job into smaller tasks that are executed on different servers; this is called the map phase. This is followed by a data shuffling phase where appropriate data is exchanged between the servers. The final reduce phase, completes the computation. Prior work has explored a mechanism for reducing the overall execution time by operating on a computation vs. communication tradeoff. Specifically, the idea is to run redundant copies of map tasks that are placed on judiciously chosen servers. The shuffle phase exploits the location of the nodes and utilizes coded transmission. The main drawback of this approach is that it requires the original job to be split into a number of map tasks that grows exponentially in the system parameters. This is problematic, as we demonstrate that splitting jobs too finely can in fact adversely affect the overall execution time. In this work we show that one can simultaneously obtain low communication loads while ensuring that jobs do not need to be split too finely. Our approach uncovers a deep relationship between this problem and a class of combinatorial structures called resolvable designs. We present experimental results obtained on Amazon EC2 clusters for a widely known distributed algorithm, namely TeraSort. We obtain over 4.69x improvement in speedup over the baseline approach and more than 2.6x over current state of the art.