AitF: FULL: Collaborative Research: Provably Efficient GPU Algorithms

New York University, New York NY

Investigators

Abstract

Graphics processing units (GPUs) were originally developed as specialized hardware exclusively for graphics rendering. In recent years they have become massively parallel systems with hundreds of processing cores supporting thousands of threads. Given their computational potential, they are now used to support general-purpose computation via high-level programming languages. As a result, they have become a standard platform for high-performance computing (HPC) simulations in natural sciences. However, there is still very little understanding of what types of algorithms translate into efficient GPU programs, and many implementations rely on a limited number of design patterns and many rounds of trial-and-error. There is a need for simple but accurate algorithmic models to get a wider algorithmic community involved in GPU computing. The project will develop such a model, intended to have the transformative effect of enabling algorithms researchers to focus their efforts on creating algorithms for GPUs in a way that is currently not possible, increasing the algorithmic knowledgebase in GPU computing. Over time, more efficient algorithms will lead to better utilization of computing resources and reuse of code implemented as libraries. Such a model for GPUs will also enable teaching GPU computing to a wider group of students, similarly to how sequential and PRAM algorithms are currently taught. This project will study the algorithmic aspects of GPU computing and will develop a simple but accurate theoretical model for GPUs, that will define clear guidelines and complexity metrics for algorithm evaluation. The PIs will develop and implement algorithms that will improve the state of the art code base of general purpose computation on GPUs in the areas of combinatorial algorithms, computational geometry, visualization, search algorithms, and data structures.