Hybrid Hexagonal/Classical Tiling for GPUs

Tobias Grosser, Albert Cohen, Justin Holewinski, Ponuswamy Sadayappan, Sven Verdoolaege

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


Time-tiling is necessary for the efficient execution of iterative stencil computations. Classical hyper-rectangular tiles cannot be used due to the combination of backward and forward dependences along space dimensions. Existing techniques trade temporal data reuse for inefficiencies in other areas, such as load imbalance, redundant computations, or increased control flow overhead, therefore making it challenging for use with GPUs.

We propose a time-tiling method for iterative stencil computations on GPUs. Our method does not involve redundant computations. It favors coalesced global-memory accesses, data reuse in local/shared-memory or cache, avoidance of thread divergence, and concurrency, combining hexagonal tile shapes along the time and one spatial dimension with classical tiling along the other spatial dimensions. Hexagonal tiles expose multi-level parallelism as well as data reuse. Experimental results demonstrate significant performance improvements over existing stencil compilers.
Original languageEnglish
Title of host publicationProceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization
Number of pages10
ISBN (Electronic)9781450326704
Publication statusPublished - 15 Feb 2014
Event2014 International Symposium on Code Generation and Optimization - Orlando, United States
Duration: 15 Feb 201419 Feb 2014

Publication series



Symposium2014 International Symposium on Code Generation and Optimization
Abbreviated titleCGO 2014
Country/TerritoryUnited States
Internet address


Dive into the research topics of 'Hybrid Hexagonal/Classical Tiling for GPUs'. Together they form a unique fingerprint.

Cite this