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.