CAREER: Parallel Algorithms and Frameworks for Graph and Hypergraph Processing

职业：图和超图处理的并行算法和框架

基本信息

批准号：
1845763
负责人：
Julian Shun
金额：
$ 59.76万
依托单位：
Massachusetts Institute of Technology
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-03-01 至 2025-02-28
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1845763&HistoricalAwards=false
关键词：
CAREER Parallel Algorithms Frameworks Graph

项目摘要

Graphs are a tool used to model the interactions between various entities. Efficiently processing large graphs has attracted significant attention due to its applications in various domains, such as biology, chemistry, and social network analysis. With the explosion in the volume of data, graphs have become very large and can contain hundreds of billions of vertices and trillions of edges. Various applications also benefit from modeling the underlying data as a hypergraph, which enables relationships among multiple entities to be represented better than a graph. In addition, many of these data sets are changing rapidly in real-time and applications require computing results on the latest data. It is crucial to design high-performance parallel algorithms to enable analysis to be done on graphs and hypergraphs in a timely fashion. However, writing efficient parallel code is notoriously difficult. Furthermore, many parallel algorithms used in practice today do not have strong theoretical guarantees, causing them to perform extremely poorly on certain inputs. To address these challenges, this project involves creating high-level programming frameworks with highly-optimized backends to make it easier for non-experts to write high-performance parallel programs for graphs and hypergraphs dealing with static and streaming data. This project also involves designing parallel algorithms that are efficient both in theory and in practice, so that they can perform well under all possible inputs and across many machine parameters, and scale gracefully to larger data sets. Using the resulting algorithms and frameworks, scientists will be able to use high-level tools to perform graph and hypergraph analytics on massive inputs much more efficiently than before, both in theory and in practice.This project involves designing new parallel primitives and algorithms for many fundamental graph and hypergraph problems that are fast and memory-efficient, both in theory and in practice. The new algorithms are being evaluated on the largest publicly-available data sets using large-scale multicore machines. The project also involves creating high-level abstractions and programming frameworks to support the implementation of theoretically-efficient algorithms on both static and streaming data. First, a domain specific language for graph computations that generates efficient and highly-optimized code from high-level specifications of algorithms and optimizations will be designed. Second, a unified framework for streaming graph analytics that can efficiently support parallel updates to the graph (simultaneously running algorithms and updates), incremental algorithms, and temporal analysis will be developed. Finally, a novel abstraction and framework for hypergraph processing that will support theoretically-efficient implementations of hypergraph algorithms will be designed. The results will lead to fundamental advances in parallel algorithm design and programming frameworks for graph and hypergraph analytics.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.

图是用于对各种实体之间的交互进行建模的工具。高效处理大图由于其在生物学、化学和社交网络分析等各个领域的应用而引起了极大的关注。随着数据量的爆炸式增长，图变得非常大，可以包含数千亿个顶点和数万亿个边。各种应用程序还受益于将底层数据建模为超图，这使得多个实体之间的关系能够比图更好地表示。此外，许多数据集实时快速变化，应用程序需要最新数据的计算结果。设计高性能并行算法以便及时对图和超图进行分析至关重要。然而，编写高效的并行代码是出了名的困难。此外，当今实践中使用的许多并行算法没有强有力的理论保证，导致它们在某些输入上表现极差。为了应对这些挑战，该项目涉及创建具有高度优化后端的高级编程框架，以使非专家更容易为处理静态和流数据的图和超图编写高性能并行程序。该项目还涉及设计在理论和实践中都高效的并行算法，以便它们可以在所有可能的输入和跨许多机器参数下表现良好，并优雅地扩展到更大的数据集。使用由此产生的算法和框架，科学家将能够使用高级工具在理论和实践上比以前更有效地对大量输入执行图形和超图分析。该项目涉及为许多数据设计新的并行原语和算法在理论和实践中都快速且内存高效的基本图和超图问题。新算法正在使用大型多核机器在最大的公开数据集上进行评估。该项目还涉及创建高级抽象和编程框架，以支持在静态和流数据上实现理论上高效的算法。首先，将设计一种用于图计算的领域特定语言，该语言根据算法和优化的高级规范生成高效且高度优化的代码。其次，将开发一个统一的流图分析框架，可以有效地支持图的并行更新（同时运行算法和更新）、增量算法和时间分析。最后，将设计一种新颖的超图处理抽象和框架，该框架将支持超图算法理论上高效的实现。研究结果将带来图和超图分析的并行算法设计和编程框架的根本性进步。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

期刊论文数量（37）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Theoretically efficient parallel graph algorithms can be fast and scalable

理论上高效的并行图算法可以快速且可扩展

DOI：
10.1145/3210377.3210414
发表时间：
2021-04
期刊：
ACM transactions on parallel computing
影响因子：
0
作者：
Dhulipala, Laxman;Blelloch, Guy;Shun, Julian
通讯作者：
Shun, Julian

Parallel Filtered Graphs for Hierarchical Clustering

用于层次聚类的并行过滤图

DOI：
10.1109/icde55515.2023.00153
发表时间：
2023-03-09
期刊：
2023 IEEE 39th International Conference on Data Engineering (ICDE)
影响因子：
0
作者：
Shangdi Yu;Julian Shun
通讯作者：
Julian Shun

Optimizing Ordered Graph Algorithms with GraphIt

使用 GraphIt 优化有序图算法

DOI：
发表时间：
2020-02
期刊：
International Symposium on Code Generation and Optimization
影响因子：
0
作者：
Zhang, Yunming;Brahmakshatriya, Ajay;Chen, Xinyi;Dhulipala, Laxman;Kamil, Shoaib;Amarasinghe, Saman;Shun, Julian
通讯作者：
Shun, Julian

Parallel Algorithms for Butterfly Computations

蝴蝶计算的并行算法