AF: Small: New Directions for Parallel Data Structures

在过去的十年中，硬件的进步使多核并行机成为主流。如今，几乎不可能找到单核处理器，研究多核处理器上的并行算法具有巨大的现实意义和重大的理论意义。算法设计的一个非常重要的方面是设计高效和易于使用的数据结构。该项目旨在开发新的并行数据结构，能够促进并行算法的实现，具有良好的理论保证和实际性能。此外，研究小组还寻求开发即将问世的数据结构和算法的库实现，并将公开提供。该项目包括一个教育部分，将把并行算法整合到现有的本科课程中，并开发关于并行计算理论和实践的研究生课程。该项目特别旨在研究三种并行数据结构及其潜在的应用。第一个工作是研究一种高效的并行动态最近邻搜索的数据结构，并将其应用于层次聚类问题。第二部分对并行优先级队列进行了研究，从理论和实践两个方面研究了并行单源最短路径(SSSP)问题及其相关问题。这包括统一现有算法，为优先级队列提供更好的设计，从而设计出与现有算法的成本界限相匹配的并行SSSP算法，同时在实践中也是快速的。第三个推力研究了一个与并行依赖图相关的算法框架，该框架允许异步。依赖图是并行计算中捕捉对象间依赖关系的数据结构。它们已被证明对各种并行算法的设计是有效的。该项目计划为执行依赖图的通用框架开发底层数据结构。该项目的预期成果包括一系列基本图形和几何问题的高效并行算法，这些算法在理论上和实践上都是简单和高效的。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Hardware advances in the last decade have brought multicore parallel machines to the mainstream. Today, it becomes almost impossible to find a single-core processor, and studying parallel algorithms on multicore processors has become of huge practical relevance and significant theoretical interest. A very important aspect of algorithm design is to design data structures that are efficient and easy to use. This project aims to develop new parallel data structures that can facilitate parallel algorithms with good theoretical guarantees and practical performance. Also, the research team seeks to develop library implementations of the outcoming data structures and algorithms, which will be publicly available. The project includes an educational component that will integrate parallel algorithms in existing undergraduate courses and develop graduate-level courses about the theory and practice of parallel computing.In particular, this project aims at studying three parallel data structures and their potential applications. The first effort studies an efficient data structure for parallel dynamic nearest-neighbor search, with numerous applications to hierarchical clustering problems. The second studies a parallel priority queue with the goal of developing efficient algorithms for the parallel single-source shortest paths (SSSP) and related problems, both in theory and in practice. This includes unifying the existing algorithms, providing better design for priority queues, and thereby designing parallel SSSP algorithms that match the cost bounds of existing algorithms while also being fast in practice. The third thrust studies an algorithmic framework related to parallel dependence graphs, which allows for asynchrony. Dependence graphs are data structures to capture the dependence between objects in parallel computation. They have been shown effective for the design of various parallel algorithms. This project plans to develop the underlying data structures for a general framework to execute dependence graphs. The expected outcomes of this project include a list of efficient parallel algorithms for fundamental graph and geometric problems that are simple and efficient both theoretically and in practice.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.