【IT168 资讯】并行算法采用并行编程语言NESL实现，该语言是卡内基梅隆大学Scandal项目中开发的一种编程语言。对于每个算法，团队给出了一个简短的描述以及复杂性评估(就工作和深度而言)。
在很多情况下，NESL代码已经设置完毕，可以使用FORMs基本接口来运行算法。随意更改数据或算法，并提交修改后的版本。请注意，一些算法已经规定了对输入的限制(例如必须是均匀的)。
注意：本文涉及的一些功能描述和文档非常简洁，但都是可以正常工作的。(原文地址：https://www.cs.cmu.edu/~scandal/nesl/algorithms.html#scan，所有代码示例均可点击进入原文查看)
并行算法序列和字符串：
·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
