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.


Tree Scan

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 List Ranking

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.

Quicksort

This is a parallel version of Quicksort. It has expected work of O(n log n) and an expected depth of O(log n).

Counting Sort

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.

Selection Sort

This is a parallel version of selection sort. Like the sequential version it does O(n^2) work. Its depth is O(n).

Insertion Sort

This is a parallel version of insertion sort. Like the sequential version it does O(n^2) work. Its depth is O(n).

Batcher's Bitonic Sort

Here is Batcher's bitonic sort. It has total work O(n log^2 n) and depth O(log^2 n).

Batcher's Odd-Even Merge

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.

Halving Merge

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.

Quick Select

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.

Sample Select

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.

String Search


String Compare

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

Matching Parentheses

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.