Task framework demo programs

The programs in this directory include ones that I've used to test and experiment with the task framework. You may also find them useful as demonstrations of various constructions and techniques that can be used with Tasks. However, most of these programs are not themselves particularly useful, and have not been constructed or documented with any concern for reuse or extensibility. They are not properly packaged (i.e., they do not declare to be in any package). They can be compiled via: javac *.java

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]
where #threads is the number of threads to establish in a TaskGroupRunner that runs the tasks. All of the programs print out ThreadGroup.stats(), normally at the ends of their runs. Some of the programs do not bother printing out any further results. Some programs, at some parameter settings deal with huge arrays and matrices that require a lot of memory, so you might need to use -Xmx switches; for example -Xmx64m to use a maximum of 64Mbytes of memory.


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.

Doug Lea
Last modified: Tue Jan 18 07:12:03 EST 2000