Modeling the conflicting demands of parallelism and Temporal/Spatial locality in affine scheduling

Oleksandr Zinenko 1 Sven Verdoolaege 2 Chandan Reddy 1 Jun Shirako 3 Tobias Grosser 4 Vivek Sarkar 3 Albert Cohen 1
1 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
2 KU Leuven - Catholic University of Leuven - Katholieke Universiteit Leuven
3 Georgia Institute of Technology (Georgia Tech)
4 ETH Zürich - Eidgenössische Technische Hochschule - Swiss Federal Institute of Technology in Zürich [Zürich]
Abstract : The construction of effective loop nest optimizers and par-allelizers remains challenging despite decades of work in the area. Due to the increasing diversity of loop-intensive applications and to the complex memory/computation hierarchies in modern processors, optimization heuristics are pulled towards conflicting goals, highlighting the lack of a systematic approach to optimizing locality and parallelism. Acknowledging these conflicting demands on loop nest optimization , we propose an algorithmic template capable of modeling the multi-level parallelism and the temporal/spatial locality of multiprocessors and accelerators. This algorithmic template orchestrates a collection of parameterizable, linear optimization problems over a polyhedral space of semantics-preserving transformations. While the overall problem is not convex, effective algorithms can be derived from this template delivering unprecedented performance portability over GPU and multicore CPU. We discuss the rationale for this algorithmic template and validate it on representative computational kernels/benchmarks.
Keywords : Compilers Polyhedral model
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [36 references]  Display  Hide  Download
https://hal.inria.fr/hal-01751823
Contributor : Oleksandr Zinenko <>
Submitted on : Thursday, March 29, 2018 - 2:41:43 PM
Last modification on : Tuesday, March 5, 2019 - 9:32:53 AM

File

paper.pdf
Files produced by the author(s)

Identifiers

Collections

ENS-PARIS | PSL | INRIA | INRIA-ROCQ

Citation

Oleksandr Zinenko, Sven Verdoolaege, Chandan Reddy, Jun Shirako, Tobias Grosser, et al.. Modeling the conflicting demands of parallelism and Temporal/Spatial locality in affine scheduling. CC'18 - 27th International Conference on Compiler Construction, Feb 2018, Vienna, Austria. ⟨10.1145/3178372.3179507⟩. ⟨hal-01751823⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

291

Files downloads

203

Contact


archive-ouverte@inria.fr