PeopleA 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 length).

We also have a collection of parallel algorithm 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


Scan

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 example
  scan(+, 0, [2, 8, 9, -4, 1, 3, -2, 7]);
is
  [0, 2, 10, 19, 15, 16, 19, 17]

The algorithms


List Ranking

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, the array
  [2, 5, 1, 3, 7, 6, 6, 3]
represents the two lists
  0 -> 2 -> 1 -> 5 -> 6
  4 -> 7 -> 3

The algorithms


Sorting

There are many parallel sorting algorithms. Here we give a sampling of some of them.

The algorithms


Merging

The algorithms


Medians

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 algorithms


Searching

The algorithms


String Matching

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.

The algorithms


Other String Operations

Here we consider various operations on strings, such as lexicographically comparing two strings, breaking a string of characters into lines, and matching parentheses.

The algorithms


Trees

The algorithms


Connected Components

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.

The algorithms


Spanning Trees

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.

The algorithms


Shortest paths

The algorithms


Maximal Independent Set

The algorithms


Graph separators

The algorithms


Convex Hull

The algorithms


Closest Pairs

The algorithms


Delaunay Triangulation

The algorithms


Fourier Transform

The algorithms


Dense Matrix Operations

The algorithms


Sparse Matrix Operations

The algorithms


N-body Code

The algorithms


Other Numerical Code

The algorithms