How to add two arrays in Java in parallel manner?

问题:

For example, there are two huge (length 2-3 million) of the array float [] or double []. Need them very quickly add up. How to do it? Are there any libraries for this?

回答1:

Employ a fixed thread-pool with the number of threads equaling the number of processor cores. Submit as many tasks as there are threads. Each task receives its index range it needs to sum. In the main thread collect the results from all Futures returned to you from ExecutorService.submit and sum them up to the final result.

回答2:

One approach can be to decide a splitting of the array, and let N threads read specified parts of array and find individual sums. A final thread can then add up all these individual sums for final output.

回答3:

I've not had to do much truly high-performance coding but there isn't really a lot of room for optimization here (unless I'm being naive) except to divide the list into n segments (1 for each core) and have each core come up with a subtotal and add the subtotals up. Now if you were being asked to multiply the values, as soon as a worker encounters a 0, you have your answer.

public class ArrayAdder {
    public double getTotal(double[] array) {
        Worker workers[] = new Worker[Runtime.getRuntime().availableProcessors()];
        for (int i = 0; i < workers.length - 1;i++) {
            workers[i] = new Worker(array, 
                    i * array.length / workers.length,
                    (i + 1) * array.length / workers.length);
        }
        workers[workers.length - 1] = new Worker(array, 
                (workers.length - 1) * array.length / workers.length,array.length);
        double total = 0;
        for (int i = 0;i < workers.length;i++) {
            try {
                workers[i].join();
                total += workers[i].getSum();
            } catch (InterruptedException e) {
                i--; //retry the wait for worker[i]
            }

        }
        return total;

    }
    static class Worker extends Thread {
        public Worker(double[] array, int start, int end) {
            super();
            this.array = array;
            this.start = start;
            this.end = end;
            start();
        }
        private double[] array;
        private int start;
        private int end;
        private double sum;
        @Override
        public void run() {
            for (int i=start;i < end;i++) {
                sum += array[i];
            }

        }
        public double getSum() { return sum; }
    }
}

You might want to store the subtotals and total as a BigDecimal depending on how large you expect the values to be. Of course, unless you need an exact answer, adding them up as ints/longs would be much faster - obviously you'd want to round and not just cast or just cast (which may be faster) and assume you answer will be low by ~ array.length / 2 as half the time, the cast will "round" it in the incorrect direction.

回答4:

Use the Fork/Join framework in Java7.

回答5:

Another possible optimisation might be to try to use the superscalar abilities of your CPU by partially unrolling your loop.

For instance, on an architecture (and if the JVM is intelligent) with a pipeline size of four ints, you could write :

for(int i = 0; i < array.size(); i += 4)
{
    c[i] = a[i] + b[i];
    c[i+1] = a[i+1] + b[i+1];
    c[i+2] = a[i+2] + b[i+2];
    c[i+3] = a[i+3] + b[i+3];
}

But you have to write different code for every different architecture pipeline size.