Parallel algorithms on sequences and strings
This page contains a collection of parallel algorithm on sequences and
strings. It includes a brief description of each algorithm along with
the NESL code. These algorithms have been
developed by the Scandal project.
If you have arrived here via a search engine, we suggest going to the
toplevel algorithms page.
The algorithm we use is a standard tree-based algorithm that requires
a total of O(n) work and O(log n) depth. The
code shown here works if the length of the array is a power of 2.
Wyllie's algorithm for list ranking is based on a technique called
pointer jumping. It requires O(n log n) work and O(log
n) depth.
This is a parallel version of Quicksort. It has expected work
of O(n log n) and an expected depth of O(log n).
This is a simple O(n^2) work and constant depth algorithm
that sorts by counting how many keys are less than every key. To
account for duplicate keys we need to tag each value with its index
and then make pairwise comparisons.
This is a parallel version of selection sort. Like the sequential
version it does O(n^2) work. Its depth is O(n).
This is a parallel version of insertion sort. Like the sequential
version it does O(n^2) work. Its depth is O(n).
Here is Batcher's bitonic sort. It has total work O(n log^2 n)
and depth O(log^2 n).
Here is Batcher's odd-even merge. It has total work O(n
log n) and depth O(log n). It is therefore
not work efficient.
As written it only works if both lists are equal lengths and are powers of 2.
This is an O(n) work and O(log n) depth merging algorithm.
As written it only works if both lists are equal lengths and are powers of 2.
The parallel quickselect algorithm is based on the sequential version.
Like quicksort it picks a pivot and then finds the keys less and greater
than the pivot. Unlike quicksort, it only has to recurse on one of these
two sets rather than both since it can determine in which of the sets the
kth element belongs. Because of this is has expected work O(n)
instead of O(n log n) for quicksort. Like quicksort, its
depth is O(log n), expected.
This is a select algorithm that has O(n) work
and constant depth with high probability. The idea is to take a sample
of the data of size sqrt(n) and then do an n^2 algorithm to find a
range in that sample (kmin,kmax) in which the kth element is likely
to appear. This technique quickly restricts the range in which
the algorithm has to consider.
This algorithm for comparing two string a and b returns -1 if a < b,
returns 0 if a = b and returns 1 if a > b. It uses a reduce (which is
implemented on a tree) to combine the values from each character. The
work of the algorith is O(#s1 + #s2) and the depth is
O(log(min(#s1,#s2))).
This is an interesting algorithm since one might think that matching
parentheses seems very sequential. For each location the algorithm
returns the index of the matching parenthesis. The algorithm is based
on a scan and an interger sort (rank). The scan returns the depth of
each parenthesis and the sort groups them into groups of equal depth.
At this point we can simply switch the indices of neighbors.
Assuming a work-efficient radix sort, this algorithm does O(n)
work and has the depth is bounded by the sort.