apache/spark — pull request #506 by mengxr (2014-04-23 10:02:13+00:00)
Title: [SPARK-1485][MLLIB] Implement Butterfly AllReduce

The current implementations of machine learning algorithms rely on the driver for some computation and data broadcasting. This may create a bottleneck at the driver for both computation and communication, especially in multi-model training. An efficient implementation of AllReduce can help free up the driver. This PR contains a simple butterfly AllReduce implementation. Compared it with reduce + broadcast (http) on a 16-node EC2 cluster (with slow connection), and saw 2x speed-up on vectors of size 1k to 10m.

Possible improvements:

1. Each executor only needs one copy.
2. Better handling when the number of partitions is not a power of two?