On the Fundamental Limits of Coded Data Shuffling for Distributed Machine Learning
On the Fundamental Limits of Coded Data Shuffling for Distributed Machine Learning
复制标题
DOI：
10.1109/tit.2020.2964547
复制
发表时间：
2020-05-01
影响因子：
2.5
通讯作者：
Mohajer, Soheil
中科院分区：
文献类型：
--
作者：
Elmahdy, Adel;Mohajer, Soheil
我们考虑分布式学习系统中的数据洗牌问题，其中主节点通过共享链路连接到一组工作节点，以便将一组文件传送到工作节点。主节点可以访问文件数据库。在每次混洗迭代中，每个工作节点处理新的文件子集，并具有多余的存储来部分缓存剩余的文件，假设缓存的文件未编码。工作节点的缓存在每次迭代时都会更新，它们应该被设计为满足后续迭代中文件的任何可能的未知排列。对于这个问题，我们的特点是准确的负载-内存权衡最坏情况下的洗牌推导出的最小通信负载为每个工作节点的给定存储容量。作为副产品，当文件的数量等于工作节点的数量时，任何洗牌的确切负载-内存权衡都是特征。我们提出了一种新的确定性编码洗牌计划，提高了现有技术的状态，通过利用该高速缓存存储器创建编码功能，可以由几个工作节点解码。然后，我们证明了我们提出的方案的最优性，通过推导出一个匹配的下限，并表明所提出的编码洗牌计划的位置相位是最佳的所有洗牌。
We consider the data shuffling problem in a distributed learning system, in which a master node is connected to a set of worker nodes, via a shared link, in order to communicate a set of files to the worker nodes. The master node has access to a database of files. In every shuffling iteration, each worker node processes a new subset of files, and has excess storage to partially cache the remaining files, assuming the cached files are uncoded. The caches of the worker nodes are updated every iteration, and they should be designed to satisfy any possible unknown permutation of the files in subsequent iterations. For this problem, we characterize the exact load-memory trade-off for worst-case shuffling by deriving the minimum communication load for a given storage capacity per worker node. As a byproduct, the exact load-memory trade-off for any shuffling is characterized when the number of files is equal to the number of worker nodes. We propose a novel deterministic coded shuffling scheme, which improves the state of the art, by exploiting the cache memories to create coded functions that can be decoded by several worker nodes. Then, we prove the optimality of our proposed scheme by deriving a matching lower bound and showing that the placement phase of the proposed coded shuffling scheme is optimal over all shuffles.