CAREER: Efficient Algorithms for Modern Computer Architecture

最近的计算机硬件进步已经使并行处理器成为主流，并提供了更高的计算效率和生产力的潜力。 为了享受现代多核机器的好处，算法必须适合内存中的数据和辅助空间。在现代硬件上，在算法中使用太多空间限制了多核机器上可解决的问题大小，并可能在实践中降低性能。因此，设计高效的算法现在面临着与几十年前截然不同的挑战。 这个CAREER项目关注并行算法设计和分析中的两个关键挑战：空间效率和通信效率。该项目将提供有效的计算模型，以更好地满足多目标优化公式、新的图形算法和具有改进的理论保证的数据结构，以及新的数据结构和算法的开源软件。 该项目旨在弥合理论与实践之间的差距，这对于促进并行处理各种问题至关重要。 教育计划包括重新设计算法课程，以纳入内存存储考虑因素，以及支持编码俱乐部和编码竞赛，旨在使计算机科学更容易获得，特别是对当地代表性不足的学生群体。该项目有两个主要目标。第一个推力是研究空间有效的并行算法。本项目将首先研究一个简单而有效的计算模型，用于测量并行算法的空间使用情况，目的是研究空间有效的并行图算法和数据结构，使用辅助空间次线性输入大小。第二个推力是研究新的内存处理（PIM）系统的算法设计，这是最近开发的，以减少CPU和内存之间的昂贵的数据传输的需要。 这里的算法挑战在于PIM系统是共享存储器和分布式存储器的组合，因此PIM上的有效算法必须利用每种存储器的优点。这个项目将研究算法和数据结构，是有效的PIM架构。该项目的预期成果将是具有强有力的理论保证和良好的实际性能的算法，以及在现代计算机架构上设计和性能工程有效算法的一般经验。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Recent computer hardware advances have brought parallel processors to the mainstream and provided the potential for higher efficiency and productivity in computing. To enjoy the benefit of modern multicore machines, an algorithm must fit the data and auxiliary space in memory. On modern hardware, using too much space in an algorithm limits the solvable problem size on a multicore machine and may slow down the performance in practice. Consequently, designing efficient algorithms nowadays faces very different challenges from decades ago. This CAREER project focuses on two critical challenges in parallel algorithm design and analysis: space efficiency and communication efficiency. The project will provide efficient computational models to better meet multiobjective optimization formulations, new graph algorithms and data structures with improved theoretical guarantees, as well as open-source software for the new data structures and algorithms. This project aims to bridge the gap between theory and practice, which is crucial for promoting the accessibility of parallelism to a diverse set of problems. The educational plan comprises redesign of algorithm courses to include memory storage considerations as well as support for a coding club and coding competition designed to make computer science more accessible, particularly to the underrepresented student population reflected in the local area. This project has two major thrusts. The first thrust is to study space-efficient parallel algorithms. This project will first study a simple yet effective computational model for measuring space usage of a parallel algorithm with the objective of investigating space-efficient parallel graph algorithms and data structures using auxiliary space sublinear to the input size. The second thrust is to study algorithm design on the new processing-in-memory (PIM) system, which has recently been developed to reduce the need for expensive data transfers between CPU and memory. The algorithmic challenge here is that the PIM system is a combination of shared memory and distributed memory, so efficient algorithms on PIM must utilize advantages of each. This project will study algorithms and data structures that are efficient on the PIM architecture. The expected outcome of this project will be algorithms with strong theoretical guarantees and good practical performance, and general lessons in designing and performance engineering efficient algorithms on modern computer architectures.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.