Uploaded image for project: 'Spark'
  1. Spark
  2. SPARK-2174

Implement treeReduce and treeAggregate

    Details

    • Type: New Feature
    • Status: Resolved
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 1.1.0
    • Component/s: MLlib, Spark Core
    • Labels:
      None
    • Target Version/s:

      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.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                mengxr Xiangrui Meng
                Reporter:
                mengxr Xiangrui Meng
              • Votes:
                0 Vote for this issue
                Watchers:
                3 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: