Reduce, Broadcast and AllReduce

在做机器学习的时候,经常要做这样一个操作:每台机器计算出一个vector,然后把这些vector汇总加起来,再广播回去

传统模式

如下面这组图所示:

1.png

2.png

3.png

4.png

总体来说,它可以分为两步:

  1. Reduce。 即map-reduce中的那个reduce。
  2. Broadcast。 把reduce的结果broadcast到所有节点。

直接以这样两步走的方式解决此问题会很低效。如果vector长度很大,那么负责汇聚的那个节点,就会成为性能瓶颈。

树状模式

于是就有了基于tree的map-reduce来解决这个问题。这种方式被广泛用在了Vowpal Wabbit和spark中。

tree1.png

tree2.png

tree3.png

broadcast的过程与reduce的过程类似,我就不画了。

下面举个例子分析下它需要花多少时间。 假设我们有75台机器,采用5叉树的方式来汇聚。那么需要5层。 第一层75台机器。 第二层15台机器。 第三层3台机器。 第四层1台机器。

假设每个Vector的大小是1GB,而带宽是10Gb/s,那么reduce阶段至少需要(5+5+3)*8/10=10秒才能传输完。

采用上一种方案,reduce需要75*1*8/10=60秒。相比之下有很大的改进。

All to All 模式

All to All的模式是每台机器和每台机器都得建立一个连接。

初始状态是这样:

  value1 value2 value3 value4
机器1 1 3 2 1
机器2 2 5 4 5
机器3 8 10 9 7
机器4 6 2 3 6

然后,第i行的数据都汇总到第i%n台机器上。(n为机器数)
如下表所示。红色的代表新修改的值。

  value1 value2 value3 value4
机器1 17 3 2 1
机器2 2 20 4 5
机器3 8 10 18 7
机器4 6 2 3 19

然后broadcast出去

  value1 value2 value3 value4
机器1 17 20 18 19
机器2 17 20 18 19
机器3 17 20 18 19
机器4 17 20 18 19

然后还是按上面的例子算下时间。可以发现,网络开销和机器数量无关。每台机器都需要传输大约2GB*(1-1/n)的数据出去,接收1GB * (1-1/n)的数据进来。所以,大约2秒就可以完成。

汇总比较一下:

  所需时间
传统方法 60秒*2
Tree 10秒*2
All to All 2秒

结合实际

Yahoo的vowpal wabbit是率先把tree allreduce与hadoop结合起来。

spark在reduce阶段提供了tree的模式,实现方法是通过多轮的map-reduce。在broadcast阶段,它默认采用bittorrent的方式做broadcast,这也算是一大创举吧

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥