并行算法序列和字符串:
·Scan (prefix sums)
·List ranking
·Sorting
·Merging
·Medians
·Searching
·String matching
·Other string operations
并行算法的树和图:
·Trees
·Connected components
·Spanning trees
·Shortest paths
·Maximal independent set
·Graph separators
计算几何的并行算法:
·Convex hull
·Closest pairs
·Delaunay triangulation
数值/科学计算的并行算法
·Fourier transform
·Dense matrix operations
·Sparse matrix operations
·N-body code
·Other
Scan
Scan操作(也称为all-prefix-sum)采用二元联合运算符作为标识函数和arry,并返回一个新数组,其中每个元素具有所有先前元素的总和(sum是相对于关联运算符定义的)。例如
scan(+, 0, [2, 8, 9, -4, 1, 3, -2, 7]);
是
[0, 2, 10, 19, 15, 16, 19, 17]
算法
·Tree Scan
List Ranking
List ranking需要一个链接列表,并返回列表中每个元素的位置。位置给出了距列表尾部的距离。使用整数数组表示列表,其中每个整数表示列表中下一个元素的索引。我们用自指针终止列表。 例如,数组
[2, 5, 1, 3, 7, 6, 6, 3]
代表以下两列:
0 -> 2 -> 1 -> 5 -> 6
4 -> 7 -> 3
算法:
·Wyllie
·Random Mate
·Sorting
有许多并行排序算法。这里给出了一些示例。
算法
·Quicksort
·Selection sort
·Insertion sort
·Counting sort
·Batcher’s Bitonic Sort
·Radix Sort
·String Radix Sort
Merging算法:
·Batcher’s Odd-Even Merge
·Halving Merge
Medians
这里考虑找到一个集合中第k个最小元素的问题。众所周知,这个问题可以在O(n)时间序列内解决。在这里考虑的两个算法都需要O(n)的工作,虽然第一个是预期的情况,第二个是高概率。
算法
·Quick Select
·Sample Select
Searching算法:
·Hash Tables
String Matching
字符串匹配问题需要一个TEXT字符串和一个PATTERN字符串,并查找模式在文本中出现的所有位置。
算法:
·Naive algorithm
·Vishkin algorithm
其他字符串
这里考虑字符串的各种操作,比如按字母顺序比较两个字符串,将一串字符分解成几行,然后再匹配括号。
算法
·String comparison
·breaking a string into lines
·Matching Parentheses
树算法:
·Generate Euler tour from edgelist
·Rootfix (e.g. for level numbering)
·Leaffix (e.g. for subtree sizes)
连接组件
连接组件问题采用无向图,并返回所有通过边连接的组件。对于一个有n个顶点和m条边的图,这个问题可以用O(n + m)时间顺序地使用深度优先搜索或宽度优先搜索来解决,并行算法是基于收缩图的思想。
算法
·Awerbuch Shiloach
·Random mate
·Hybrid
生成树
生成树算法与连接组件类似,但生成树算法需要跟踪哪些边用于收缩,而不需要将图扩展回去。
算法
·Hybrid based Spanning Tree
短路径算法:
·Breadth First Search
最大独立集算法:
·Luby’s Algorithm
图划分算法:
·Spectral
·Recursive bisection
·Teng/Vavasis/Miller
Convex Hull算法:
·Jarvis March
·Quickhull
·Kirkpatrick-Seidel
·Overmar’s Mergehull
·Atallah’s variant of Overmar’s Mergehull (O(lg n) time)
Closest Pairs算法:
·All closest pairs
Delaunay Triangulation算法:
·Projection based
·Closest pair based
Fourier Transform算法:
·Fast Fourier transform
Dense Matrix Operations算法:
·Matrix multiply
·Matrix inverse
·Linear system solve
·Null space of matrix
Sparse Matrix Operations算法:
·Matrix-vector multiply
·Jacobi
·Conjugate gradient
N-body Code算法:
·All pairs
·Barnes-Hut
·Greengard’s FMM
·PMTA (a hybrid)
其他数值编码算法:
·prime numbers
·adaptive integration
·line fitting
·order-m recurrences
·Tree based preconditioner