Package ca.cgjennings.algo

Class SplitJoin

  • public abstract class SplitJoin
extends java.lang.Object
    Simplifies running an algorithm in parallel on multiple CPUs (or CPU cores). Like the fork-join model, it is used to break a problem into independent subproblems, the results of which are combined to produce a final result. Unlike the fork-join model, the split-join model only splits the problem up one time, whereas fork-join repeats the split recursively. The split-join model thus avoids some of the overhead of subproblem creation, but is more sensitive to having its performance degraded by a rate-limiting subproblem. The split-join model is typically more efficient than fork-join when the following conditions hold:
    1. All of the computational units have similar performance characteristics (multi-core CPUs, for example).
    2. The problem is CPU-bound so that performance is predictable.
    3. The problem can be broken down in roughly equal subproblems, each with the same computational complexity. (Or, more generally, each subproblem can be expected to complete in roughly the same amount of time.)

    A typical pattern for using SplitJoin is as follows:

    1. Obtain one of the available shared instances using getInstance().
    2. Call that instance's getIdealSplitCount() to determine the number of subproblems to create.
    3. Create an array or collection or Runnables or Callables, each of which will complete one subproblem.
    4. Use one of the run or evaluate methods to complete the subproblems (in parallel if possible). This will return when all of the subproblems have been completed.
    5. If necessary, combine the results of the subproblems.
    Since:
    3.0
    Author:
    Chris Jennings

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected SplitJoin()
      A constructor to be used by concrete subclasses.

    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      static SplitJoin createInstance()
      Returns a new SplitJoin instance suited to the platform.
      static SplitJoin createInstance​(int nThreads)
      Returns a new SplitJoin instance that will use the specified number of threads.
      void dispose()
      Provides a hint to this instance that it will no longer be used.
      abstract <V> java.util.List<V> evaluate​(java.util.Collection<? extends java.util.concurrent.Callable<V>> subproblems)
      Submits subproblems for completion.
      <V> java.util.List<V> evaluateUnchecked​(java.util.Collection<? extends java.util.concurrent.Callable<V>> subproblems)
      Submits subproblems as if by evaluate( subproblems ).
      abstract void execute​(java.lang.Runnable task)
      Runs a task.
      static boolean getHighPriorityThreadHint()
      Returns the value of a hint that indicates whether SplitJoins are allowed to create higher than normal priority threads.
      int getIdealSplitCount()
      Returns the ideal number of evenly divided subproblems to break problems into.
      static SplitJoin getInstance()
      Returns a SplitJoin instance suited to the platform.
      abstract void run​(java.lang.Runnable[] subproblems)
      Submits an array of subproblems for completion.
      abstract void run​(java.util.Collection<? extends java.lang.Runnable> subproblems)
      Submits a collection of subproblems for completion.
      void runUnchecked​(java.lang.Runnable[] subproblems)
      Submits subproblems as if by run( subproblems ).
      void runUnchecked​(java.util.Collection<? extends java.lang.Runnable> subproblems)
      Submits subproblems as if by run( subproblems ).
      static void setHighPriorityThreadHint​(boolean enable)
      Sets a hint as to whether the creation of higher than normal priority threads is allowed.
      static void setParallelExecutionEnabled​(boolean enable)
      Sets a hint as to whether to allow parallel execution of subproblems.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • SplitJoin

        protected SplitJoin()
        A constructor to be used by concrete subclasses. To get an instance of a suitable concrete subclass, use getInstance() or createInstance().

    • Method Detail

      • getInstance

        public static SplitJoin getInstance()
        Returns a SplitJoin instance suited to the platform.
        Returns:
        a suitable instance; it may be new or shared

      • createInstance

        public static SplitJoin createInstance()
        Returns a new SplitJoin instance suited to the platform. This instance is guaranteed not to be shared.
        Returns:
        a new instance suitable for parallelizing CPU bound tasks

      • createInstance

        public static SplitJoin createInstance​(int nThreads)
        Returns a new SplitJoin instance that will use the specified number of threads. This instance is guaranteed not to be shared, and is guaranteed to employ up to the specified number of threads (depending on the number of subproblems).
        Parameters:
        nThreads - the number of threads to be used
        Returns:
        a new instance that uses the specified number of threads
        Throws:
        java.lang.IllegalArgumentException - if the number of threads is not positive

      • run

        public abstract void run​(java.lang.Runnable[] subproblems)
                  throws java.util.concurrent.ExecutionException
        Submits an array of subproblems for completion. The subproblems will not return a result; if a return value is required for the join stage, submit Callables instead.
        Parameters:
        subproblems - the subproblems to complete
        Throws:
        java.util.concurrent.ExecutionException - if at least one subproblem throws an exception, then this method will wrap and throw one of those exceptions (which one cannot be guaranteed)

      • run

        public abstract void run​(java.util.Collection<? extends java.lang.Runnable> subproblems)
                  throws java.util.concurrent.ExecutionException
        Submits a collection of subproblems for completion. The subproblems will not return a result; if a return value is required for the join stage, submit Callables instead.
        Parameters:
        subproblems - the subproblems to complete
        Throws:
        java.util.concurrent.ExecutionException - if at least one subproblem throws an exception, then this method will wrap and throw one of those exceptions (which one cannot be guaranteed)

      • evaluate

        public abstract <V> java.util.List<V> evaluate​(java.util.Collection<? extends java.util.concurrent.Callable<V>> subproblems)
                                        throws java.util.concurrent.ExecutionException
        Submits subproblems for completion. Each subproblem is a callable that returns a value of type V. The return values of each subproblem will be returned in an array (in the same order as the subproblems).
        Type Parameters:
        V - the type of the value returned by each subproblem
        Parameters:
        subproblems - the problems to complete
        Returns:
        the individual return values from each subproblem
        Throws:
        java.util.concurrent.ExecutionException - if at least one subproblem throws an exception, then this method will wrap and throw one of those exceptions (which one cannot be guaranteed)

      • runUnchecked

        public void runUnchecked​(java.lang.Runnable[] subproblems)
        Submits subproblems as if by run( subproblems ). However, if one of the subproblems throws an exception, it will be thrown as an unchecked RuntimeException.
        Parameters:
        subproblems - the subproblems to complete
        Throws:
        java.lang.RuntimeException - if one of the subproblems throws an exception
        See Also:
        run(java.lang.Runnable[])

      • runUnchecked

        public void runUnchecked​(java.util.Collection<? extends java.lang.Runnable> subproblems)
        Submits subproblems as if by run( subproblems ). However, if one of the subproblems throws an exception, it will be thrown as an unchecked RuntimeException.
        Parameters:
        subproblems - the subproblems to complete
        Throws:
        java.lang.RuntimeException - if one of the subproblems throws an exception
        See Also:
        run(java.util.Collection)

      • evaluateUnchecked

        public <V> java.util.List<V> evaluateUnchecked​(java.util.Collection<? extends java.util.concurrent.Callable<V>> subproblems)
        Submits subproblems as if by evaluate( subproblems ). However, if one of the subproblems throws an exception, it will be thrown as an unchecked RuntimeException.
        Type Parameters:
        V - the type of the value returned by each subproblem
        Parameters:
        subproblems - the subproblems to complete
        Returns:
        the individual return values from each subproblem
        Throws:
        java.lang.RuntimeException - if one of the subproblems throws an exception
        See Also:
        evaluate(java.util.Collection)

      • execute

        public abstract void execute​(java.lang.Runnable task)
        Runs a task. The task may be run in another thread, in which case this method will not wait for the task to complete. The purpose of this method is to reuse a thread that would normally have been used for split-join tasks instead of creating a new Thread yourself. If there is an idle split-join thread available, then this method generally has lower overhead than creating a new thread.
        Parameters:
        task - the task to run in another thread

      • dispose

        public void dispose()
        Provides a hint to this instance that it will no longer be used. Calling this is not required, but may free up resources sooner than not calling it would. The effect of continuing to use this SplitJoin after disposing of it is undefined.

      • getIdealSplitCount

        public int getIdealSplitCount()
        Returns the ideal number of evenly divided subproblems to break problems into. (Since the SplitJoin is unaware of the nature of the problem being solved, it cannot guarantee the accuracy of this value. However, if each subproblem performs the same amount of work, the returned value should be close to the ideal value.)
        Returns:
        the number of subproblems that a problem should be broken into to achieve optimal wall clock execution times

      • setHighPriorityThreadHint

        public static void setHighPriorityThreadHint​(boolean enable)
        Sets a hint as to whether the creation of higher than normal priority threads is allowed. If true, then SplitJoin instances may try to creates threads with above average priority. Note that even if enabled, this is not guaranteed to have an effect.
        Parameters:
        enable - true to allow higher than normal priority threads

      • getHighPriorityThreadHint

        public static boolean getHighPriorityThreadHint()
        Returns the value of a hint that indicates whether SplitJoins are allowed to create higher than normal priority threads.
        Returns:
        the current value of the hint (default is true)

      • setParallelExecutionEnabled

        public static void setParallelExecutionEnabled​(boolean enable)
        Sets a hint as to whether to allow parallel execution of subproblems. This may be useful during debugging or to work around any hardware- or platform-specific issues that appear (such as CPU overheating). When set to false, future calls to getInstance() or createInstance() that create a new instance rather than share an existing one will return a SplitJoin implementation that executes subproblems serially in the calling thread. To guarantee that all SplitJoin instances run serially, this must value must be set before the first call to getInstance().
        Parameters:
        enable - allow parallel problem solving if true, disable if false (default is true)