Michele Tartara
Skip Abstract Section
Abstract
Optimizing programs to exploit the underlying hardware architecture is an important task. Much research has been done on enabling compilers to find the best set of code optimizations that can build the fastest and less resource-hungry executable for a given program. A common approach is iterative compilation, sometimes enriched by machine learning techniques. This provides good results, but requires extremely long compilation times and an initial training phase lasting even for days or weeks.
We present long-term learning, a new algorithm that allows the compiler user to improve the performance of compiled programs with reduced compilation times with respect to iterative compilation, and without an initial training phase. Our algorithm does not just build good programs: it acquires knowledge every time a program is compiled and it uses such knowledge to learn compiler heuristics, without the need for an expert to manually define them. The heuristics are evolved during every compilation, by evaluating their effect on the generated programs. We present implementations of long-term learning on top of two different compilers, and experimental data gathered on multiple hardware configurations showing its effectiveness.
- Agakov, F. V., Bonilla, E. V., Cavazos, J., Franke, B., Fursin, G., et al. 2006. Using machine learning to focus iterative optimization. In Proceedings of the International Symposium on Code Generation and Optimization. 295--305. Google Scholar
Digital Library
- Ansel, J., Chan, C. P., Wong, Y. L., Olszewski, M., Zhaq, Q., et al. 2009. Petabricks: A language and compiler for algorithm choice. In Proceedings of the 2009 ACM SIGPLAN Conference on Programming Language Design and Implementation. 38--49. Google ScholarDigital Library
- Ansel, J., Pacula, M., Amarasinghe, S. P., and O'Reilly, U. -M. 2011. An efficient evolutionary algorithm for solving incrementally structured problems. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. 1699--1706. Google ScholarDigital Library
- Arlandini, C. and Invernizzi, A. 2008. Lagrange: Un nuovo server per il calcolo ad alte pretazioni. Bollettino del CILEA 0, 110.Google Scholar
- Blum, A. 1996. On-Line algorithms in machine learning. In Proceedings of the Workshop on OnLine Algorithms. Springer, 306--325. Google ScholarDigital Library
- Bodin, F., Kisuki, T., Knijnenburg, P., O'Boyle, M., and Rohou, E. 1998. Iterative compilation in a non-linear optimization space. In Proceedings of the Workshop on Profile and Feedback Directed Compilation in conjunction with the International Conference on Parallel Architectures and Compilation Techniques (PACT).Google Scholar
- Cavazos, J., Fursin, G., Agakov, F. V., Bonilla, E. V., O'Boyle, M. F. P., et al. 2007. Rapidly selecting good compiler optimizations using performance counters. In Proceedings of the 5th Annual International Symposium on Code Generation and Optimization. 185--197. Google ScholarDigital Library
- Dubach, C., Cavazos, J., Franke, B., Fursin, G., O'Boyle, M. F. P., et al. 2007. Fast compiler optimisation evaluation using code-feature based performance prediction. In Proceedings of the 4th International Conference on Computing Frontiers. 131--142. Google ScholarDigital Library
- Dubach, C., Jones T. M., Bonilla E. V., Fursin, G., and O'Boyle, M. F. P. 2009 Portable compiler optimisation across embedded programs and microarchitectures using machine learning. In Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture. 78--88. Google ScholarDigital Library
- Fogel, G. 2000. What is evolutionary computation? IEEE Spectrum 37, 2, 26--32. Google ScholarDigital Library
- Fursin, G. 2010. Collective benchmark (cbench), a collection of open-source programs with multiple datasets assembled by the community to enable realistic benchmarking and research on program and architecture optimization. http://ctuning.org/cbenchGoogle Scholar
- Fursin, G., Cavazos, J., O'Boyle, M. F. P., and Temam, O. 2007 Midatasets: Creating the conditions for a more realistic evaluation of iterative optimization. In Proceedings of the International Conference on High Performance Embedded Architectures & Compilers. 245--260. Google ScholarDigital Library
- Fursin, G., Kashnikov, Y., Memon, A. W., Chamski, Z., Teman, O., et al. 2011. Milepost gcc: Machine learning enabled self-tuning compiler. Int. J. Parallel Program 39, 3, 296--327.Google ScholarCross Ref
- Fursin, G., Miranda, C., Temam, O., Namolaru, M., Yom-Tov, E., et al. 2008. Milepost gcc: Machine learning based research compiler. In Proceedings of the GCC Developers Summit.Google Scholar
- Fursin, G. and Temam, O. 2010. Collective optimization: A practical collaborative approach. ACM Trans. Archit. Code Optim. 7, 4, 20. Google ScholarDigital Library
- Guthaus, M. R., Ringenberg, J. S., Ernst, D., Austin, T. M., Mudge, T., et al. 2001. Mibench: A free, commercially representative embedded benchmark suite. In Proceedings of the IEEE International Workshop on Workload Characterization (WWC'01). IEEE Computer Society, Los Alamitos, CA, 3--14. Google ScholarDigital Library
- Kaelbling, L. P., Littman, M. L., and Moore, A. W. 1996. Reinforcement learning: A survey. CoRR csAI/9605103.Google Scholar
- Kisuki, T., Knijnenburg, P., O'Boyle, M., and Wijshoff, H. A. G. 2000. Iterative compilation in program optimization. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.3007Google Scholar
- Kohavi, R. 1995. A study of cross- validation and bootstrap for accuracy estimation and model selection. In Proceedings of the 14th International Joint Conference on Artificial Intelligence. 1137--1145. Google ScholarDigital Library
- Kulkarni, P. A., Hines, S., Hiser, J., Whalley, D. B., Davidson, J. W., et al. 2004. Fast searches for effective optimization phase sequences. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation. 171--182. Google ScholarDigital Library
- Lattner, C. and Adve, V. S. 2004. LLVM: A compilation framework for lifelong program analysis & transformation. In Proceedings of the International Symposium on Code Generation and Optimization. 75--88. Google ScholarDigital Library
- Leather, H. 2011. Machine learning in compilers. Ph.D thesis, Institute of Computing Systems Architecture, School of Information, University of Edinburgh.Google Scholar
- Leather, H., Bonilla, E. V., and O'Boyle, M. F. P. 2009. Automatic feature generation for machine learning based optimizing compilation. In Proceedings of the 7th Annual IEEE/ACM International Symposium on Code Generation and Optimization. 81--91. Google ScholarDigital Library
- Long, S. 2011. Sustainable learning-based optimization based on rknm outlier detection. In Proceedings of the 5th Workshop on Statistical and Machine Learning Approaches to Architecture and Compliation (SMART'11).Google Scholar
- Merrill, J. 2003. GENERIC and GIMPLE: A new tree representation for entire functions. In Proceeedings of the GCC Summit. Red Hat Inc.Google Scholar
- Monsifrot, A., Bodin, F., and Quiniou, R. 2002. A machine learning approach to automatic production of compiler heuristics. In Proceedings of the 10th International Conference on Artificial Intelligence: Methodology, Systems, and Applications. 41--50. Google ScholarDigital Library
- Namolaru, M., Cohen, A., Fursin, G., Zaks, A., and Freund, A. 2010. Practical aggregation of semantical program properties for machine learning based optimization. In Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems. 197--206. Google ScholarDigital Library
- Park, E., Kulkarni, S., and Cavazos, J. 2011. An evaluation of different modeling techniques for iterative compilation. In Proceedings of the 14th International Conference on Compilers, Architectures and Synthesis for Embedded Systems. 65--74. Google ScholarDigital Library
- Russell, S. J. and Norvig, P. 2010. Artificial Intelligence -- A Modern Approach 3rd ED. Pearson Education. Google ScholarDigital Library
- Stephenson, M., Amarasinghe, S. P., Martin, M. C., and O'Reilly, U.-M. 2003. Meta optimization: Improving compiler heuristics with machine learning. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation. 77--90. Google ScholarDigital Library
- Tartara, M. and Crespi Reghizzi, S. 2012. Parallel iterative compilation: Using MapReduce to speedup machine learning in compilers. In Proceedings of the 3rd International Workshop on MapReduce and its Applications (MAPREDUCE'12). Google ScholarDigital Library
- Thomson, J., O'Boyle, M. F. P., Fursin, G., and Franke, B. 2009. Reducing training time in a one-shot machine learning-based compiler. In Proceedings of the 22nd International Workshop on Languages and Compilers for Parallel Computing (LCPC'09). 399--407. Google ScholarDigital Library
Index Terms
- Continuous learning of compiler heuristics
Recommendations
Parallel iterative compilation: using MapReduce to speedup machine learning in compilers
MapReduce '12: Proceedings of third international workshop on MapReduce and its Applications DateResearch has proved that machine learning and iterative compilation techniques can be profitable when applied to compilers to improve the optimizations they perform on programs. Unfortunately, these techniques are hampered by the long training times ...
Machine-Learning-Based Self-Optimizing Compiler Heuristics✱
MPLR '22: Proceedings of the 19th International Conference on Managed Programming Languages and RuntimesCompiler optimizations are often based on hand-crafted heuristics to guide the optimization process. These heuristics are designed to benefit the average program and are otherwise static or only customized by profiling information. We propose machine-...
Improving Vectorization Heuristics in a Dynamic Compiler with Machine Learning Models
VMIL 2022: Proceedings of the 14th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate LanguagesOptimizing compilers rely on many hand-crafted heuristics to guide the optimization process. However, the interactions between different optimizations makes their design a difficult task. We propose using machine learning models to either replace such ...
Comments