在做机器学习的时候,经常要做这样一个操作:每台机器计算出一个vector,然后把这些vector汇总加起来,再广播回去
传统模式
如下面这组图所示:
总体来说,它可以分为两步:
- Reduce。 即map-reduce中的那个reduce。
- Broadcast。 把reduce的结果broadcast到所有节点。
直接以这样两步走的方式解决此问题会很低效。如果vector长度很大,那么负责汇聚的那个节点,就会成为性能瓶颈。
树状模式
于是就有了基于tree的map-reduce来解决这个问题。这种方式被广泛用在了Vowpal Wabbit和spark中。
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条评论, 我也要评论