It’s finished! After almost 2 years of research and months of writing, I finally submitted my Master of Engineering thesis to the department. In this post, I would like to thank the many people who have made my past 5 years at MIT such an extraordinary experience: Joel Moses for being a great academic advisor, Una-May O’Reilly for her endless enthusiasm and invaluable advice as my thesis supervisor, the many amazing professors in my classes, and finally my friends and family. Thank you all!
My finished thesis, titled “Evolutionary Algorithms for Compiler-Enabled Program Autotuning”, is available here:
PetaBricks is an implicitly parallel programming language which, through the process of autotuning, can automatically optimize programs for fast QoS-aware execution on any hardware. In this thesis we develop and evaluate two PetaBricks autotuners: INCREA and SiblingRivalry. INCREA, based on a novel bottom-up evolutionary algorithm, optimizes programs offline at compile time. SiblingRivalry improves on INCREA by optimizing online during a program’s execution, dynamically adapting to changes in hardware and the operating system. Continuous adaptation is achieved through racing, where half of available resources are devoted to always-on learning. We evaluate INCREA and SiblingRivalry on a large number of real-world benchmarks, and show that our autotuners can significantly speed up PetaBricks programs with respect to many non-tuned and mis-tuned baselines. Our results indicate the need for a continuous learning loop that can optimize efficiently by exploiting online knowledge of a program’s performance. The results leave open the question of how to solve the online optimization problem on all cores, i.e. without racing.