CAREER: Efficient Algorithms for Modern Computer Architecture

最近的计算机硬件进步使并行处理器成为主流，并为提高计算效率和生产率提供了潜力。要享受现代多核机器的好处，算法必须适应内存中的数据和辅助空间。在现代硬件上，在算法中使用过多的空间限制了多核机器上可解问题的大小，并且可能会在实践中降低性能。因此，设计高效的算法如今面临着与几十年前截然不同的挑战。这个职业项目关注并行算法设计和分析中的两个关键挑战：空间效率和通信效率。该项目将提供高效的计算模型，以更好地满足多目标优化公式、新的图形算法和经过改进的理论保证的数据结构，以及用于新的数据结构和算法的开源软件。该项目旨在弥合理论与实践之间的鸿沟，这对于促进并行处理一系列不同问题至关重要。教育计划包括重新设计算法课程，以纳入内存存储考虑因素，以及支持编码俱乐部和编码竞赛，旨在使计算机科学更容易获得，特别是对当地反映出的代表不足的学生群体。这个项目有两个主要推动力。第一个重点是研究空间效率高的并行算法。这个项目将首先研究一个简单而有效的计算模型，用于测量并行算法的空间使用情况，目的是研究空间效率高的并行图算法和使用辅助空间与输入大小次线性的数据结构。第二个重点是研究新的内存中处理(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.