Threading block [5] -- reduce

第四课：parallel_reduce

前面的paralle_for只对单个element进行操作，是最容易进行并行化的问题，大多数问题并不是这样，比如要把所有的数加在一起:) 这个就是parallel_reduce发力的地方了。最简单的函数如下：

int serial_sum_foo (int a[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += foo(a[i]);
    }
    return sum;
}


用parallel_reduce实现如下：

    SumFoo sf(a);
    parallel_reduce(blocked_size<size_t>(0, n), sf);
    return sf.sum_;

class SumFoo
{
    int *a_;
public:
    int sum_;
    void operator() (blocked_range& r) {
        int sum = sum_;        /* explicit internal */
        for (int i = r.begin(); i != r.end(); ++i) {
            sum += foo(a[i]);
        }
        sum_ = sum;
    }
    void join (const SumFoo& x) { sum_ += x.sum_; }

    SumFoo(SumFoo& x, split) : a_(x.a_), sum_(0) {}
    SumFoo(int a[]) : a_(a), sum_(0) {}
};


从上面可以看出parallel_reduce的functor比parallel_for多了一个join()。reduce是采用了split-join的方式，类似quick-sort首先将一个range split为两部分，然后递归处理，第一部分处理完成后等待第二部分的join，即x.join(y)，最后return x；当然实际的情况比这个复杂，并不能保证一个SumFoo只完成一个range，由于可以临时无法创建worker，同一个SumFoo对多个split后的range作Operator(). 但是join的顺序是可以保证的，也就是对于strcat以上的paralle_reduce也是可以work的。

parallel_reduce的定义如下：

template<typename Range, typename Body>
void parallel_reduce(const Range& range, Body& body,
                     const auto_partitioner& partitioner)