A Quantitative Study of Irregular Programs on GPUs

Martin Burtscher, Rupesh Nasre, Keshav Pingali
Texas State University, San Marcos, Texas, USA
IEEE International Symposium on Workload Characterization (IISWC’12), 2012


   title={A Quantitative Study of Irregular Programs on GPUs},

   author={Burtscher, M. and Nasre, R. and Pingali, K.},



Download Download (PDF)   View View   Source Source   



GPUs have been used to accelerate many regular applications and, more recently, irregular applications in which the control flow and memory access patterns are data-dependent and statically unpredictable. This paper defines two measures of irregularity called control-flow irregularity and memory-access irregularity, and investigates, using performance-counter measurements, how irregular GPU kernels differ from regular kernels with respect to these measures. For a suite of 13 benchmarks, we find that (i) irregularity at the warp level varies widely, (ii) control-flow irregularity and memory-access irregularity are largely independent of each other, and (iii) most kernels, including regular ones, exhibit some irregularity. A program’s irregularity can change between different inputs, systems, and arithmetic precision but generally stays in a specific region of the irregularity space. Whereas some highly tuned implementations of irregular algorithms exhibit little irregularity, trading off extra irregularity for better locality or less work can improve overall performance.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: