论文标题
全能在同步系统中编码
All-to-All Encode in Synchronous Systems
论文作者
论文摘要
我们定义了全部编码，这是一种集体通信操作，用作分散计算和存储系统的原始操作。考虑一个场景，每个处理器最初都有一个数据包，并且需要所有数据包的线性组合；线性组合从一个处理器到另一个处理器不同，由错误校正代码的发电机矩阵指定。我们使用线性网络模型，在该模型中，处理器传输数据的线性组合并先前接收到数据包，并采用标准同步系统设置来分析其通信成本。我们提供了一种通用算法，该算法仅通过改变中间系数来计算此模型中的任何矩阵，并证明其最佳性。当发电机矩阵是Vandermonde或Lagrange类型的时，我们进一步优化了所提出算法的通信效率。
We define all-to-all encode, a collective communication operation serving as a primitive in decentralized computation and storage systems. Consider a scenario where every processor initially has a data packet and requires a linear combination of all data packets; the linear combinations are distinct from one processor to another, and are specified by a generator matrix of an error correcting code. We use a linear network model, in which processors transmit linear combinations of their data and previously received packets, and adopt a standard synchronous system setting to analyze its communication cost. We provide a universal algorithm which computes any matrix in this model by only varying intermediate coefficients, and prove its optimality. When the generator matrix is of the Vandermonde or Lagrange type, we further optimize the communication efficiency of the proposed algorithm.
