AitF: Collaborative Reserach: Theory and Implementation of Dynamic Data Structures for the GPU

Computers organize data in 'data structures,' which are designed to allow certain operations on data such as looking up all items that match a particular set of criteria, or adding new items to an existing data set. Computer scientists strive to build data structures that can perform these operations quickly and efficiently. One way to make data structure operations faster is to use not just one but many processors, operating in parallel, to perform a given operation. However, many of today's parallel data structures support only a limited set of operations and, notably, do not allow operations that modify these data structures instead of rebuilding an entire structure from scratch when only part of the data is updated. In this project the PIs bring together expertise in data structures and parallel computing to design, build, and evaluate dynamic data structures that allow update operations. This work targets the high-performance, highly-parallel graphics processing unit (GPU) and will significantly broaden the class of applications that the GPU can address. The PIs will release their results as freely-available open-source software and will work with industrial partner NVIDIA to incorporate the research and educational outcomes of this project into NVIDIA's broad educational efforts.

In this project the PIs propose to build dynamic, high-performance data structures for manycore (GPU) computing. Today's GPU data structures are rarely constructed on the GPU but instead are built on the CPU and copied to the GPU, and today's GPU data structures cannot be updated dynamically on the GPU but instead must be rebuilt from scratch. This project targets dynamic dictionary data structures with point and range queries, lists, and approximate membership and range query structures. The PIs will implement these data structures as high-performance, flexible, open-source software and use these data structures to develop a theoretical model, targeted at the GPU, for use by theorists and practitioners in manycore computing. The project will also focus on numerous cross-cutting issues in data structure design, implementation, modeling, and evaluation that have the potential for significant practical impact on manycore computing.