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

AF：小型：共享内存并行算法：理论与实践

基本信息

批准号：
1910030
负责人：
Guy Blelloch
金额：
$ 40万
依托单位：
Carnegie-Mellon University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-07-01 至 2022-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910030&HistoricalAwards=false
关键词：
AF Small Shared Memory Parallel

项目摘要

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.

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

项目成果

期刊论文数量（21）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Parallel Minimum Cuts in O ( m log 2 n ) Work and Low Depth

O ( m log 2 n ) 工作和低深度并行最小切削

DOI：
10.1145/3409964.3461797
发表时间：
2021
期刊：
Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
0
作者：
Anderson, Daniel;Blelloch, Guy E.
通讯作者：
Blelloch, Guy E.

Parallel Batch-Dynamic Trees via Change Propagation

通过变更传播的并行批动态树

DOI：
10.4230/lipics.esa.2020.2
发表时间：
2020
期刊：
European Symposium on Algorithms (ESA
影响因子：
0
作者：
Umut Acar, Daniel Anderson
通讯作者：
Umut Acar, Daniel Anderson

Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable

DOI：
10.1145/3210377.3210414
发表时间：
2018-05
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
0
作者：
Laxman Dhulipala;G. Blelloch;Julian Shun
通讯作者：
Laxman Dhulipala;G. Blelloch;Julian Shun

Parallelism in Randomized Incremental Algorithms