Divergence analysis

Growing interest in graphics processing units has brought renewed attention to the Single Instruction Multiple Data (SIMD) execution model. SIMD machines give application developers tremendous computational power; however, programming them is still challenging. In particular, developers must deal wi...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on programming languages and systems 2013-12, Vol.35 (4), p.1-36, Article 13
Main Authors: Sampaio, Diogo, Souza, Rafael Martins de, Collange, Caroline, Pereira, Fernando Magno Quintão
Format: Article
Language:English
Subjects:
Applied sciences
Benchmarks
Compilers
Computer Science
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Computer systems performance. Reliability
Developers
Divergence
Exact sciences and technology
Hardware Architecture
Optimization
Programming
Programming Languages
Programming theory
Registers
Software
Software and its engineering
Software notations and tools
Theoretical computing
Translations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Growing interest in graphics processing units has brought renewed attention to the Single Instruction Multiple Data (SIMD) execution model. SIMD machines give application developers tremendous computational power; however, programming them is still challenging. In particular, developers must deal with memory and control-flow divergences. These phenomena stem from a condition that we call data divergence, which occurs whenever two processing elements (PEs) see the same variable name holding different values. This article introduces divergence analysis, a static analysis that discovers data divergences. This analysis, currently deployed in an industrial quality compiler, is useful in several ways: it improves the translation of SIMD code to non-SIMD CPUs, it helps developers to manually improve their SIMD applications, and it also guides the automatic optimization of SIMD programs. We demonstrate this last point by introducing the notion of a divergence-aware register spiller. This spiller uses information from our analysis to either rematerialize or share common data between PEs. As a testimony of its effectiveness, we have tested it on a suite of 395 CUDA kernels from well-known benchmarks. The divergence-aware spiller produces GPU code that is 26.21% faster than the code produced by the register allocator used in the baseline compiler.
ISSN:0164-0925
1558-4593
DOI:10.1145/2523815