Go to the first, previous, next, last section, table of contents.

The Parallel NoFib Suite

. .

While developing GranSim (and GUM) we have started to collect a set of interesting and non-trivial parallel programs written in parallel Haskell. These programs are used as a test suite for GranSim and part of the NoFib Suite of GHC.

Currently this suite contains the following programs:

  1. Sieve of Erathostenes (sieve), which creates a bidirectional pipeline, where each processor filters the multiples of one prime number out of an input list.
  2. Warshall's shortest path algorithm in a graph (warshall), which creates a cyclic pipeline of processors.
  3. A function matmult, which performs a parallel matrix multiplication.
  4. A function determinant, which computes for a given square matrix its determinant.
  5. A function LinSolv, which solves a given set of linear equations over integers by using multiple homomorphic images, computing the result in each image via Cramer's Rule. The main part of this algorithm is the parallel determinant computation.
  6. A function coins, which computes the number of possibilities how to pay a given value with a given set of coins.
  7. An award assignment program, that basically has to compute permutations of a given list (pperms).
  8. A parallel verion of Quicksort (sort).
  9. A function word search program soda7, which searches a given grid of letters for a given set of words.
  10. An RSA encryption program rsa (taken out of the sequential nofib suite).
  11. An n-queens program queens.
  12. The parallel database manager for GUM dcbm. It performs queries to a database in parallel.
  13. The bill of materials program bom developed (under GranSim) by Phil Trinder as part of the Parallel Databases Project.
  14. A ray-tracer nray based on a version taken from Kelly's thesis and ported to GRIP by Hammond.
  15. A univariant resultant computation, using the SACLIB library for computer algebra. Mainly the basic polynomial arithmetic has been taken form that library.
  16. One of the FLARE programs, solving a problem in the area of computational fluid dynamics cfd.
  17. A function minimax, which computes for a given position in the game of tic-tac-toe the best next move using an Alpha-Beta pruning algorithm.
  18. Several NESL programs, including a numerical integration algorithm integrate, a quick hull algorithm qhull for computing the convex hull of a set of points in a plane, a matrix inversion based on gauss-jordan elimination mi and a fast fourier transformation fft. All algorithms are based on the NESL versions published by Guy Blelloch in CACM 39(3) and translated to Haskell.
  19. A Newton-Raphson iteration for finding a root of a polynomial. This program has been taken from the Impala suite of implicitly parallel benchmark programs (written in Id).

Despite its name the parallel nofib suite also contains some fib-ish programs. These programs should be of interest for getting a start with parallel functional programming using GranSim:

  1. A parallel factorial function (parfact), which computes the sum of all numbers from 1 up to a given value n by bisecting the interval and computing results of the intervals in parallel.
  2. A parallel fib-like function (parfib), which performs an additional gcd computation and 2 additional multiplications in each recursive call.

Go to the first, previous, next, last section, table of contents.