changeset 7553:e83cdd58f1cf

8012647: Add Arrays.parallelPrefix (prefix sum, scan, cumulative sum) Reviewed-by: chegar, alanb, psandoz Contributed-by: Doug Lea <dl@cs.oswego.edu>, Tristan Yan <tristan.yan@oracle.com>, Chris Hegarty <chris.hegarty@oracle.com>
author chegar
date Wed, 26 Jun 2013 15:30:39 +0100
parents 0822bcddbd4f
children 71059bca036a
files src/share/classes/java/util/ArrayPrefixHelpers.java src/share/classes/java/util/Arrays.java test/java/util/Arrays/ParallelPrefix.java
diffstat 3 files changed, 1039 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/java/util/ArrayPrefixHelpers.java	Wed Jun 26 15:30:39 2013 +0100
@@ -0,0 +1,697 @@
+/*
+ * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package java.util;
+
+/*
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+import java.util.concurrent.ForkJoinPool;
+import java.util.concurrent.CountedCompleter;
+import java.util.function.BinaryOperator;
+import java.util.function.IntBinaryOperator;
+import java.util.function.LongBinaryOperator;
+import java.util.function.DoubleBinaryOperator;
+
+/**
+ * ForkJoin tasks to perform Arrays.parallelPrefix operations.
+ *
+ * @author Doug Lea
+ * @since 1.8
+ */
+class ArrayPrefixHelpers {
+    private ArrayPrefixHelpers() {}; // non-instantiable
+
+    /*
+     * Parallel prefix (aka cumulate, scan) task classes
+     * are based loosely on Guy Blelloch's original
+     * algorithm (http://www.cs.cmu.edu/~scandal/alg/scan.html):
+     *  Keep dividing by two to threshold segment size, and then:
+     *   Pass 1: Create tree of partial sums for each segment
+     *   Pass 2: For each segment, cumulate with offset of left sibling
+     *
+     * This version improves performance within FJ framework mainly by
+     * allowing the second pass of ready left-hand sides to proceed
+     * even if some right-hand side first passes are still executing.
+     * It also combines first and second pass for leftmost segment,
+     * and skips the first pass for rightmost segment (whose result is
+     * not needed for second pass).  It similarly manages to avoid
+     * requiring that users supply an identity basis for accumulations
+     * by tracking those segments/subtasks for which the first
+     * existing element is used as base.
+     *
+     * Managing this relies on ORing some bits in the pendingCount for
+     * phases/states: CUMULATE, SUMMED, and FINISHED. CUMULATE is the
+     * main phase bit. When false, segments compute only their sum.
+     * When true, they cumulate array elements. CUMULATE is set at
+     * root at beginning of second pass and then propagated down. But
+     * it may also be set earlier for subtrees with lo==0 (the left
+     * spine of tree). SUMMED is a one bit join count. For leafs, it
+     * is set when summed. For internal nodes, it becomes true when
+     * one child is summed.  When the second child finishes summing,
+     * we then moves up tree to trigger the cumulate phase. FINISHED
+     * is also a one bit join count. For leafs, it is set when
+     * cumulated. For internal nodes, it becomes true when one child
+     * is cumulated.  When the second child finishes cumulating, it
+     * then moves up tree, completing at the root.
+     *
+     * To better exploit locality and reduce overhead, the compute
+     * method loops starting with the current task, moving if possible
+     * to one of its subtasks rather than forking.
+     *
+     * As usual for this sort of utility, there are 4 versions, that
+     * are simple copy/paste/adapt variants of each other.  (The
+     * double and int versions differ from long version soley by
+     * replacing "long" (with case-matching)).
+     */
+
+    // see above
+    static final int CUMULATE = 1;
+    static final int SUMMED   = 2;
+    static final int FINISHED = 4;
+
+    /** The smallest subtask array partition size to use as threshold */
+    static final int MIN_PARTITION = 16;
+
+    static final class CumulateTask<T> extends CountedCompleter<Void> {
+        final T[] array;
+        final BinaryOperator<T> function;
+        CumulateTask<T> left, right;
+        T in, out;
+        final int lo, hi, origin, fence, threshold;
+
+        /** Root task constructor */
+        public CumulateTask(CumulateTask<T> parent,
+                            BinaryOperator<T> function,
+                            T[] array, int lo, int hi) {
+            super(parent);
+            this.function = function; this.array = array;
+            this.lo = this.origin = lo; this.hi = this.fence = hi;
+            int p;
+            this.threshold =
+                    (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3))
+                    <= MIN_PARTITION ? MIN_PARTITION : p;
+        }
+
+        /** Subtask constructor */
+        CumulateTask(CumulateTask<T> parent, BinaryOperator<T> function,
+                     T[] array, int origin, int fence, int threshold,
+                     int lo, int hi) {
+            super(parent);
+            this.function = function; this.array = array;
+            this.origin = origin; this.fence = fence;
+            this.threshold = threshold;
+            this.lo = lo; this.hi = hi;
+        }
+
+        public final void compute() {
+            final BinaryOperator<T> fn;
+            final T[] a;
+            if ((fn = this.function) == null || (a = this.array) == null)
+                throw new NullPointerException();    // hoist checks
+            int th = threshold, org = origin, fnc = fence, l, h;
+            CumulateTask<T> t = this;
+            outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) {
+                if (h - l > th) {
+                    CumulateTask<T> lt = t.left, rt = t.right, f;
+                    if (lt == null) {                // first pass
+                        int mid = (l + h) >>> 1;
+                        f = rt = t.right =
+                                new CumulateTask<T>(t, fn, a, org, fnc, th, mid, h);
+                        t = lt = t.left  =
+                                new CumulateTask<T>(t, fn, a, org, fnc, th, l, mid);
+                    }
+                    else {                           // possibly refork
+                        T pin = t.in;
+                        lt.in = pin;
+                        f = t = null;
+                        if (rt != null) {
+                            T lout = lt.out;
+                            rt.in = (l == org ? lout :
+                                     fn.apply(pin, lout));
+                            for (int c;;) {
+                                if (((c = rt.getPendingCount()) & CUMULATE) != 0)
+                                    break;
+                                if (rt.compareAndSetPendingCount(c, c|CUMULATE)){
+                                    t = rt;
+                                    break;
+                                }
+                            }
+                        }
+                        for (int c;;) {
+                            if (((c = lt.getPendingCount()) & CUMULATE) != 0)
+                                break;
+                            if (lt.compareAndSetPendingCount(c, c|CUMULATE)) {
+                                if (t != null)
+                                    f = t;
+                                t = lt;
+                                break;
+                            }
+                        }
+                        if (t == null)
+                            break;
+                    }
+                    if (f != null)
+                        f.fork();
+                }
+                else {
+                    int state; // Transition to sum, cumulate, or both
+                    for (int b;;) {
+                        if (((b = t.getPendingCount()) & FINISHED) != 0)
+                            break outer;                      // already done
+                        state = ((b & CUMULATE) != 0? FINISHED :
+                                 (l > org) ? SUMMED : (SUMMED|FINISHED));
+                        if (t.compareAndSetPendingCount(b, b|state))
+                            break;
+                    }
+
+                    T sum;
+                    if (state != SUMMED) {
+                        int first;
+                        if (l == org) {                       // leftmost; no in
+                            sum = a[org];
+                            first = org + 1;
+                        }
+                        else {
+                            sum = t.in;
+                            first = l;
+                        }
+                        for (int i = first; i < h; ++i)       // cumulate
+                            a[i] = sum = fn.apply(sum, a[i]);
+                    }
+                    else if (h < fnc) {                       // skip rightmost
+                        sum = a[l];
+                        for (int i = l + 1; i < h; ++i)       // sum only
+                            sum = fn.apply(sum, a[i]);
+                    }
+                    else
+                        sum = t.in;
+                    t.out = sum;
+                    for (CumulateTask<T> par;;) {             // propagate
+                        if ((par = (CumulateTask<T>)t.getCompleter()) == null) {
+                            if ((state & FINISHED) != 0)      // enable join
+                                t.quietlyComplete();
+                            break outer;
+                        }
+                        int b = par.getPendingCount();
+                        if ((b & state & FINISHED) != 0)
+                            t = par;                          // both done
+                        else if ((b & state & SUMMED) != 0) { // both summed
+                            int nextState; CumulateTask<T> lt, rt;
+                            if ((lt = par.left) != null &&
+                                (rt = par.right) != null) {
+                                T lout = lt.out;
+                                par.out = (rt.hi == fnc ? lout :
+                                           fn.apply(lout, rt.out));
+                            }
+                            int refork = (((b & CUMULATE) == 0 &&
+                                           par.lo == org) ? CUMULATE : 0);
+                            if ((nextState = b|state|refork) == b ||
+                                par.compareAndSetPendingCount(b, nextState)) {
+                                state = SUMMED;               // drop finished
+                                t = par;
+                                if (refork != 0)
+                                    par.fork();
+                            }
+                        }
+                        else if (par.compareAndSetPendingCount(b, b|state))
+                            break outer;                      // sib not ready
+                    }
+                }
+            }
+        }
+    }
+
+    static final class LongCumulateTask extends CountedCompleter<Void> {
+        final long[] array;
+        final LongBinaryOperator function;
+        LongCumulateTask left, right;
+        long in, out;
+        final int lo, hi, origin, fence, threshold;
+
+        /** Root task constructor */
+        public LongCumulateTask(LongCumulateTask parent,
+                                LongBinaryOperator function,
+                                long[] array, int lo, int hi) {
+            super(parent);
+            this.function = function; this.array = array;
+            this.lo = this.origin = lo; this.hi = this.fence = hi;
+            int p;
+            this.threshold =
+                    (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3))
+                    <= MIN_PARTITION ? MIN_PARTITION : p;
+        }
+
+        /** Subtask constructor */
+        LongCumulateTask(LongCumulateTask parent, LongBinaryOperator function,
+                         long[] array, int origin, int fence, int threshold,
+                         int lo, int hi) {
+            super(parent);
+            this.function = function; this.array = array;
+            this.origin = origin; this.fence = fence;
+            this.threshold = threshold;
+            this.lo = lo; this.hi = hi;
+        }
+
+        public final void compute() {
+            final LongBinaryOperator fn;
+            final long[] a;
+            if ((fn = this.function) == null || (a = this.array) == null)
+                throw new NullPointerException();    // hoist checks
+            int th = threshold, org = origin, fnc = fence, l, h;
+            LongCumulateTask t = this;
+            outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) {
+                if (h - l > th) {
+                    LongCumulateTask lt = t.left, rt = t.right, f;
+                    if (lt == null) {                // first pass
+                        int mid = (l + h) >>> 1;
+                        f = rt = t.right =
+                                new LongCumulateTask(t, fn, a, org, fnc, th, mid, h);
+                        t = lt = t.left  =
+                                new LongCumulateTask(t, fn, a, org, fnc, th, l, mid);
+                    }
+                    else {                           // possibly refork
+                        long pin = t.in;
+                        lt.in = pin;
+                        f = t = null;
+                        if (rt != null) {
+                            long lout = lt.out;
+                            rt.in = (l == org ? lout :
+                                     fn.applyAsLong(pin, lout));
+                            for (int c;;) {
+                                if (((c = rt.getPendingCount()) & CUMULATE) != 0)
+                                    break;
+                                if (rt.compareAndSetPendingCount(c, c|CUMULATE)){
+                                    t = rt;
+                                    break;
+                                }
+                            }
+                        }
+                        for (int c;;) {
+                            if (((c = lt.getPendingCount()) & CUMULATE) != 0)
+                                break;
+                            if (lt.compareAndSetPendingCount(c, c|CUMULATE)) {
+                                if (t != null)
+                                    f = t;
+                                t = lt;
+                                break;
+                            }
+                        }
+                        if (t == null)
+                            break;
+                    }
+                    if (f != null)
+                        f.fork();
+                }
+                else {
+                    int state; // Transition to sum, cumulate, or both
+                    for (int b;;) {
+                        if (((b = t.getPendingCount()) & FINISHED) != 0)
+                            break outer;                      // already done
+                        state = ((b & CUMULATE) != 0? FINISHED :
+                                 (l > org) ? SUMMED : (SUMMED|FINISHED));
+                        if (t.compareAndSetPendingCount(b, b|state))
+                            break;
+                    }
+
+                    long sum;
+                    if (state != SUMMED) {
+                        int first;
+                        if (l == org) {                       // leftmost; no in
+                            sum = a[org];
+                            first = org + 1;
+                        }
+                        else {
+                            sum = t.in;
+                            first = l;
+                        }
+                        for (int i = first; i < h; ++i)       // cumulate
+                            a[i] = sum = fn.applyAsLong(sum, a[i]);
+                    }
+                    else if (h < fnc) {                       // skip rightmost
+                        sum = a[l];
+                        for (int i = l + 1; i < h; ++i)       // sum only
+                            sum = fn.applyAsLong(sum, a[i]);
+                    }
+                    else
+                        sum = t.in;
+                    t.out = sum;
+                    for (LongCumulateTask par;;) {            // propagate
+                        if ((par = (LongCumulateTask)t.getCompleter()) == null) {
+                            if ((state & FINISHED) != 0)      // enable join
+                                t.quietlyComplete();
+                            break outer;
+                        }
+                        int b = par.getPendingCount();
+                        if ((b & state & FINISHED) != 0)
+                            t = par;                          // both done
+                        else if ((b & state & SUMMED) != 0) { // both summed
+                            int nextState; LongCumulateTask lt, rt;
+                            if ((lt = par.left) != null &&
+                                (rt = par.right) != null) {
+                                long lout = lt.out;
+                                par.out = (rt.hi == fnc ? lout :
+                                           fn.applyAsLong(lout, rt.out));
+                            }
+                            int refork = (((b & CUMULATE) == 0 &&
+                                           par.lo == org) ? CUMULATE : 0);
+                            if ((nextState = b|state|refork) == b ||
+                                par.compareAndSetPendingCount(b, nextState)) {
+                                state = SUMMED;               // drop finished
+                                t = par;
+                                if (refork != 0)
+                                    par.fork();
+                            }
+                        }
+                        else if (par.compareAndSetPendingCount(b, b|state))
+                            break outer;                      // sib not ready
+                    }
+                }
+            }
+        }
+    }
+
+    static final class DoubleCumulateTask extends CountedCompleter<Void> {
+        final double[] array;
+        final DoubleBinaryOperator function;
+        DoubleCumulateTask left, right;
+        double in, out;
+        final int lo, hi, origin, fence, threshold;
+
+        /** Root task constructor */
+        public DoubleCumulateTask(DoubleCumulateTask parent,
+                                  DoubleBinaryOperator function,
+                                  double[] array, int lo, int hi) {
+            super(parent);
+            this.function = function; this.array = array;
+            this.lo = this.origin = lo; this.hi = this.fence = hi;
+            int p;
+            this.threshold =
+                    (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3))
+                    <= MIN_PARTITION ? MIN_PARTITION : p;
+        }
+
+        /** Subtask constructor */
+        DoubleCumulateTask(DoubleCumulateTask parent, DoubleBinaryOperator function,
+                           double[] array, int origin, int fence, int threshold,
+                           int lo, int hi) {
+            super(parent);
+            this.function = function; this.array = array;
+            this.origin = origin; this.fence = fence;
+            this.threshold = threshold;
+            this.lo = lo; this.hi = hi;
+        }
+
+        public final void compute() {
+            final DoubleBinaryOperator fn;
+            final double[] a;
+            if ((fn = this.function) == null || (a = this.array) == null)
+                throw new NullPointerException();    // hoist checks
+            int th = threshold, org = origin, fnc = fence, l, h;
+            DoubleCumulateTask t = this;
+            outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) {
+                if (h - l > th) {
+                    DoubleCumulateTask lt = t.left, rt = t.right, f;
+                    if (lt == null) {                // first pass
+                        int mid = (l + h) >>> 1;
+                        f = rt = t.right =
+                                new DoubleCumulateTask(t, fn, a, org, fnc, th, mid, h);
+                        t = lt = t.left  =
+                                new DoubleCumulateTask(t, fn, a, org, fnc, th, l, mid);
+                    }
+                    else {                           // possibly refork
+                        double pin = t.in;
+                        lt.in = pin;
+                        f = t = null;
+                        if (rt != null) {
+                            double lout = lt.out;
+                            rt.in = (l == org ? lout :
+                                     fn.applyAsDouble(pin, lout));
+                            for (int c;;) {
+                                if (((c = rt.getPendingCount()) & CUMULATE) != 0)
+                                    break;
+                                if (rt.compareAndSetPendingCount(c, c|CUMULATE)){
+                                    t = rt;
+                                    break;
+                                }
+                            }
+                        }
+                        for (int c;;) {
+                            if (((c = lt.getPendingCount()) & CUMULATE) != 0)
+                                break;
+                            if (lt.compareAndSetPendingCount(c, c|CUMULATE)) {
+                                if (t != null)
+                                    f = t;
+                                t = lt;
+                                break;
+                            }
+                        }
+                        if (t == null)
+                            break;
+                    }
+                    if (f != null)
+                        f.fork();
+                }
+                else {
+                    int state; // Transition to sum, cumulate, or both
+                    for (int b;;) {
+                        if (((b = t.getPendingCount()) & FINISHED) != 0)
+                            break outer;                      // already done
+                        state = ((b & CUMULATE) != 0? FINISHED :
+                                 (l > org) ? SUMMED : (SUMMED|FINISHED));
+                        if (t.compareAndSetPendingCount(b, b|state))
+                            break;
+                    }
+
+                    double sum;
+                    if (state != SUMMED) {
+                        int first;
+                        if (l == org) {                       // leftmost; no in
+                            sum = a[org];
+                            first = org + 1;
+                        }
+                        else {
+                            sum = t.in;
+                            first = l;
+                        }
+                        for (int i = first; i < h; ++i)       // cumulate
+                            a[i] = sum = fn.applyAsDouble(sum, a[i]);
+                    }
+                    else if (h < fnc) {                       // skip rightmost
+                        sum = a[l];
+                        for (int i = l + 1; i < h; ++i)       // sum only
+                            sum = fn.applyAsDouble(sum, a[i]);
+                    }
+                    else
+                        sum = t.in;
+                    t.out = sum;
+                    for (DoubleCumulateTask par;;) {            // propagate
+                        if ((par = (DoubleCumulateTask)t.getCompleter()) == null) {
+                            if ((state & FINISHED) != 0)      // enable join
+                                t.quietlyComplete();
+                            break outer;
+                        }
+                        int b = par.getPendingCount();
+                        if ((b & state & FINISHED) != 0)
+                            t = par;                          // both done
+                        else if ((b & state & SUMMED) != 0) { // both summed
+                            int nextState; DoubleCumulateTask lt, rt;
+                            if ((lt = par.left) != null &&
+                                (rt = par.right) != null) {
+                                double lout = lt.out;
+                                par.out = (rt.hi == fnc ? lout :
+                                           fn.applyAsDouble(lout, rt.out));
+                            }
+                            int refork = (((b & CUMULATE) == 0 &&
+                                           par.lo == org) ? CUMULATE : 0);
+                            if ((nextState = b|state|refork) == b ||
+                                par.compareAndSetPendingCount(b, nextState)) {
+                                state = SUMMED;               // drop finished
+                                t = par;
+                                if (refork != 0)
+                                    par.fork();
+                            }
+                        }
+                        else if (par.compareAndSetPendingCount(b, b|state))
+                            break outer;                      // sib not ready
+                    }
+                }
+            }
+        }
+    }
+
+    static final class IntCumulateTask extends CountedCompleter<Void> {
+        final int[] array;
+        final IntBinaryOperator function;
+        IntCumulateTask left, right;
+        int in, out;
+        final int lo, hi, origin, fence, threshold;
+
+        /** Root task constructor */
+        public IntCumulateTask(IntCumulateTask parent,
+                               IntBinaryOperator function,
+                               int[] array, int lo, int hi) {
+            super(parent);
+            this.function = function; this.array = array;
+            this.lo = this.origin = lo; this.hi = this.fence = hi;
+            int p;
+            this.threshold =
+                    (p = (hi - lo) / (ForkJoinPool.getCommonPoolParallelism() << 3))
+                    <= MIN_PARTITION ? MIN_PARTITION : p;
+        }
+
+        /** Subtask constructor */
+        IntCumulateTask(IntCumulateTask parent, IntBinaryOperator function,
+                        int[] array, int origin, int fence, int threshold,
+                        int lo, int hi) {
+            super(parent);
+            this.function = function; this.array = array;
+            this.origin = origin; this.fence = fence;
+            this.threshold = threshold;
+            this.lo = lo; this.hi = hi;
+        }
+
+        public final void compute() {
+            final IntBinaryOperator fn;
+            final int[] a;
+            if ((fn = this.function) == null || (a = this.array) == null)
+                throw new NullPointerException();    // hoist checks
+            int th = threshold, org = origin, fnc = fence, l, h;
+            IntCumulateTask t = this;
+            outer: while ((l = t.lo) >= 0 && (h = t.hi) <= a.length) {
+                if (h - l > th) {
+                    IntCumulateTask lt = t.left, rt = t.right, f;
+                    if (lt == null) {                // first pass
+                        int mid = (l + h) >>> 1;
+                        f = rt = t.right =
+                                new IntCumulateTask(t, fn, a, org, fnc, th, mid, h);
+                        t = lt = t.left  =
+                                new IntCumulateTask(t, fn, a, org, fnc, th, l, mid);
+                    }
+                    else {                           // possibly refork
+                        int pin = t.in;
+                        lt.in = pin;
+                        f = t = null;
+                        if (rt != null) {
+                            int lout = lt.out;
+                            rt.in = (l == org ? lout :
+                                     fn.applyAsInt(pin, lout));
+                            for (int c;;) {
+                                if (((c = rt.getPendingCount()) & CUMULATE) != 0)
+                                    break;
+                                if (rt.compareAndSetPendingCount(c, c|CUMULATE)){
+                                    t = rt;
+                                    break;
+                                }
+                            }
+                        }
+                        for (int c;;) {
+                            if (((c = lt.getPendingCount()) & CUMULATE) != 0)
+                                break;
+                            if (lt.compareAndSetPendingCount(c, c|CUMULATE)) {
+                                if (t != null)
+                                    f = t;
+                                t = lt;
+                                break;
+                            }
+                        }
+                        if (t == null)
+                            break;
+                    }
+                    if (f != null)
+                        f.fork();
+                }
+                else {
+                    int state; // Transition to sum, cumulate, or both
+                    for (int b;;) {
+                        if (((b = t.getPendingCount()) & FINISHED) != 0)
+                            break outer;                      // already done
+                        state = ((b & CUMULATE) != 0? FINISHED :
+                                 (l > org) ? SUMMED : (SUMMED|FINISHED));
+                        if (t.compareAndSetPendingCount(b, b|state))
+                            break;
+                    }
+
+                    int sum;
+                    if (state != SUMMED) {
+                        int first;
+                        if (l == org) {                       // leftmost; no in
+                            sum = a[org];
+                            first = org + 1;
+                        }
+                        else {
+                            sum = t.in;
+                            first = l;
+                        }
+                        for (int i = first; i < h; ++i)       // cumulate
+                            a[i] = sum = fn.applyAsInt(sum, a[i]);
+                    }
+                    else if (h < fnc) {                       // skip rightmost
+                        sum = a[l];
+                        for (int i = l + 1; i < h; ++i)       // sum only
+                            sum = fn.applyAsInt(sum, a[i]);
+                    }
+                    else
+                        sum = t.in;
+                    t.out = sum;
+                    for (IntCumulateTask par;;) {            // propagate
+                        if ((par = (IntCumulateTask)t.getCompleter()) == null) {
+                            if ((state & FINISHED) != 0)      // enable join
+                                t.quietlyComplete();
+                            break outer;
+                        }
+                        int b = par.getPendingCount();
+                        if ((b & state & FINISHED) != 0)
+                            t = par;                          // both done
+                        else if ((b & state & SUMMED) != 0) { // both summed
+                            int nextState; IntCumulateTask lt, rt;
+                            if ((lt = par.left) != null &&
+                                (rt = par.right) != null) {
+                                int lout = lt.out;
+                                par.out = (rt.hi == fnc ? lout :
+                                           fn.applyAsInt(lout, rt.out));
+                            }
+                            int refork = (((b & CUMULATE) == 0 &&
+                                           par.lo == org) ? CUMULATE : 0);
+                            if ((nextState = b|state|refork) == b ||
+                                par.compareAndSetPendingCount(b, nextState)) {
+                                state = SUMMED;               // drop finished
+                                t = par;
+                                if (refork != 0)
+                                    par.fork();
+                            }
+                        }
+                        else if (par.compareAndSetPendingCount(b, b|state))
+                            break outer;                      // sib not ready
+                    }
+                }
+            }
+        }
+    }
+
+
+}
\ No newline at end of file
--- a/src/share/classes/java/util/Arrays.java	Wed Jun 26 06:32:40 2013 -0700
+++ b/src/share/classes/java/util/Arrays.java	Wed Jun 26 15:30:39 2013 +0100
@@ -1559,6 +1559,183 @@
         }
     }
 
+    // Parallel prefix
+
+    /**
+     * Cumulates, in parallel, each element of the given array in place,
+     * using the supplied function. For example if the array initially
+     * holds {@code [2, 1, 0, 3]} and the operation performs addition,
+     * then upon return the array holds {@code [2, 3, 3, 6]}.
+     * Parallel prefix computation is usually more efficient than
+     * sequential loops for large arrays.
+     *
+     * @param array the array, which is modified in-place by this method
+     * @param op a side-effect-free, associative function to perform the
+     * cumulation
+     * @throws NullPointerException if the specified array or function is null
+     * @since 1.8
+     */
+    public static <T> void parallelPrefix(T[] array, BinaryOperator<T> op) {
+        if (array.length > 0)
+            new ArrayPrefixHelpers.CumulateTask<>
+                    (null, op, array, 0, array.length).invoke();
+    }
+
+    /**
+     * Performs {@link #parallelPrefix(Object[], BinaryOperator)}
+     * for the given subrange of the array.
+     *
+     * @param array the array
+     * @param fromIndex the index of the first element, inclusive
+     * @param toIndex the index of the last element, exclusive
+     * @param op a side-effect-free, associative function to perform the
+     * cumulation
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > array.length}
+     * @throws NullPointerException if the specified array or function is null
+     * @since 1.8
+     */
+    public static <T> void parallelPrefix(T[] array, int fromIndex,
+                                          int toIndex, BinaryOperator<T> op) {
+        rangeCheck(array.length, fromIndex, toIndex);
+        if (fromIndex < toIndex)
+            new ArrayPrefixHelpers.CumulateTask<>
+                    (null, op, array, fromIndex, toIndex).invoke();
+    }
+
+    /**
+     * Cumulates, in parallel, each element of the given array in place,
+     * using the supplied function. For example if the array initially
+     * holds {@code [2, 1, 0, 3]} and the operation performs addition,
+     * then upon return the array holds {@code [2, 3, 3, 6]}.
+     * Parallel prefix computation is usually more efficient than
+     * sequential loops for large arrays.
+     *
+     * @param array the array, which is modified in-place by this method
+     * @param op a side-effect-free, associative function to perform the
+     * cumulation
+     * @throws NullPointerException if the specified array or function is null
+     * @since 1.8
+     */
+    public static void parallelPrefix(long[] array, LongBinaryOperator op) {
+        if (array.length > 0)
+            new ArrayPrefixHelpers.LongCumulateTask
+                    (null, op, array, 0, array.length).invoke();
+    }
+
+    /**
+     * Performs {@link #parallelPrefix(long[], LongBinaryOperator)}
+     * for the given subrange of the array.
+     *
+     * @param array the array
+     * @param fromIndex the index of the first element, inclusive
+     * @param toIndex the index of the last element, exclusive
+     * @param op a side-effect-free, associative function to perform the
+     * cumulation
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > array.length}
+     * @throws NullPointerException if the specified array or function is null
+     * @since 1.8
+     */
+    public static void parallelPrefix(long[] array, int fromIndex,
+                                      int toIndex, LongBinaryOperator op) {
+        rangeCheck(array.length, fromIndex, toIndex);
+        if (fromIndex < toIndex)
+            new ArrayPrefixHelpers.LongCumulateTask
+                    (null, op, array, fromIndex, toIndex).invoke();
+    }
+
+    /**
+     * Cumulates, in parallel, each element of the given array in place,
+     * using the supplied function. For example if the array initially
+     * holds {@code [2.0, 1.0, 0.0, 3.0]} and the operation performs addition,
+     * then upon return the array holds {@code [2.0, 3.0, 3.0, 6.0]}.
+     * Parallel prefix computation is usually more efficient than
+     * sequential loops for large arrays.
+     *
+     * <p> Because floating-point operations may not be strictly associative,
+     * the returned result may not be identical to the value that would be
+     * obtained if the operation was performed sequentially.
+     *
+     * @param array the array, which is modified in-place by this method
+     * @param op a side-effect-free function to perform the cumulation
+     * @throws NullPointerException if the specified array or function is null
+     * @since 1.8
+     */
+    public static void parallelPrefix(double[] array, DoubleBinaryOperator op) {
+        if (array.length > 0)
+            new ArrayPrefixHelpers.DoubleCumulateTask
+                    (null, op, array, 0, array.length).invoke();
+    }
+
+    /**
+     * Performs {@link #parallelPrefix(double[], DoubleBinaryOperator)}
+     * for the given subrange of the array.
+     *
+     * @param array the array
+     * @param fromIndex the index of the first element, inclusive
+     * @param toIndex the index of the last element, exclusive
+     * @param op a side-effect-free, associative function to perform the
+     * cumulation
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > array.length}
+     * @throws NullPointerException if the specified array or function is null
+     * @since 1.8
+     */
+    public static void parallelPrefix(double[] array, int fromIndex,
+                                      int toIndex, DoubleBinaryOperator op) {
+        rangeCheck(array.length, fromIndex, toIndex);
+        if (fromIndex < toIndex)
+            new ArrayPrefixHelpers.DoubleCumulateTask
+                    (null, op, array, fromIndex, toIndex).invoke();
+    }
+
+    /**
+     * Cumulates, in parallel, each element of the given array in place,
+     * using the supplied function. For example if the array initially
+     * holds {@code [2, 1, 0, 3]} and the operation performs addition,
+     * then upon return the array holds {@code [2, 3, 3, 6]}.
+     * Parallel prefix computation is usually more efficient than
+     * sequential loops for large arrays.
+     *
+     * @param array the array, which is modified in-place by this method
+     * @param op a side-effect-free, associative function to perform the
+     * cumulation
+     * @throws NullPointerException if the specified array or function is null
+     * @since 1.8
+     */
+    public static void parallelPrefix(int[] array, IntBinaryOperator op) {
+        if (array.length > 0)
+            new ArrayPrefixHelpers.IntCumulateTask
+                    (null, op, array, 0, array.length).invoke();
+    }
+
+    /**
+     * Performs {@link #parallelPrefix(int[], IntBinaryOperator)}
+     * for the given subrange of the array.
+     *
+     * @param array the array
+     * @param fromIndex the index of the first element, inclusive
+     * @param toIndex the index of the last element, exclusive
+     * @param op a side-effect-free, associative function to perform the
+     * cumulation
+     * @throws IllegalArgumentException if {@code fromIndex > toIndex}
+     * @throws ArrayIndexOutOfBoundsException
+     *     if {@code fromIndex < 0} or {@code toIndex > array.length}
+     * @throws NullPointerException if the specified array or function is null
+     * @since 1.8
+     */
+    public static void parallelPrefix(int[] array, int fromIndex,
+                                      int toIndex, IntBinaryOperator op) {
+        rangeCheck(array.length, fromIndex, toIndex);
+        if (fromIndex < toIndex)
+            new ArrayPrefixHelpers.IntCumulateTask
+                    (null, op, array, fromIndex, toIndex).invoke();
+    }
+
     // Searching
 
     /**
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/Arrays/ParallelPrefix.java	Wed Jun 26 15:30:39 2013 +0100
@@ -0,0 +1,165 @@
+/*
+ * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/**
+ * @test
+ * @summary unit test for Arrays.ParallelPrefix().
+ * @author Tristan Yan
+ * @run testng ParallelPrefix
+ */
+
+import java.util.Arrays;
+import java.util.function.BinaryOperator;
+import java.util.function.DoubleBinaryOperator;
+import java.util.function.Function;
+import java.util.function.IntBinaryOperator;
+import java.util.function.LongBinaryOperator;
+import java.util.stream.IntStream;
+import java.util.stream.LongStream;
+import static org.testng.Assert.*;
+import org.testng.annotations.DataProvider;
+import org.testng.annotations.Test;
+
+public class ParallelPrefix {
+    //Array size less than MIN_PARTITION
+    private final static int SMALL_ARRAY_SIZE = 1 << 3;
+
+    //Array size equals MIN_PARTITION
+    private final static int THRESHOLD_ARRAY_SIZE = 1 << 4;
+
+    //Array size greater than MIN_PARTITION
+    private final static int MEDIUM_ARRAY_SIZE = 1 << 8;
+
+    //Array size much greater than MIN_PARTITION
+    private final static int LARGE_ARRAY_SIZE = 1 << 12;
+
+    private final static int[] ARRAY_SIZE_COLLECTION  = new int[]{
+        SMALL_ARRAY_SIZE, THRESHOLD_ARRAY_SIZE,MEDIUM_ARRAY_SIZE, LARGE_ARRAY_SIZE};
+
+    @DataProvider
+    public static Object[][] intSet(){
+        return genericData(size -> IntStream.range(0, size).toArray(), new IntBinaryOperator[]{Integer::sum, Integer::min});
+    }
+
+    @DataProvider
+    public static Object[][] longSet(){
+        return genericData(size -> LongStream.range(0, size).toArray(), new LongBinaryOperator[]{Long::sum, Long::min});
+    }
+
+    @DataProvider
+    public static Object[][] doubleSet(){
+        return genericData(size -> IntStream.range(0, size).mapToDouble(i -> (double)i).toArray(),
+                new DoubleBinaryOperator[]{Double::sum, Double::min});
+    }
+
+    @DataProvider
+    public static Object[][] stringSet(){
+        Function<Integer, String[]> stringsFunc = size ->
+                IntStream.range(0, size).mapToObj(Integer::toString).toArray(String[]::new);
+        BinaryOperator<String> cancatBop = String::concat;
+        return genericData(stringsFunc,  new BinaryOperator[]{cancatBop});
+    }
+
+    private static <T, OPS> Object[][] genericData(Function<Integer, T> generateFunc, OPS[] ops) {
+        //test arrays which size is equals n-1, n, n+1, test random data
+        Object[][] data = new Object[ARRAY_SIZE_COLLECTION.length * 3 * ops.length][4];
+        for(int n = 0; n < ARRAY_SIZE_COLLECTION.length; n++ ) {
+            for(int testValue = -1 ; testValue <= 1; testValue++) {
+                int array_size = ARRAY_SIZE_COLLECTION[n] + testValue;
+                for(int opsN = 0; opsN < ops.length; opsN++) {
+                    int index = n * 3 * ops.length + (testValue + 1) * ops.length + opsN;
+                    data[index][0] = generateFunc.apply(array_size);
+                    data[index][1] = array_size / 3;
+                    data[index][2] = 2 * array_size / 3;
+                    data[index][3] = ops[opsN];
+                }
+            }
+        }
+        return data;
+    }
+
+    @Test(dataProvider="intSet")
+    public void testParallelPrefixForInt(int[] data, int fromIndex, int toIndex, IntBinaryOperator op) {
+        int[] sequentialResult = data.clone();
+        for (int index = fromIndex + 1; index < toIndex; index++) {
+            sequentialResult[index ] = op.applyAsInt(sequentialResult[index  - 1], sequentialResult[index]);
+        }
+
+        int[] parallelResult = data.clone();
+        Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
+        assertEquals(parallelResult, sequentialResult);
+
+        int[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
+        Arrays.parallelPrefix(parallelRangeResult, op);
+        assertEquals(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
+    }
+
+    @Test(dataProvider="longSet")
+    public void testParallelPrefixForLong(long[] data, int fromIndex, int toIndex, LongBinaryOperator op) {
+        long[] sequentialResult = data.clone();
+        for (int index = fromIndex + 1; index < toIndex; index++) {
+            sequentialResult[index ] = op.applyAsLong(sequentialResult[index  - 1], sequentialResult[index]);
+        }
+
+        long[] parallelResult = data.clone();
+        Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
+        assertEquals(parallelResult, sequentialResult);
+
+        long[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
+        Arrays.parallelPrefix(parallelRangeResult, op);
+        assertEquals(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
+    }
+
+    @Test(dataProvider="doubleSet")
+    public void testParallelPrefixForDouble(double[] data, int fromIndex, int toIndex, DoubleBinaryOperator op) {
+        double[] sequentialResult = data.clone();
+        for (int index = fromIndex + 1; index < toIndex; index++) {
+            sequentialResult[index ] = op.applyAsDouble(sequentialResult[index  - 1], sequentialResult[index]);
+        }
+
+        double[] parallelResult = data.clone();
+        Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
+        assertEquals(parallelResult, sequentialResult);
+
+        double[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
+        Arrays.parallelPrefix(parallelRangeResult, op);
+        assertEquals(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
+    }
+
+    @Test(dataProvider="stringSet")
+    public void testParallelPrefixForStringr(String[] data , int fromIndex, int toIndex, BinaryOperator<String> op) {
+        String[] sequentialResult = data.clone();
+        for (int index = fromIndex + 1; index < toIndex; index++) {
+            sequentialResult[index ] = op.apply(sequentialResult[index  - 1], sequentialResult[index]);
+        }
+
+        String[] parallelResult = data.clone();
+        Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
+        assertEquals(parallelResult, sequentialResult);
+
+        String[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
+        Arrays.parallelPrefix(parallelRangeResult, op);
+        assertEquals(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
+    }
+}
+