Collaborative Research: AF: Small: Efficient Massively Parallel Algorithms

合作研究：AF：小型：高效大规模并行算法

基本信息

批准号：
2218678
负责人：
Mohammad Hajiaghayi
金额：
$ 29.82万
依托单位：
University of Maryland, College Park
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-06-15 至 2025-05-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2218678&HistoricalAwards=false
关键词：
Collaborative Research AF Small Efficient

项目摘要

Modern computing systems have moved beyond single-coresingle-processor devices to more modern multicore processors operatingin networked systems and available in warehouse-scale cloudspopularized by companies such as Amazon or Google. Future advances incomputing power will likely come not mainly from faster devices, butby processing in inherently parallel and distributed environments, andby understanding how to exploit the parallelism inherent in manyalgorithmic problems. Simultaneously, the world has entered the era of``big data'' with large data sets on which previously unthinkablesized problems with great economic and social impact need to besolved. This new parallel, interconnected, big-data world speciallyrequires fundamental research on their algorithms, which are bothparallel and distributed.The algorithms in this project address thisimportant research challenge by building and developing new generalframeworks for massively parallel computation.As the main thrust of this project, the investigators will designfundamental and efficient algorithms for core massively parallelcomputations especially in the practical Massively ParallelComputation (MPC) framework. In particular, they will consider methodsfor reducing the number of rounds in the MPC model as well astradeoffs between rounds, memory, number of machines, andcommunication time. They seek to find new MPC algorithms for basicgraph problems such as connectivity, matching, vertex cover, maximalindependent set, as well as other basic string matching problems suchas suffix trees, edit distance, and longest commonsubsequence. Another focus is dynamic algorithms for massivelyparallel computation, which modify the output efficiently in aparallel/distributed setting based on frequent modifications of theinput and with direct applications in evolving social networks, theWorld Wide Web, road networks, scheduling systems among others. Theinvestigators will augmenting current parallelenvironments/architectures with better data structures andabstractions to allow simplified and fast implementations of thecurrent fundamental algorithms that can be used in practicevia open-source codes. The discoveries in this project will beintegrated into existing and new courses and books about parallelalgorithms, distributed algorithms, and foundations of big data. Thewealth of attractive open problems in these areas will provide bothchallenging research topics and intuitive accessible problems toinspire students to enter research in computer science andmathematics. In particular the project will involve Ph.D. students andpost-docs, undergraduate students, and even high-school students(especially students among minorities and women), many of whom willcontinue their research at other academic institutions and researchcenters, further broadening the impact of this research.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.

现代计算系统已经从单核单处理器设备发展到在网络系统中运行的更现代的多核处理器，并可在亚马逊或谷歌等公司普及的仓库规模云中使用。未来计算能力的进步可能主要不是来自更快的设备，而是通过在固有的并行和分布式环境中进行处理，以及了解如何利用许多算法问题中固有的并行性。与此同时，世界已经进入“大数据”时代，拥有大量数据，需要解决以前难以想象的、具有巨大经济和社会影响的问题。这个新的并行、互连、大数据世界特别需要对其并行和分布式算法进行基础研究。该项目中的算法通过构建和开发用于大规模并行计算的新通用框架来解决这一重要的研究挑战。作为该项目的主旨，研究人员将为核心大规模并行计算设计基本且高效的算法，特别是在实用的大规模并行计算（MPC）框架中。特别是，他们将考虑减少 MPC 模型中轮数的方法以及轮数、内存、机器数量和通信时间之间的权衡。他们寻求寻找新的 MPC 算法来解决基本图问题，例如连通性、匹配、顶点覆盖、最大独立集，以及其他基本字符串匹配问题，例如后缀树、编辑距离和最长公共子序列。另一个焦点是大规模并行计算的动态算法，它根据输入的频繁修改在并行/分布式设置中有效地修改输出，并直接应用于不断发展的社交网络、万维网、道路网络、调度系统等。研究人员将通过更好的数据结构和抽象来增强当前的并行环境/架构，以允许简化和快速地实现可通过开源代码在实践中使用的当前基本算法。该项目的发现将被整合到有关并行算法、分布式算法和大数据基础的现有和新课程和书籍中。这些领域中大量有吸引力的开放问题将提供具有挑战性的研究主题和直观易懂的问题，以激励学生进入计算机科学和数学研究。特别是该项目将涉及博士。学生和博士后、本科生，甚至高中生（特别是少数族裔和女性学生），其中许多人将在其他学术机构和研究中心继续他们的研究，进一步扩大这项研究的影响。该奖项反映了 NSF 的法定使命通过使用基金会的智力优点和更广泛的影响审查标准进行评估，并被认为值得支持。

项目成果

期刊论文数量（6）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

在真正的次二次时间中近似编辑距离：Quantum 和 MapReduce

DOI：
10.1145/3456807
发表时间：
2021-05
期刊：
Journal of the ACM
影响因子：
2.5
作者：
Boroujeni, Mahdi;Ehsani, Soheil;Ghodsi, Mohammad;Hajiaghayi, Mohammadtaghi;Seddighin, Saeed
通讯作者：
Seddighin, Saeed

Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance

有界树编辑距离的 (n poly(k)) 时间算法

DOI：
10.1109/focs54457.2022.00071
发表时间：
2022-10
期刊：
FOCS
影响因子：
0
作者：
Das, Debarati;Gilbert, Jacob;Hajiaghayi, MohammadTaghi;Kociumaka, Tomasz;Saha, Barna;Saleh, Hamed
通讯作者：
Saleh, Hamed

Improved communication complexity of fault-tolerant consensus

提高容错共识的通信复杂度

DOI：
10.1145/3519935.3520078
发表时间：
2022-06
期刊：
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
0
作者：
Hajiaghayi, Mohammad T.;Kowalski, Dariusz R.;Olkowski, Jan
通讯作者：
Olkowski, Jan

Adaptive Massively Parallel Algorithms for Cut Problems

用于解决问题的自适应大规模并行算法