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, CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France
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.
Type de document :
Communication dans un congrès
International Symposium on Code Generation and Optimization (CGO'11), Apr 2011, Chamonix, France. 2011
Liste complète des métadonnées

Littérature citée [41 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00551076
Contributeur : Albert Cohen <>
Soumis le : lundi 31 janvier 2011 - 17:10:29
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : samedi 3 décembre 2016 - 08:59:31

Fichier

cgo11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00551076, version 1

Collections

Citation

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. 2011. 〈inria-00551076〉

Partager

Métriques

Consultations de la notice

483

Téléchargements de fichiers

164