AF: SMALL: Parallel Cache-efficient Data Structures

There are two main challenges when it comes to software efficiency and scalability on modern systems: taking advantage of multiple processors to get enough data to processors and keeping them occupied with work throughout the computation. The first challenge is known as parallelism, and the second one is known as I/O-efficiency or cache-efficiency. The goal of this project is to understand the power and limitations of various existing models of parallel and I/O-efficient computation and to apply the gained knowledge to discover new techniques for designing data structures that are both parallel and cache-efficient. Data structures are essential to simplifying software development and contributing to code reuse. This project will produce a number of parallel cache-efficient data structures, hence contributing to the overall goal of simplifying software design and increasing code reuse on modern high-performance systems. The project will also offer paid research training opportunities for undergraduate and graduate students. To achieve this goal, the project will proceed along four main thrusts of investigation. (1) Fractional cascading is a classical data structuring technique and a multi-way distribution framework is a fundamental technique for designing I/O-efficient algorithms. The project will incorporate fractional cascading into the multi-way distribution framework, combining parallelism with I/O efficiency. (2) (Partial) persistence in a search tree allows multiple queries to be performed independently of each other despite the updates modifying the search tree between the queries. The project will develop a parallel construction of (partially) persistent B-trees, hence providing a simple way of achieving query parallelization on dynamic B-trees. (3) Amortized analysis is a powerful data structuring technique. The project will extend this technique to the parallel computational models that support I/O efficiency. (4) Finally, the project will prove a number of lower bounds for data structures in parallel and I/O-efficient models of computation, contributing to our collective understanding of the power and limitations of these models. 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.