Separators in Two or More Dimensions and Parallel Algorithm Design

这个研究项目的目标是了解如何快速设计 和处理器高效算法，重点是 是针对细粒度并行架构。 的方法 将主要解决图论问题， 更具体问题的解决方案，如找到近似 偏微分方程的有限元解法 法 几乎所有这些工作都假设下划线图形 拥有一些进一步的几何或拓扑结构，希望 寻找快速和处理器效率高的算法的问题， 否则似乎很难有效地并行化。 将开发处理器高效算法来构建 在稀疏线性系统中出现的图分离器。 这些 分离器将被用于建设更有效的 直接和迭代的方法来解决这些系统。 的 使用几何约束获得的图形之间的关系， 将研究使用拓扑约束获得的那些。 大部分研究将集中在处理器的设计上- 有效的并行算法的抽象机器，拥有一个 消息传递体系结构，如并行随机访问 机 已经开发的许多并行算法是 高效和简单，当机器可用时， 有效地执行消息传递，应该有大量的 加速。 下一代或两代并行机将 能够处理大量的交通产生的 指针算法 算法将被设计用于 一种增加单位代价的并行随机存取机模型 前缀和或扫描等操作。 增广算法 模型应该更简单，从而有更好的效率 在较新的机器上实现。

The goal of this research project is to understand how to design fast and processor-efficient algorithms with an emphasis on algorithms that are targeted toward fine-grain parallel architectures. The approach will be to solve mostly graph theoretic problems that arise from the solution to more concrete problems such as finding approximate solutions to partial differential equations using the finite element method. Almost all of this work assumes that the underlining graphs possess some further geometric or topologic structure, with the hope of finding fast and processor-efficient algorithms for problems which otherwise seem hard to parallelize efficiently. Processor-efficient algorithms will be developed for constructing graph separators which arise in sparse linear systems. These separators will then be used in the construction of more efficient direct and iterative methods for solving these systems. The relationship between graphs obtained using geometric constraints and those obtained using topological constraints will be studied. The bulk of the research will be in the design of processor- efficient parallel algorithms for abstract machines that possess a message passing architecture, such as the Parallel Random Access Machine. Many of the parallel algorithms that have been developed are efficient and simple enough that, when machines are available that can efficiently perform message passing, there should be substantial speedups. The next one or two generations of parallel machines will be able to handle the large amount of traffic generated by the pointer-based algorithms. Algorithms will be designed for the Parallel Random Access Machine model augmented with unit cost operations such as prefix-sum or scan. Algorithms for the augmented model should be simpler, and thus have a better chance of efficient implementation on the newer machines.