← 研踪 PaperTrailarXiv:2611.21190 · v1
Linear Network Coding for Sum All-Reduce over Ring Networks
首次提交 2026-11-16 22:46
版本更新 2026-11-16 22:46
雷达观测 2026-11-17 17:11
摘要
Sum All-Reduce is a fundamental collective communication primitive in which each node holds a local vector and every node must recover the componentwise sum of all vectors. In distributed training, this operation is often implemented over a ring topology using a reduce--multicast scheme. We study sum All-Reduce on directed rings via linear network coding, which includes reduce--multicast as a special case. We give a necessary and sufficient feasibility condition in terms of the coding matrices. For a ring with nodes and unit-capacity links, where each node holds a vector containing symbols, we prove that the number of time units required by any feasible linear code satisfies , giving a rate of at most . The bound is tight over every field. When , an interleaved reduce--multicast code achieves the bound; when and divides , a reduce--partial-multicast code does. When and does not divide , no coordinate-wise code---in particular, no reduce--multicast code---achieves the bound, while an explicit linear network code does.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-16 22:46 · 最新观测版本
Linear Network Coding for Sum All-Reduce over Ring Networks
Sum All-Reduce is a fundamental collective communication primitive in which each node holds a local vector and every node must recover the componentwise sum of all vectors. In distributed training, this operation is often implemented over a ring topology using a reduce--multicast scheme. We study sum All-Reduce on directed rings via linear network coding, which includes reduce--multicast as a special case. We give a necessary and sufficient feasibility condition in terms of the coding matrices. For a ring with nodes and unit-capacity links, where each node holds a vector containing symbols, we prove that the number of time units required by any feasible linear code satisfies , giving a rate of at most . The bound is tight over every field. When , an interleaved reduce--multicast code achieves the bound; when and divides , a reduce--partial-multicast code does. When and does not divide , no coordinate-wise code---in particular, no reduce--multicast code---achieves the bound, while an explicit linear network code does.
查看此版本解读 →查看此版本原文 ↗