聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

Reduce, Broadcast and AllReduce

2015-08-12 05:10 浏览: 1680509 次 我要评论(0 条) 字号:

在做机器学习的时候,经常要做这样一个操作:每台机器计算出一个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需要7518/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秒

这就是MPI为什么能比Spark快10倍,而Spark又比很多传统的程序快10倍……



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复