CAREER: Parallel Algorithms: Theory for Practice

最近的硬件进步使多核并行机成为主流。电子学提供了高性能的承诺，理论研究在支持高性能方面很重要。然而，多核并行的理论和实践之间仍然存在着巨大的差距。首先，传统（顺序）设置中的许多简单问题在并行时变得更加复杂，并且在理论上仍然是开放的。这给并行算法的教学和推广带来了困难。第二，一些重要的实际想法没有被现有的理论所捕获，研究人员需要将理论和实践分开考虑。因此，重要的是开发新的理论结果的并行算法，是简单的理解，可以更好地捕捉实践。本项目的目标是研究共享内存并行理论，包括设计新的并行算法，改进理论保证，研究新的并行模型，以更好地捕捉实践，以及促进并行算法的可访问性（广泛的受众和教育）和实用性（具有良好的性能）。第一个推力是设计简单而有效的并行算法从顺序迭代算法通过仔细分析迭代之间的真实依赖关系。一个更广泛的目标是找到使顺序算法高度并行化的条件和利用并行性的方法。第二个目标是设计新的模型和算法来降低同步成本。虽然在大多数现有的并行模型中被视为恒定成本，但实际上同步线程的成本很高，需要更精确的建模。本项目将研究新的模型，以系统地了解并行算法中的同步成本。这个项目非常注重理论与实践的结合。除了新的理论界限外，研究团队还将评估结果的实用性，以确保其简单性（是否适合课堂环境）和可编程性/性能（是否可以实现高性能）。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

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.