Title: The relation between diamond tiling and hexagonal tiling
Authors: Grosser, Tobias
Verdoolaege, Sven
Cohen, Albert
Sadayappan, P.
Issue Date: Jan-2014
Host Document: 1st Int'l Workshop on High-Performance Stencil Computations (HiStencils 2014)
Conference: HiStencils edition:2014 location:Vienna, Austria date:21 January 2014
Abstract: Iterative stencil computations are important in scientific computing and more
and more also in the embedded and mobile domain. Recent publications have
shown that tiling schemes that ensure concurrent start provide efficient ways
to execute these kernels. Diamond tiling and hybrid-hexagonal tiling are two
successful tiling schemes that enable concurrent start. Both have different
advantages: diamond tiling is integrated in a general purpose optimization
framework and uses a cost function to choose among tiling hyperplanes,
whereas the more flexible tile sizes of hybrid-hexagonal tiling have proven
to be effective for the generation of GPU code.

We show that these two approaches are
even more interesting when combined. We revisit the formalization of
diamond and hexagonal tiling,
present the effects of tile size and wavefront choices on tile-level
parallelism, and formulate constraints for optimal diamond tile shapes. We
then extend the diamond tiling formulation into a hexagonal tiling one,
combining the benefits of both. The paper closes with
an outlook of hexagonal tiling in higher dimensional spaces,
an important generalization suitable for massively parallel architectures.
Publication status: published
KU Leuven publication type: IMa
Appears in Collections:Informatics Section

Files in This Item:
File Description Status SizeFormat
histencils2014-grosser.pdf Published 2522KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.