Informatics Report Series


Report   

EDI-INF-RR-0951


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Hybrid Optimizations: Which Optimization Algorithm to Use?
Authors: John Cavazos ; J. Eliot B. Moss ; Michael O'Boyle
Date:Mar 2006
Publication Title:Complier Construction (LNCS)
Publisher:Springer
Publication Type:Conference Paper Publication Status:Published
Volume No:3923 Page Nos:124-138
DOI:10.1007/11688839_12 ISBN/ISSN:978-3-540-33050-9
Abstract:
We introduce a new class of compiler heuristics: hybrid optimizations. Hybrid optimizations choose dynamically at compile time which optimization algorithm to apply from a set of different algorithms that implement the same optimization. They use a heuristic to predict the most appropriate algorithm for each piece of code being optimized. Specifically, we construct a hybrid register allocator that chooses between linear scan and graph coloring register allocation. Linear scan is more efficient, but sometimes less effective; graph coloring is generally more expensive, but sometimes more effective. Our setting is Java JIT compilation, which makes optimization algorithm efficiency particularly important. Our hybrid allocator decides, based on features of a method, which algorithm to apply to that method. We used supervised learning to induce the decision heuristic. We evalute our technique within Jikes RVM [1] and show on average it outperforms graph coloring by 9% and linear scan by 3% for a typical compilation scenario. To our knowledge, this is the first time anyone has used heuristics induced by machine learning to select between different optimization algorithms.
Copyright:
2006 by The University of Edinburgh. All Rights Reserved
Links To Paper
1st Link
Bibtex format
@InProceedings{EDI-INF-RR-0951,
author = { John Cavazos and J. Eliot B. Moss and Michael O'Boyle },
title = {Hybrid Optimizations: Which Optimization Algorithm to Use?},
book title = {Complier Construction (LNCS)},
publisher = {Springer},
year = 2006,
month = {Mar},
volume = {3923},
pages = {124-138},
doi = {10.1007/11688839_12},
url = {http://homepages.inf.ed.ac.uk/jcavazos/cc-2006.pdf},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh