Ring算法是一种基于环形拓扑结构的分布式计算算法,其核心思想是将系统中的节点(如进程或计算单元)组织成一个逻辑环,每个节点仅与环上的直接邻居节点(左邻和右邻)通信,信息沿环的固定方向依次传递,从而实现协作。
百度在2018年提出一种在深度学习场景下高效的all reduce算法,称为Ring all reduce。整个通信过程可以分为reduce-scatter和all gather两个阶段。
假设我们有如下5个节点:
GPU 0: a0 b0 c0 d0 e0 GPU 1: a1 b1 c1 d1 e1 GPU 2: a2 b2 c2 d2 e2 GPU 3: a3 b3 c3 d3 e3 GPU 4: a4 b4 c4 d4 e4
其reduce-scatter过程如下,第1步为:
GPU 0: a0 b0 c0 d0 e0+e4 GPU 1: a0+a1 b1 c1 d1 e1 GPU 2: a2 b1+b2 c2 d2 e2 GPU 3: a3 b3 c2+c3 d3 e3 GPU 4: a4 b4 c4 d3+d4 e4
而第2步为:
GPU 0: a0 b0 c0 d0+d3+d4 e0+e4 GPU 1: a0+a1 b1 c1 d1 e1+e0+e4 GPU 2: a0+a1+a2 b1+b2 c2 d2 e2 GPU 3: a3 b1+b2+b3 c2+c3 d3 e3 GPU 4: a4 b4 c2+c3+c4 d3+d4 e4
而第3步为:
GPU 0: a0 b0 c0+c2+c3+c4 d0+d3+d4 e0+e4 GPU 1: a0+a1 b1 c1 d1+d0+d3+d4 e1+e0+e4 GPU 2: a0+a1+a2 b1+b2 c2 d2 e2+e1+e0+e4 GPU 3: a0+a1+a2+a3 b1+b2+b3 c2+c3 d3 e3 GPU 4: a4 b1+b2+b3+b4 c2+c3+c4 d3+d4 e4
最后我们得到:
GPU 0: a0 b0+b1+b2+b3+b4 c0+c2+c3+c4 d0+d3+d4 e0+e4 GPU 1: a0+a1 b1 c1+c0+c2+c3+c4 d1+d0+d3+d4 e1+e0+e4 GPU 2: a0+a1+a2 b1+b2 c2 d2+d1+d0+d3+d4 e2+e1+e0+e4 GPU 3: a0+a1+a2+a3 b1+b2+b3 c2+c3 d3 e3+e2+e1+e0+e4 GPU 4: a0+a1+a2+a3+a4 b1+b2+b3+b4 c2+c3+c4 d3+d4 e4
之后就要开始进行all-gather进行广播了。而执行完一个环后,所有节点均有完整的备份。因此,Ring All Reduce进行2次环就完成整个数据的同步。
参考文章:
https://www.zhihu.com/question/57799212 https://blog.csdn.net/weixin_44966641/article/details/149980684 https://www.bilibili.com/video/BV1fg41187rc/
如果喜欢这篇文章或对您有帮助，可以：[☕] 请我喝杯咖啡 | [💓] 小额赞助
