AF: Small: Shared-Memory Parallel Algorithms: Theory and Practice

随着近年来多核处理器的出现，从50美元的业余工具包到数百万美元的超级计算机，共享内存并行算法具有越来越重要的实践和理论意义。该项目正在开发与当今共享内存并行机器相关的新算法方法和结果。这个项目的影响将体现在能够更好地利用现代多核架构的计算能力的应用程序上。该项目旨在开发许多这些算法的库实现，这些算法将向公众提供。在教育方面，该项目将产生课程作业，帮助本科生学习并行算法及其实现。该项目侧重于三个领域。首先是研究开发模型的结果，即二进制分叉模型，它比以前的一些模型更适用于今天的机器。特别是，该模型与大多数并行机器上可用的软件平台相匹配，并支持与它们运行的机器最相关的异步并行形式。第二个方面是更好地理解许多顺序算法中已经存在的并行性。我们的目标是推导出更简单、更高效的算法。第三个领域是开发允许用户有效地对底层数据结构进行批量更新的算法。这被称为批并行动态算法，它遵循了之前对顺序单更新动态更新的大量工作。在二进制分叉模型中，每个任务只能分叉成两个子任务，但可以递归地和异步地进行。目前，即使对于排序和图连接等一些基本问题，二进制分叉模型也没有严格的性能界限，而这正是本项目试图解决的问题。为了理解顺序算法中的并行性，本项目将研究迭代顺序算法中子计算之间的依赖关系。在并行批处理算法的推动下，该项目正在研究将这些思想应用于图连通性和相关问题。我们的目标是实现相对于最佳（或接近最佳）顺序算法而言工作效率更高的算法，特别是对于图连接而言，每次更新可以实现O（log^2 n）平算工作，同时允许批量更新。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

With the advent in recent years of multicore processors ranging from fifty dollar hobby kits to multi-million dollar supercomputers, shared-memory parallel algorithms have increasingly significant practical and theoretical relevance. This project is developing new algorithmic approaches and results relevant to today's shared-memory parallel machines. The impact of this project will be felt in applications being able to make better use of the computational power of modern multi-core architectures. The project seeks to develop library implementations of many of these algorithms which will be made available to the public. On the educational side, the project will result in coursework that will help undergraduate students learn about parallel algorithms and their implementation.The project focuses on three areas. The first is research on developing results in a model, the binary forking model, that is more relevant to today's machines than some previous models. In particular the model matches the software platforms that are available on most parallel machines, and supports an asynchronous form of parallelism that are most relevant to the machines they run on. The second area is to better understand the parallelism already available in many sequential algorithms. The goal is to derive algorithms that are simpler and more efficient. The third area is to develop algorithms that allow the user to efficiently make batches of updates to underlying data structures. This is referred to as batch parallel dynamic algorithms, and follows significant prior work on sequential single update dynamic updates. In the binary forking model each task can only fork into two child tasks, but can do so recursively and asynchronously. At present no tight performance bounds for the binary forking model are known even for some basic problems such as sorting and graph connectivity, which this project seeks to remedy. For the thrust on understanding parallelism in sequential algorithms, the project will study the dependencies among sub-computations in iterative sequential algorithms. In the thrust on parallel batched algorithms the project is looking at applying the ideas to graph connectivity and related problems. The goal is to achieve algorithms that are work-efficient relative to the best (or near best) sequential algorithms---and in particular for graph connectivity to achieve O(log^2 n) amortized work per update, while allowing batches of updates.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.