Modeling the Conflicting Demands of Parallelism and Temporal/Spatial Locality in Affine Scheduling

Oleksandr Zinenko, Sven Verdoolaege, Chandan Reddy, Jun Shirako, Tobias Grosser, Vivek Sarkar, Albert Cohen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

The construction of effective loop nest optimizers and parallelizers 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.
Original languageEnglish
Title of host publicationProceedings of the 27th International Conference on Compiler Construction
Place of PublicationNew York, NY, USA
Number of pages11
ISBN (Print)978-1-4503-5644-2
Publication statusPublished - 24 Feb 2018
Event27th International Conference on Compiler Construction - Vienna, Austria
Duration: 24 Feb 201825 Feb 2018

Publication series



Conference27th International Conference on Compiler Construction
Abbreviated titleCC'18
Internet address

Keywords / Materials (for Non-textual outputs)

  • Compiler Optimizations
  • Polyhedral Model


Dive into the research topics of 'Modeling the Conflicting Demands of Parallelism and Temporal/Spatial Locality in Affine Scheduling'. Together they form a unique fingerprint.

Cite this