ABSTRACT

There is growing interest in using Graphics Processing Units (GPUs) to increase the performance and the energy efficiency of applications outside the graphics domain. GPUs are particularly suited to run regular programs that perform operations similar to pixel processing, and they can offer a large advantage over multicore CPUs in terms of performance, price, and energy efficiency in this domain. Not surprisingly, GPUs are increasingly appearing in devices ranging from handhelds to supercomputers.

Although regular algorithms are very important, new problem domains such as computational biology, data mining, and social networks necessitate very different algorithmic foundations: they require building, computing with, and updating large graphs. Unfortunately, relatively little is understood about how to implement irregular applications efficiently on current GPU architectures. Features such as lockstep operation and the need to minimize thread divergence and maximize memory coalescing pose particular challenges to efficient implementation of irregular algorithms. Nevertheless, some recent successes in hand-porting irregular codes suggest that the difficulties lie not in the GPU hardware but in the immaturity of the state of the art of writing and tuning GPU code due to the lack of general, well-understood optimization techniques.

This work will develop programming notations, compiler optimizations, and runtime system support that will enable programmers to express their algorithms at a high level of abstraction but still yield good performance. Projected tasks include producing highly optimized handwritten GPU implementations of important irregular algorithms and adding them to the LonestarGPU benchmark suite, identifying common patterns of optimizations and runtime systems support needed for efficient GPU implementations, developing a programming notation to permit the software developer to specify irregular algorithms at a high level of abstraction, implementing a synthesis system that automatically generates high-performance GPU code from these high-level specifications, and developing course material for teaching GPU programming of irregular codes.

The higher performance and better energy efficiency of GPUs relative to multicore CPUs has sincere societal benifits. This work builds on the realization of these benefits by facilitating simpler and more widespread utilization of GPUs and incorporating more effective practices into future compilers and GPU hardware.

Please report errors in award information by writing to: awardsearch@nsf.gov.