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
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
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 :
Reports
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-00848691
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

File

RR-8339.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00848691, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

693

Files downloads

687