Divergence Analysis and Optimizations

The growing interest in GPU programming has brought renewed attention to the Single Instruction Multiple Data (SIMD) execution model. SIMD machines give application developers a tremendous computational power; however, the model also bring restrictions. In particular, processing elements (PEs) execute in lock-step, and might lose performance due to divergences in the program’s control flow. In face of divergences, some PEs will execute, while others wait, until they reach a synchronization point. The need to reason about divergences complicates SIMD programming, a fact that motivates our work: our objective is to free developers from these complications, moving to the compiler the task to reduce the cost of divergences. We have implemented a static analysis that determines which conditional branches might cause divergences. We have also introduced two optimizations that specifically improve divergent code. The first – and simpler – optimization consists in replacing non-divergent branches by cheaper instructions. Our second optimization is much more elaborate: we use the Smith-Waterman gene sequencing algorithm to identify chains of similarities between two possibly divergent program paths, and weave these paths together as much as possible. We have implemented our techniques on the Ocelot open-source CUDA compiler, and have tested it on many industrial-strength GPU benchmarks, including Rodinia and the Nvidia’s SDK. Our divergence analysis has a 34% false-positive rate, compared to the results of a dynamic profiler. Our optimizations provide gains of up to 4% for heavily optimized industrial-strength benchmarks, including a well-known version of parallel quicksort. Our implementation is freely available. For more details about the divergence analysis, we recommend our PACT 2011 paper, Divergence Analysis and Optimizations. For a more concise tutorial, see the slides that we used in PACT, or a short class on the subject.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s