The Promises of Hybrid Hexagonal/Classical Tiling for GPU

Tobias Grosser 1 Sven Verdoolaege 1 Albert Cohen 1 P. Sadayappan 2
1 Parkas - Parallélisme de Kahn Synchrone
CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria Paris-Rocquencourt, DI-ENS - Département d'informatique de l'École normale supérieure
Abstract : Time-tiling is necessary for efficient execution of iterative stencil computations. But the usual hyper-rectangular tiles cannot be used because of positive/negative dependence distances along the stencil's spatial dimensions. Several prior efforts have addressed this issue. However, known techniques trade enhanced data reuse for other causes of inefficiency, such as unbalanced parallelism, redundant computations, or increased control flow overhead incompatible with efficient GPU execution. We explore a new path to maximize the effectivness of time-tiling on iterative stencil computations. Our approach is particularly well suited for GPUs. It does not require any redundant computations, it favors coalesced global-memory access and data reuse in shared-memory/cache, avoids thread divergence, and extracts a high degree of parallelism. We introduce hybrid hexagonal tiling, combining hexagonal tile shapes along the time (sequential) dimension and one spatial dimension, with classical tiling for other spatial dimensions. An hexagonal tile shape simultaneously enable parallel tile execution and reuse along the time dimension. Experimental results demonstrate significant performance improvements over existing stencil compilers.
Document type :
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download
Contributor : Albert Cohen <>
Submitted on : Saturday, July 27, 2013 - 9:11:01 PM
Last modification on : Thursday, February 7, 2019 - 3:49:20 PM
Long-term archiving on : Wednesday, April 5, 2017 - 5:15:39 PM


Files produced by the author(s)


  • HAL Id : hal-00848691, version 1



Tobias Grosser, Sven Verdoolaege, Albert Cohen, P. Sadayappan. The Promises of Hybrid Hexagonal/Classical Tiling for GPU. [Research Report] RR-8339, INRIA. 2013. ⟨hal-00848691⟩



Record views


Files downloads