On the worst-case communication overhead for distributed data shuffling
On the worst-case communication overhead for distributed data shuffling
复制标题
关于分布式数据洗牌的最坏情况通信开销
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Tandon
中科院分区：
文献类型：
--
作者：
M. Attia;R. Tandon
用于处理大规模数据集的分布式学习平台变得越来越普遍。在典型的分布式实现中，集中式主节点将数据集分成较小的批次，以便跨分布式工作线程进行并行处理，以实现加速和效率。一些计算任务具有顺序性质，并且涉及对数据的多次传递。在数据的每次迭代中，通常的做法是在主节点上随机重新洗牌数据，为每个工作节点分配不同的批次进行处理。这种随机的重新洗牌操作是以额外的通信开销为代价的，因为在每次洗牌时，都需要将新的数据点传递给分布式工作人员。在本文中，我们重点关注分布式数据洗牌问题的信息理论上最优通信开销的特征。我们针对没有多余存储的情况提出了一种新颖的编码数据传输方案，其中每个工作人员只能存储正在处理的分配的数据批次。我们的方案利用了一种新型的编码机会，适用于任何任意的洗牌，以及任何数量的工作人员。我们还提出了数据混洗的最小通信开销的信息论下限，并表明所提出的方案与最坏情况通信开销的下限相匹配。
Distributed learning platforms for processing large scale data-sets are becoming increasingly prevalent. In typical distributed implementations, a centralized master node breaks the data-set into smaller batches for parallel processing across distributed workers to achieve speed-up and efficiency. Several computational tasks are of sequential nature, and involve multiple passes over the data. At each iteration over the data, it is common practice to randomly re-shuffle the data at the master node, assigning different batches for each worker to process. This random re-shuffling operation comes at the cost of extra communication overhead, since at each shuffle, new data points need to be delivered to the distributed workers. In this paper, we focus on characterizing the information theoretically optimal communication overhead for the distributed data shuffling problem. We propose a novel coded data delivery scheme for the case of no excess storage, where every worker can only store the assigned data batches under processing. Our scheme exploits a new type of coding opportunity and is applicable to any arbitrary shuffle, and for any number of workers. We also present information theoretic lower bounds on the minimum communication overhead for data shuffling, and show that the proposed scheme matches this lower bound for the worst-case communication overhead.