Program optimization space pruning for a multithreaded GPU

Shane Ryoo, Christopher I. Rodrigues, Sam S. Stone, Sara S. Baghsorkhi, Sain Zee Ueng, John A. Stratton, Wen Mei W. Hwu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Program optimization for highly-parallel systems has historically been considered an art, with experts doing much of the performance tuning by hand. With the introduction of inexpensive, single-chip, massively parallel platforms, more developers will be creating highly-parallel applications for these platforms, who lack the substantial experience and knowledge needed to maximize their performance. This creates a need for more structured optimization methods with means to estimate their performance effects. Furthermore these methods need to be understandable by most programmers. This paper shows the complexity involved in optimizing applications for one such system and one relatively simple methodology for reducing the workload involved in the optimization process. This work is based on one such highly-parallel system, the GeForce 8800 GTX using CUDA. Its flexible allocation of resources to threads allows it to extract performance from a range of applications with varying resource requirements, but places new demands on developers who seek to maximize an application's performance. We show how optimizations interact with the architecture in complex ways, initially prompting an inspection of the entire configuration space to find the optimal configuration. Even for a seemingly simple application such as matrix multiplication, the optimal configuration can be unexpected. We then present metrics derived from static code that capture the first-order factors of performance. We demonstrate how these metrics can be used to prune many optimization configurations, down to those that lie on a Pareto-optimal curve. This reduces the optimization space by as much as 98% and still finds the optimal configuration for each of the studied applications.

Original languageEnglish (US)
Title of host publicationProceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization
Number of pages10
StatePublished - 2008

Publication series

NameProceedings of the 2008 CGO - Sixth International Symposium on Code Generation and Optimization


  • Optimization
  • Parallel computing

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Program optimization space pruning for a multithreaded GPU'. Together they form a unique fingerprint.

Cite this