AF: Small: New Directions for Parallel Data Structures

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.