权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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.

近年来，随着从50美元的业余爱好工具包到数百万美元的超级计算机的多核处理器的出现，共享内存并行算法具有越来越重要的实践和理论意义。该项目正在开发与当今共享内存并行机相关的新算法方法和结果。该项目的影响将在能够更好地利用现代多核架构的计算能力的应用程序中感受到。该项目寻求开发其中许多算法的库实现，并将向公众提供。在教育方面，该项目将产生课程作业，帮助本科生学习并行算法及其实现。该项目集中在三个领域。第一个是对一个模型的开发结果的研究，该模型比以前的一些模型更适合于今天的机器。特别是，该模型与大多数并行机上可用的软件平台相匹配，并支持与它们运行的机器最相关的异步形式的并行性。第二个领域是更好地理解许多顺序算法中已有的并行性。其目标是得出更简单、更有效的算法。第三个领域是开发允许用户高效地对底层数据结构进行批量更新的算法。这被称为批处理并行动态算法，并且遵循在顺序单次更新动态更新方面的大量先前工作。在二进制分叉模型中，每个任务只能分叉成两个子任务，但可以递归和异步地完成。目前还不知道二进制分叉模型的严格性能界限，甚至对于排序和图连接等一些基本问题也是已知的，本项目试图解决这些问题。为了理解顺序算法中的并行性，该项目将研究迭代顺序算法中的子计算之间的依赖关系。在并行批处理算法的推动下，该项目正着眼于将这些想法应用于图的连通性和相关问题。我们的目标是实现相对于最好(或接近最好)的顺序算法而言工作效率更高的算法-特别是对于图形连接性，以实现O(log^2n)次更新的分期工作，同时允许批量更新。该奖项反映了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.

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

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

Joinable Parallel Balanced Binary Trees

可连接的并行平衡二叉树

DOI：
10.1145/3512769
发表时间：
2022
期刊：
ACM Transactions on Parallel Computing
影响因子：
1.6
作者：
Blelloch, Guy;Ferizovic, Daniel;Sun, Yihan
通讯作者：
Sun, Yihan

Work-Efficient Batch-Incremental Minimum Spanning Trees with Applications to the Sliding-Window Model

DOI：
10.1145/3350755.3400241
发表时间：
2020-02
期刊：
Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
0
作者：
Daniel Anderson;G. Blelloch;Kanat Tangwongsan
通讯作者：
Daniel Anderson;G. Blelloch;Kanat Tangwongsan