org.amino.alg.parallelprefix
Class ThreadedParallelPrefix<T>

java.lang.Object
  org.amino.alg.parallelprefix.AbstractParallelPrefix<T>
      org.amino.alg.parallelprefix.ThreadedParallelPrefix<T>

Type Parameters:

T - Element type of array, if array is a non-primitive type. Irrelevant if array is of a primitive type.

All Implemented Interfaces:

ParallelPrefix<T>

public class ThreadedParallelPrefix<T>
extends AbstractParallelPrefix<T>

Threaded implementation of parallel-prefix operation.

Inspired by Guy E. Blelloch "Prefix Sums and Their Applications". In John H. Reif (Ed.), Synthesis of Parallel Algorithms, Morgan Kaufmann, 1990.

Implementation Details

There are three distinct passes: Two parallel reductions, and a recusive scan call. It is assumed that there are many more array elements than worker threads, and that there is at most a 1-to-1 mapping of threads to processing cores.

In the first pass, the input array is divided into M/N sequential chunks, where M is the number of elements in the array, and N the number of worker threads. A partial reduction is performed in parallel, the results going into a temporary work array of size M/N, with each element corresponding to a particular worker thread.

A recursive call to scan this work array is then performed.

Finally, each thread then adds the corresponding value to each of it's elements.

Author:

donawa

See Also:

ParallelPrefix

Nested Class Summary

class

ThreadedParallelPrefix.PartialReduction Class for performing partial reductions for Parallel-prefix operations across a pool of threads.

Field Summary

static int

DEFAULT_MINIMUM_ARRAY_SIZE minimum size.

Constructor Summary

ThreadedParallelPrefix()
Set number of worker threads to the number of availableProcessors.

ThreadedParallelPrefix(int nthreads)

Method Summary

int	getMinimumArraySize()
void	scan(byte[] inputArray, byte[] outputArray, BinaryOp<T> op) Perform a parallel-prefix operation on input array 'array'.
void	scan(char[] inputArray, char[] outputArray, BinaryOp<T> op) Perform a parallel-prefix operation on input array 'array'.
void	scan(double[] inputArray, double[] outputArray, BinaryOp<T> op) Perform a parallel-prefix operation on input array 'array'.
void	scan(float[] inputArray, float[] outputArray, BinaryOp<T> op) Perform a parallel-prefix operation on input array 'array'.
void	scan(int[] inputArray, int[] outputArray, BinaryOp<T> op) Perform a parallel-prefix operation on input array 'array'.
void	scan(long[] inputArray, long[] outputArray, BinaryOp<T> op) Perform a parallel-prefix operation on input array 'array'.
void	scan(short[] inputArray, short[] outputArray, BinaryOp<T> op) Perform a parallel-prefix operation on input array 'array'.
void	scan(T[] inputArray, T[] outputArray, BinaryOp<T> op) Perform a parallel-prefix operation on input array 'array'.
void	setMinimumArraySize(int size)

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_MINIMUM_ARRAY_SIZE

public static final int DEFAULT_MINIMUM_ARRAY_SIZE

minimum size. TODO find a better number than this guess.

See Also:

Constant Field Values

Constructor Detail

ThreadedParallelPrefix

public ThreadedParallelPrefix(int nthreads)

Parameters:

nthreads - Number of threads to use in parallelizing the scan operation.

ThreadedParallelPrefix

public ThreadedParallelPrefix()

Set number of worker threads to the number of availableProcessors.

Method Detail

setMinimumArraySize

public void setMinimumArraySize(int size)

Parameters:

size - minimum size of array for non-serial scan to be used.

getMinimumArraySize

public int getMinimumArraySize()

Returns:

minimum size of input array required for threaded (non-serial) scan to be employed.

scan

public void scan(int[] inputArray,
                 int[] outputArray,
                 BinaryOp<T> op)

Perform a parallel-prefix operation on input array 'array'. Input array is not modified. Result will be {a[0],op(a[0],a[1]),op(a[1],a[2]),...,op(a[n-1],a[n])}

Specified by:

scan in interface ParallelPrefix<T>

Overrides:

scan in class AbstractParallelPrefix<T>

Parameters:

inputArray - Single dimension input array

outputArray - Single dimension destination array. Can be the same as inputArray

op - binary operator

scan

public void scan(float[] inputArray,
                 float[] outputArray,
                 BinaryOp<T> op)

Perform a parallel-prefix operation on input array 'array'. Input array is not modified. Result will be {a[0],op(a[0],a[1]),op(a[1],a[2]),...,op(a[n-1],a[n])}

Specified by:

scan in interface ParallelPrefix<T>

Overrides:

scan in class AbstractParallelPrefix<T>

Parameters:

inputArray - Single dimension input array

outputArray - Single dimension destination array. Can be the same as inputArray

op - binary operator

scan

public void scan(double[] inputArray,
                 double[] outputArray,
                 BinaryOp<T> op)

Perform a parallel-prefix operation on input array 'array'. Input array is not modified. Result will be {a[0],op(a[0],a[1]),op(a[1],a[2]),...,op(a[n-1],a[n])}

Specified by:

scan in interface ParallelPrefix<T>

Overrides:

scan in class AbstractParallelPrefix<T>

Parameters:

inputArray - Single dimension input array

outputArray - Single dimension destination array. Can be the same as inputArray

op - binary operator

scan

public void scan(char[] inputArray,
                 char[] outputArray,
                 BinaryOp<T> op)

Perform a parallel-prefix operation on input array 'array'. Input array is not modified. Result will be {a[0],op(a[0],a[1]),op(a[1],a[2]),...,op(a[n-1],a[n])}

Specified by:

scan in interface ParallelPrefix<T>

Overrides:

scan in class AbstractParallelPrefix<T>

Parameters:

inputArray - Single dimension input array

outputArray - Single dimension destination array. Can be the same as inputArray

op - binary operator

scan

public void scan(byte[] inputArray,
                 byte[] outputArray,
                 BinaryOp<T> op)

Perform a parallel-prefix operation on input array 'array'. Input array is not modified. Result will be {a[0],op(a[0],a[1]),op(a[1],a[2]),...,op(a[n-1],a[n])}

Specified by:

scan in interface ParallelPrefix<T>

Overrides:

scan in class AbstractParallelPrefix<T>

Parameters:

inputArray - Single dimension input array

outputArray - Single dimension destination array. Can be the same as inputArray

op - binary operator

scan

public void scan(short[] inputArray,
                 short[] outputArray,
                 BinaryOp<T> op)

Perform a parallel-prefix operation on input array 'array'. Input array is not modified. Result will be {a[0],op(a[0],a[1]),op(a[1],a[2]),...,op(a[n-1],a[n])}

Specified by:

scan in interface ParallelPrefix<T>

Overrides:

scan in class AbstractParallelPrefix<T>

Parameters:

inputArray - Single dimension input array

outputArray - Single dimension destination array. Can be the same as inputArray

op - binary operator

scan

public void scan(long[] inputArray,
                 long[] outputArray,
                 BinaryOp<T> op)

Perform a parallel-prefix operation on input array 'array'. Input array is not modified. Result will be {a[0],op(a[0],a[1]),op(a[1],a[2]),...,op(a[n-1],a[n])}

Specified by:

scan in interface ParallelPrefix<T>

Overrides:

scan in class AbstractParallelPrefix<T>

Parameters:

inputArray - Single dimension input array

outputArray - Single dimension destination array. Can be the same as inputArray

op - binary operator

scan

public void scan(T[] inputArray,
                 T[] outputArray,
                 BinaryOp<T> op)

Perform a parallel-prefix operation on input array 'array'. Input array is not modified. Result will be {a[0],op(a[0],a[1]),op(a[1],a[2]),...,op(a[n-1],a[n])}

Specified by:

scan in interface ParallelPrefix<T>

Overrides:

scan in class AbstractParallelPrefix<T>

Parameters:

inputArray - Single dimension input array

outputArray - Single dimension destination array. Can be the same as inputArray

op - binary operator