Skip to Main content Skip to Navigation
Journal articles

Flextended Tiles: a Flexible Extension of Overlapped Tiles for Polyhedral Compilation

Albert Cohen 1, 2 Jie Zhao 1
1 Parkas - Parallélisme de Kahn Synchrone
Inria de Paris, DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique
Abstract : Loop tiling to exploit data locality and parallelism plays an essential role in a variety of general-purpose and domain-specific compilers. Affine transformations in polyhedral frameworks implement classical forms of rectangular and parallelogram tiling, but these lead to pipelined start with rather inefficient wavefront parallelism. Multiple extensions to polyhedral compilers evaluated sophisticated shapes such as trapezoid or diamond tiles, enabling concurrent start along the axes of the iteration space; yet these resort to custom schedulers and code generators insufficiently integrated within the general framework. One of these modified shapes referred to as overlapped tiling also lacks a unifying framework to reason about its composition with affine transformations; this prevents its application in general-purpose loop-nest optimizers and the fair comparison with other techniques. We revisit overlapped tiling, recasting it as an affine transformation on schedule trees composable with any affine scheduling algorithm. We demonstrate how to derive tighter tile shapes with less redundant computations. Our method models the traditional "scalene trapezoid" shapes as well as novel "right-rectangle" variants. It goes beyond the state of the art by avoiding the restriction to a domain-specific language or introducing post-pass rescheduling and custom code generation. We conduct experiments on the PolyMage benchmarks and iterated stencils, validating the effectiveness and applicability of our technique on both general-purpose multicores and GPU accelerators.
Document type :
Journal articles
Complete list of metadata

Cited literature [39 references]  Display  Hide  Download

https://hal.inria.fr/hal-02458507
Contributor : Albert Cohen <>
Submitted on : Tuesday, January 28, 2020 - 5:42:13 PM
Last modification on : Wednesday, October 14, 2020 - 4:06:13 AM
Long-term archiving on: : Wednesday, April 29, 2020 - 4:44:03 PM

File

polytile.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Albert Cohen, Jie Zhao. Flextended Tiles: a Flexible Extension of Overlapped Tiles for Polyhedral Compilation. ACM Transactions on Architecture and Code Optimization, Association for Computing Machinery, 2020, ⟨10.1145/3369382⟩. ⟨hal-02458507⟩

Share

Metrics

Record views

117

Files downloads

426