[SPARK-2174] Implement treeReduce and treeAggregate

• Type: New Feature
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.1.0
• Component/s: MLlib, Spark Core
• Target Version/s: 1.1.0
• Assignee: Xiangrui Meng
• Reporter: Xiangrui Meng
• Created: 17/Jun/14 23:39
• Updated: 29/Jul/14 08:17
• Resolved: 29/Jul/14 08:17

Description

In `reduce` and `aggregate`, the driver node spends linear time on the number of partitions. It becomes a bottleneck when there are many partitions and the data from each partition is big.

SPARK-1485 tracks the progress of implementing AllReduce on Spark. I did several implementations including butterfly, reduce + broadcast, and treeReduce + broadcast. treeReduce + BT broadcast seems to be right way to go for Spark. Using binary tree may introduce some overhead in communication, because the driver still need to coordinate on data shuffling. In my experiments, n -> sqrt -> 1 gives the best performance in general. But it certainly needs more testing.

Issue Links

• relates to: SPARK-1485 Implement AllReduce
• links to: [Github] Pull Request #1110 (mengxr)