• Martin Farach-Colton

Congratulations to Prof. Martin Farach-Colton, who has just received an NSF grant for his project entitled “Theory and Implementation of Dynamic Data Structures for the GPU.” The grant is collaborative with John Owens of UC-Davis, and Rutgers’ portion of the grant is $349,409.00.

Computers organize data in “data structures,” which are designed to allow certain operations on this data, such as looking up all data that matches a particular set of criteria, or adding new data to an existing data set. Computer scientists hope 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 the operation. However, today?s parallel data structures only support a limited set of operations and notably do not allow operations that modify these data structures. 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 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 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 query, 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 also construct 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 impact on manycore computing.