Fork/Join

Fork/Join abstraction creates a framework for solving //divide and conquer// algorithms.



Parallel.ForkJoin will create a computation pool into which you can submit requests (subtasks). Each subtask can create multiple sub-subtasks which are again committed into the computation pool.

See also demos 44_Fork-Join Quicksort and 45_Fork-Join max.

A typical fork/join usage pattern is:

- Execute multiple subtasks.

- Wait for subtasks to terminate.

- Collect subtask results.

- Use results to compute higher-level result.

The trick here is that subtasks may spawn new subtasks and so on ad infinitum (probably a little less, or you'll run out of stack ;) ). For optimum execution, fork/join must therefore guarantee that the code is never running on too many background threads (an optimal value is usually equal to the number of cores in the system) and that those threads don't run out of work.

To achieve this, ForkJoin creates multiple worker threads and connects them to a computation pool. Computation requests (i.e. subtasks) are added to this pool. They are removed by worker threads, processed and optional new subtasks are added back to the pool.

ForkJoin programs typically use lots of stack space so it is advised to increase Maximum Stack Size
setting in project options.

IOmniForkJoin

Fork/join computation pool is implemented by the IOmniForkJoin interface and is created in the Parallel.ForkJoin factory function. There are two ForkJoin overloads – one is used for computations that don't return a result and another is used for computations that return a result of some type T.

class function ForkJoin: IOmniForkJoin; overload;
class function ForkJoin<T>: IOmniForkJoin<T>; overload;

Both interfaces declare just few methods.

IOmniForkJoin = interface
  function  Compute(action: TOmniForkJoinDelegate): IOmniCompute;
  function  NumTasks(numTasks: integer): IOmniForkJoin;
  function  TaskConfig(const config: IOmniTaskConfig): IOmniForkJoin;
end; 
 
IOmniForkJoin<T> = interface
  function  Compute(action: TOmniForkJoinDelegate<T>): IOmniCompute<T>;
  function  NumTasks(numTasks: integer): IOmniForkJoin<T>;
  function  TaskConfig(const config: IOmniTaskConfig): IOmniForkJoin<T>;
end; 

Compute creates new subtasks executing the action and returns control interface IOmniCompute (or IOmniCompute<T>).

By calling NumTasks, you can set the degree of parallelism. By default, fork/join uses as many threads as there are cores accessible by the process.

TaskConfig method is used to set up a task configuration block, applied to each worker task.

IOmniCompute

The IOmniCompute interface provides interaction with the computation unit that doesn't return a result.

IOmniCompute = interface
  procedure Execute;
  function  IsDone: boolean;
  procedure Await;
end; 

Execute executes the action that was provided to the Compute method. This method is used internally and should not be called from the user code.

IsDone verifies if the computation unit has completed the work.

Await waits for the computation unit to complete the work.

IOmniCompute\<T>

The IOmniCompute<T> interface provides interaction with the computation unit that returns a result.

IOmniCompute<T> = interface
  procedure Execute;
  function  IsDone: boolean;
  function  TryValue(timeout_ms: cardinal; var value: T): boolean;
  function  Value: T;
end;

Execute executes the action that was provided to the Compute method. This method is used internally and should not be called from the user code.

IsDone verifies if the computation unit has completed the work.

TryValue waits for up to timeout_ms milliseconds (or as long as needed if INFINITE is passed for this parameter) for the computation to complete and returns the result (if available) in the value parameter. Returns True if result is known, False otherwise.

Value returns the computation unit result. This function will block until the result is available.

Exceptions

There's no special exception handling built into the fork/join abstraction at the moment. You should always catch and handle exceptions inside the action passed to the Compute method.

Examples

Practical examples of Fork/Join usage can be found in chapter QuickSort and Parallel Max.

book/highlevel/forkjoin.txt · Last modified: 2013/03/06 02:12 by gabr
Recent changes RSS feed Debian Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki