Beyond the Realm of the Polyhedral Model: Combining Speculative Program Parallelization with Polyhedral Compilation

Aravind Sukumaran-Rajam 1
1 CAMUS - Compilation pour les Architectures MUlti-coeurS
Inria Nancy - Grand Est, ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
Abstract : In this thesis, we present our contributions to APOLLO (Automatic speculative POLyhedral Loop Optimizer), which is an automated compiler combining Thread Level Speculation (TLS) and the polyhedral model to optimize codes on the fly. By doing partial instrumentation at runtime, and subjecting it to interpolation, Apollo is able to construct a speculative polyhedral model dynamically. The speculative model is then passed to Pluto -a static polyhedral scheduler-. Apollo then selects one of the statically generated code optimization skeletons and instantiates it. The runtime continuously monitors the code for any dependence violation in a decentralized manner. Another important contribution of this thesis is our extension of the polyhedral model to codes exhibiting a non linear behavior. Thanks to the dynamic and speculative context offered by Apollo, non-linear behaviors are either modeled using linear regression hyperplanes forming tubes, or using ranges of reached values. Our approach enables the application of polyhedral transformations to non-linear codes thanks to an hybrid centralized-decentralized speculation verification system.
Document type :
Theses
Complete list of metadatas

Cited literature [82 references]  Display  Hide  Download

https://hal.inria.fr/tel-01251748
Contributor : Philippe Clauss <>
Submitted on : Wednesday, January 6, 2016 - 4:28:51 PM
Last modification on : Saturday, October 27, 2018 - 1:23:50 AM
Long-term archiving on : Thursday, April 7, 2016 - 4:09:19 PM

Identifiers

  • HAL Id : tel-01251748, version 1

Citation

Aravind Sukumaran-Rajam. Beyond the Realm of the Polyhedral Model: Combining Speculative Program Parallelization with Polyhedral Compilation. Computation and Language [cs.CL]. Université de Strasbourg, 2015. English. ⟨tel-01251748⟩

Share

Metrics

Record views

512

Files downloads

374