Task framework demo programs

These programs are intended to show interesting variations in techniques, and do not necessarily demonstrate optimal performance. But some of the programs have been adapted from other common demo and benchmark programs used in parallel processing packages. To make comparisons with them fairer, I've usually tried to keep faithful to original quirks. (In fact a few were constructed by taking original C code and mangling it until javac declared that it was legal java code :-)

All of the programs are run by:

java Prog #threads [any other arguments]
  

Contents

Fib #threads number [sequential-threshold]

A fibonacci program similar to the one listed in the documentation for the Task class. Invoke with an number to compute the fibonacci number for. For example java Fib 2 35 computes the 35th fibonacci number with two threads. The optional sequential threshold value controls the argument size under which it uses a sequential version of fib (default is 0, meaning it never does). See also FibVCB, a callback-based version with same usage parameters.

MatrixMultiply #threads matrix-size granularity

A parallel divide-and-conquer matrix multiplication. The matrix size must be a power of two. The granularity controls the matrix size under which it stops recursively generating parallel tasks and performs a sequential multiply. It must also be a power of two and be at least 2. Default if not given is 16.

Jacobi #threads matrix-size max-iterations granularity

Performs Jacobi iteration of a mesh of matrix-size for either max-iterations or until converged. For demonstration, it is just applied to a square matrix of side matrix-size with all zeroes in the interior and all ones along edges. Default granularity if not given is 256 cells. See also BarrierJacobi, a different implementation using cyclic barriers (but not Tasks). It takes the same parameters except there is no first #threads argument.

Heat #threads 0-4

A standard parallel processing benchmark program that simulates heat diffusion across a mesh. The argument between 0 and 4 just selects among sets of parameter settings that you can find more about by reading the code.

LU #threads matrix-size #runs

LU matrix decomposition of randomly filled matrix. The matrix size must be a power of two, and at least 16. A granularity constant of 16 is built-in as a compile-time final constant. The optional #runs parameter optionally repeats the compuation on a new matrix.

Integrate #threads low high e

Computes integrals using recursive Gaussian Quadrature. A sample function to integrate (the sum of (2*i-1)*power(x, (2*i-1))) for odd values of i up through e) is pre-loaded. Call with lower and upper bounds. The e value is a parameter of the function. Higher values cause the function to both be slower to compute and take more iterations (subdivisions) for its integral to converge. If not given, it defaults to 5. For example, one reasonable set of test parameters is: java Integrate 4 1 48 5.

MSort #threads input-size

Performs a parallel merge/quick sort of input-size random integers.

Microscope #threads

An adaptation of the Microscope game. It uses tasks in a parallel exhaustive best-move finder with an adjustable look-ahead level. (Warning: because of the large fan-out of moves in this game, levels greater than 4 are still very slow.) By default, it is in Demo mode, where it just plays against itself until one side wins. If a second argument is given, it is interpreted as the level to play at, upon which it starts automatically and exits automatically when the game is over.

NQueens #threads board-size

Finds a placement of N queens that do not attack each other for a given NxN board size (where the board size must be at least 4). Since there are multiple solutions, the outcome is nondeterminstic when more than one thread is used. Results and timings may vary across runs.

BufferTasks #threads

A demo showing that you can, but probably shouldn't, use Tasks for classic producer-consumer programs. It sets up varying number of producer and consumer tasks, each operating on selected buffer sizes. If any producer cannot put, or consumer cannot take, it creates a whole new task to take over where it left off, starts it, and terminates. While this process cannot infinitely livelock, it can come pretty close.