java - 程序的并行化增加了执行时间

Question

我正在 coursera 上学习莱斯大学提供的关于并行编程的类(class)。在赋值中，我们应该递归地计算数组元素的倒数和。为了并行化，我们使用了 fork/join 池并递归计算左右子数组所需的总和并将它们连接回来。但我得到的执行时间比顺序执行时要长。以下是 eclipse 中的控制台输出 -

连续时间:0.136，值:7.485471并行时间:6.674，值:7.485471

代码如下 -

package edu.coursera.parallel;

import java.util.Random;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

/**
 * Class wrapping methods for implementing reciprocal array sum in parallel.
 */
public final class ReciprocalArraySum
{

    /**
     * Default constructor.
     */
    private ReciprocalArraySum()
    {
    }

    /**
     * Sequentially compute the sum of the reciprocal values for a given array.
     *
     * @param input Input array
     * @return The sum of the reciprocals of the array input
     */
    protected static double seqArraySum(final double[] input)
    {
        double sum = 0;

        // Compute sum of reciprocals of array elements
        for (int i = 0; i < input.length; i++)
        {
            sum += (1 / input[i]);
        }

        return sum;
    }

    /**
     * Computes the size of each chunk, given the number of chunks to create
     * across a given number of elements.
     *
     * @param nChunks The number of chunks to create
     * @param nElements The number of elements to chunk across
     * @return The default chunk size
     */
    private static int getChunkSize(final int nChunks, final int nElements)
    {
        // Integer ceil
        return (nElements + nChunks - 1) / nChunks;
    }

    /**
     * Computes the inclusive element index that the provided chunk starts at,
     * given there are a certain number of chunks.
     *
     * @param chunk The chunk to compute the start of
     * @param nChunks The number of chunks created
     * @param nElements The number of elements to chunk across
     * @return The inclusive index that this chunk starts at in the set of
     *         nElements
     */
    private static int getChunkStartInclusive(final int chunk, final int nChunks, final int nElements)
    {
        final int chunkSize = getChunkSize(nChunks, nElements);
        return chunk * chunkSize;
    }

    /**
     * Computes the exclusive element index that the provided chunk ends at,
     * given there are a certain number of chunks.
     *
     * @param chunk The chunk to compute the end of
     * @param nChunks The number of chunks created
     * @param nElements The number of elements to chunk across
     * @return The exclusive end index for this chunk
     */
    private static int getChunkEndExclusive(final int chunk, final int nChunks, final int nElements)
    {
        final int chunkSize = getChunkSize(nChunks, nElements);
        final int end = (chunk + 1) * chunkSize;
        if (end > nElements)
        {
            return nElements;
        }
        else
        {
            return end;
        }
    }

    /**
     * This class stub can be filled in to implement the body of each task
     * created to perform reciprocal array sum in parallel.
     */
    private static class ReciprocalArraySumTask extends RecursiveAction
    {
        /**
         * Starting index for traversal done by this task.
         */
        private final int startIndexInclusive;
        /**
         * Ending index for traversal done by this task.
         */
        private final int endIndexExclusive;
        /**
         * Input array to reciprocal sum.
         */
        private final double[] input;
        /**
         * Intermediate value produced by this task.
         */
        private double value;

        /**
         * Constructor.
         * @param setStartIndexInclusive Set the starting index to begin
         *        parallel traversal at.
         * @param setEndIndexExclusive Set ending index for parallel traversal.
         * @param setInput Input values
         */
        ReciprocalArraySumTask(final int setStartIndexInclusive, final int setEndIndexExclusive, final double[] setInput)
        {
            this.startIndexInclusive = setStartIndexInclusive;
            this.endIndexExclusive = setEndIndexExclusive;
            this.input = setInput;
        }

        /**
         * Getter for the value produced by this task.
         * @return Value produced by this task
         */
        public double getValue()
        {
            return value;
        }

        @Override
        protected void compute()
        {
            // TODO
            if((endIndexExclusive - startIndexInclusive) <= (input.length/5))
            {
                for(int i=startIndexInclusive;i<endIndexExclusive;i++)
                {
                    value+=(1/input[i]);
                }
            }
            else
            {
                int mid = ((startIndexInclusive+endIndexExclusive)/2);
                ReciprocalArraySumTask l = new ReciprocalArraySumTask(startIndexInclusive, mid, input);
                ReciprocalArraySumTask r = new ReciprocalArraySumTask(mid, endIndexExclusive, input);
                l.fork();
                r.fork();
                l.join();
                r.join();
                value = l.getValue()+r.getValue();
            }
        }
    }

    /**
     * TODO: Modify this method to compute the same reciprocal sum as
     * seqArraySum, but use two tasks running in parallel under the Java Fork
     * Join framework. You may assume that the length of the input array is
     * evenly divisible by 2.
     *
     * @param input Input array
     * @return The sum of the reciprocals of the array input
     */
    protected static double parArraySum(final double[] input)
    {
        assert input.length % 2 == 0;
        double sum = 0.0;
        // Compute sum of reciprocals of array elements
        /*for(int i=0;i<input.length;i++)
        {
            sum+=(1/input[i]);
        }*/
        ReciprocalArraySumTask t = new ReciprocalArraySumTask(0,input.length,input);
        t.compute();
        sum = t.getValue();
        return sum;
    }

    /**
     * TODO: Extend the work you did to implement parArraySum to use a set
     * number of tasks to compute the reciprocal array sum. You may find the
     * above utilities getChunkStartInclusive and getChunkEndExclusive helpful
     * in computing the range of element indices that belong to each chunk.
     *
     * @param input Input array
     * @param numTasks The number of tasks to create
     * @return The sum of the reciprocals of the array input
     */
    protected static double parManyTaskArraySum(final double[] input, final int numTasks)
    {
        double sum = 0;

        // Compute sum of reciprocals of array elements
        for (int i = 0; i < input.length; i++)
        {
            sum += 1 / input[i];
        }

        return sum;
    }

    public static void main(String[] args)
    {
        ReciprocalArraySum r = new ReciprocalArraySum();
        double[] imp = new double[1000];
        Random rGen = new Random();
        for(int i=0;i<1000;i++)
        {
            imp[i] = (i+1);
        }
        long startTimeSeq = System.nanoTime();
        double value = r.seqArraySum(imp);
        long endTimeSeq = System.nanoTime();
        System.out.printf("Time for sequential: %4.3f , Value: %f\n",(endTimeSeq-startTimeSeq)/1e6,value);

        long startTimePar = System.nanoTime();
        value = r.parArraySum(imp);
        long endTimePar = System.nanoTime();
        System.out.printf("Time for parallel: %4.3f , Value: %f",(endTimePar-startTimePar)/1e6,value);
    }
}

Answer 1

您正在为每个 fork() 使用 join()。 加入() stalls the program甚至使用 Java 8。尝试使用 CountedCompleter类(class)。这是一种分散-聚集的形式，不会停滞。它是流中使用的 join() 的替代品。