Unified Polyhedral Modeling of Temporal and Spatial Locality

Abstract : Despite decades of work in this area, the construction of effective loop nest optimizers and parallelizers continues to be challenging due to the increasing diversity of both loop-intensive application workloads and complex memory/computation hierarchies in modern processors. The lack of a systematic approach to optimizing locality and parallelism, with a well-founded data locality model, is a major obstacle to the design of optimizing compilers coping with the variety of software and hardware. Acknowledging the conflicting demands on loop nest optimization, we propose a new unified algorithm for optimizing parallelism and locality in loop nests, that is capable of modeling temporal and spatial effects of multiprocessors and accelerators with deep memory hierarchies and multiple levels of parallelism. It orchestrates a collection of parameterizable optimization problems for locality and parallelism objectives over a polyhedral space of semantics-preserving transformations. The overall problem is not convex and is only constrained by semantics preservation. We discuss the rationale for this unified algorithm, and validate it on a collection of representative computational kernels/benchmarks.
Document type :
Reports
Complete list of metadatas

Cited literature [51 references]  Display  Hide  Download

https://hal.inria.fr/hal-01628798
Contributor : Albert Cohen <>
Submitted on : Monday, November 6, 2017 - 11:35:55 AM
Last modification on : Tuesday, March 5, 2019 - 9:30:10 AM
Long-term archiving on : Wednesday, February 7, 2018 - 1:11:03 PM

Identifiers

  • HAL Id : hal-01628798, version 1

Collections

Citation

Oleksandr Zinenko, Sven Verdoolaege, Chandan Reddy, Jun Shirako, Tobias Grosser, et al.. Unified Polyhedral Modeling of Temporal and Spatial Locality. [Research Report] RR-9110, Inria Paris. 2017, pp.41. ⟨hal-01628798⟩

Share

Metrics

Record views

430

Files downloads

380