CAREER: Parallel Algorithms: Theory for Practice

职业：并行算法：理论实践

• 批准号: 2238358
• 负责人: Yihan Sun
• 金额: $ 54.66万
• 依托单位: University of California-Riverside
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-03-01 至 2028-02-29
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2238358&HistoricalAwards=false
• 关键词: CAREER; Parallel; Algorithms; Theory; Practice

Recent hardware advances have brought multicore parallel machines to the mainstream. Parallelism offers the promise of high performance, and theoretical research is important in supporting high performance. However, there remains a significant gap between the theory and practice of multicore parallelism. First, many simple problems in the traditional (sequential) setting become more complicated in parallel and still remain open in theory. This creates difficulty in teaching and popularizing parallel algorithms to a broader audience. Second, some important practical ideas are not captured by existing theory, and researchers need to consider theory and practice separately. As a result, it is important to develop new theoretical results for parallel algorithms that are simple to understand and can better capture practice. The goal of this project is to study the theory of shared-memory parallelism, including designing new parallel algorithms with improved theoretical guarantees, studying new parallel models to better capture practice, as well as promoting accessibility (to a broad audience and in education) and practicality (with good performance) for parallel algorithms.This project focuses on two thrusts. The first thrust is to design simple and efficient parallel algorithms from sequential iterative algorithms by carefully analyzing the true dependencies between iterations. A broader goal is to find conditions that make a sequential algorithm highly parallelizable and methodologies for exploiting parallelism. The second thrust is to design new models and algorithms to reduce synchronization costs. Although viewed as a constant cost in most existing parallel models, synchronizing threads is expensive in practice, and more accurate modeling is needed. This project will study new models to systematically understand the synchronization costs in parallel algorithms. This project places a strong emphasis on combining theory and practice. In addition to new theoretical bounds, the research team will also evaluate the practicality of the results for simplicity (are they suitable in the classroom setting) and programmability/performance (can they be implemented to achieve high performance).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的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

项目成果

Efficient Parallel Output-Sensitive Edit Distance

• DOI: 10.4230/lipics.esa.2023.40
• 发表时间: 2023-06
• 作者: Xiangyun Ding;Xiaojun Dong;Yan Gu;Youzhe Liu;Yihan Sun

Provably Fast and Space-Efficient Parallel Biconnectivity

经证明快速且节省空间的并行双连接

• DOI: 10.1145/3572848.3577483
• 发表时间: 2023
• 期刊: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
• 作者: Dong, Xiaojun;Wang, Letong;Gu, Yan;Sun, Yihan
• 通讯作者: Sun, Yihan

High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems

半排序及相关问题的高性能灵活并行算法

• DOI: 10.1145/3558481.3591071
• 发表时间: 2023
• 期刊: ACM
• 作者: Dong, Xiaojun;Wu, Yunshu;Wang, Zhongqi;Dhulipala, Laxman;Gu, Yan;Sun, Yihan
• 通讯作者: Sun, Yihan

Parallel Strong Connectivity Based on Faster Reachability

• DOI: 10.1145/3589259
• 发表时间: 2023-03
• 期刊: Proceedings of the ACM on Management of Data
• 作者: Letong Wang;Xiaojun Dong;Yan Gu;Yihan Sun

Parallel Longest Increasing Subsequence and van Emde Boas Trees

并行最长递增子序列和 van Emde Boas 树

• DOI: 10.1145/3558481.3591069
• 发表时间: 2023
• 期刊: ACM
• 作者: Gu, Yan;Men, Ziyang;Shen, Zheqi;Sun, Yihan;Wan, Zijin
• 通讯作者: Wan, Zijin