Library of Parallel Algorithms
This is the toplevel page for accessing code for a collection of
parallel algorithms. The algorithms are implemented in the parallel
programming language NESL and developed by
the Scandal project. For each algorithm we
give a brief description along with its complexity (in terms of
asymptotic work and parallel depth).
In many cases the NESL code is set up so you can run the algorithm
using our FORMs bases interface. Feel free to change the data or the
algorithms and submit the modified versions. Note that some of the
algorithms have stated restrictions on the input (e.g. must be of even
We also have a collection of
animations for some of the algorithms described off of this page.
These animations require that you use X11.
Note: We are currently working on this page. At
present some of the descriptions and documentation on the functions is
quite terse. We believe they all work, however, so if you find one
that does not, please report it.
Parallel algorithms on sequences and strings
Parallel algorithms on trees and graphs
Parallel algorithms for Computational Geometry
Parallel algorithms for Numerical/Scientific Computing
The scan operation, also called all-prefix-sums takes a binary
associative operator an identity function and an arry and returns a
new array with in which each element has the sum of all previous
elements (sum is defined relative to the associative operator). For
scan(+, 0, [2, 8, 9, -4, 1, 3, -2, 7]);
[0, 2, 10, 19, 15, 16, 19, 17]
List ranking takes a linked list and returns for each element in the list
its position in the list. The positions give the distance from the tail
of the list. We represent lists using arrays of integers in which each
integer represents the index of the next element in the list.
We terminate lists with a self pointer. For example,
[2, 5, 1, 3, 7, 6, 6, 3]
represents the two lists
0 -> 2 -> 1 -> 5 -> 6
4 -> 7 -> 3
There are many parallel sorting algorithms. Here we give a sampling
of some of them.
Here we consider the more general problem of finding the kth smallest
element in a set. It is well know that this problem can be solved in
O(n) time sequentially. Here we consider two algorithms
that both require O(n) work, although for the first this
is expected case and for the second it is with high probability.
The string matching problem takes a TEXT string and a PATTERN string
and finds all the positions in which the pattern appears in the text.
Here we consider various operations on strings, such as
lexicographically comparing two strings, breaking a string of
characters into lines, and matching parentheses.
The connected-components problem takes an undirected graph and returns
all the components that are connected by an edge. For a graph with
n vertices and m edges, this problem can be
solved in O(n+m) time sequentially using either
depth-first-search or breadth-first-search. The parallel algorithms
are based on the idea of contracting the graph.
Spanning-tree algorithms are similar to those for
connected-components, except that spanning-tree algorithms need to
keep track of which edges are used for contraction and they do not
need to expand the graph back out.