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 的法定使命通过使用基金会的智力优点和更广泛的影响审查标准进行评估，并被认为值得支持。