Skip to Main content Skip to Navigation
Conference papers

Predictive Modeling in a Polyhedral Optimization Space

Eunjung Park 1 Louis-Noël Pouchet 2 John Cavazos 1 Albert Cohen 3 P. Saddayapan 2
3 ALCHEMY - Architectures, Languages and Compilers to Harness the End of Moore Years
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : It has been shown that the right set of polyhedral optimizations can make a significant difference in the running time of a program. However, the number of alternatives for a program transformed with polyhedral optimizations can be enormous. Thus, it is often impossible to iterate over a significant fraction of the entire space of polyhedral transformed variants. Recent research has focused on iterating over this search space with manually-constructed heuristics or with expensive search algorithms (e.g., genetic algorithms) that can eventually find good points in the polyhedral space. In this paper, we evaluate methods of modeling the polyhedral optimization problem using machine learning techniques. We show that these techniques can quickly find excellent program variants in the polyhedral space. We introduce two different modeling techniques, we call a "one-shot" model and a "reactive" model. Our one-shot model takes as input "one" characterization of the program and outputs several different variants that are predicted to give good performance. In contrast, our "reactive" model takes as input the characterization of the program that was last predicted to give good performance. Unlike the one-shot model, our reactive model explores the space of polyhedral program variants obtaining characterizations of each program variants and using these characterizations for the model to decide where to traverse the search space next. We show that our reactive predictor outperforms our one-shot model and can significantly outperform the most aggressive setting of state-of-the-art model-based heuristics in a just a few iterations.
Document type :
Conference papers
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download
Contributor : Albert Cohen <>
Submitted on : Monday, January 31, 2011 - 5:10:29 PM
Last modification on : Thursday, July 8, 2021 - 3:47:50 AM
Long-term archiving on: : Saturday, December 3, 2016 - 8:59:31 AM


Files produced by the author(s)


  • HAL Id : inria-00551076, version 1



Eunjung Park, Louis-Noël Pouchet, John Cavazos, Albert Cohen, P. Saddayapan. Predictive Modeling in a Polyhedral Optimization Space. International Symposium on Code Generation and Optimization (CGO'11), Apr 2011, Chamonix, France. ⟨inria-00551076⟩



Record views


Files downloads