Finding the Best Compiler Optimization Option Set Rapidly via Machine Learning

現代的編譯器，大部分都提供了為數不少的優化選項。在適宜的搭配下，這些選項對於提高程式的執行效能，有著相當程度的助益。但是，如果與程式之間的搭配出了問題，也會產生反效果，對程式的效能造成傷害。因此，該如何正確的使用這些選項便成了相當重要的課題。為了做出正確的選擇，必須對個別優化選項有相當程度的了解，同時，得一併考慮選項之間有可能的交互影響。再來，也得對將進行優化的程式所持有之特性有深刻的認知。在綜合各種因素之後，才有可能做出最適切的選擇。但這動作具有相當的門檻。對大部分的使用者來說，並不是一件容易的事。尤其當選項有相當的數目時，對這工作的複雜度來說，更是爆炸性的增加。有許多的研究專注在如何有系統的挑選優化選項，並將這複雜度降低到人們可以接受的範圍。但複雜度降低在某些情況並不等同於所需時間可被接受。因此，本文利用了機器學習的技巧，將經驗轉化而建立起一模型。透過此模型，將能幫助使用者找出與程式相對應的編譯器優化選項，並大幅縮短整各尋找過程所需要的時間。For a compiler to find a set of options that result in an optimal program execution is a NP-hard problem, especially when there are a lot of options to choose. For a large program, finding the optimal set of compiler options can take an enormous amount of time. Thus, methods have been proposed to shorten the searching time by reducing the complexity of the problem. This thesis proposes a different approach to solve the problem via machine learning techniques. The goal of this approach is to give an acceptable answer in a short time. Using our approach we achieve a 5% improvement over the -O3 of GCC on a storage system and 7% on the MediaBench II. Moreover, the time our approach costs to get acceptable answer is only 1/100 of the time that CE Algorithm takes on a storage system.誌謝 i 摘要 ii Abstract iii Table of Contents iv Table of Figures v List of Tables vi List of Tables vi Chapter 1 Introduction 1 1.1 The Problem Description 3 1.2 Overview of Related Work 3 1.3 Motivation of Our Work 5 Chapter 2 Overview of Our Approach 7 2.1 Basics of Machine Learning 7 2.2 Overview of CDModel 9 2.3 A Simple Example 13 Chapter 3 The Decision Function in the CDModel 17 3.1 Solve Classification Problem Based on Logistic Regression 17 3.2 Logistic Regression 18 3.3 Maximum Likelihood 29 3.4 Leave-One-Out Cross Validation 32 Chapter 4 Experimental Results 34 4.1 Experimental Setup 34 4.2 Target Applications 35 4.3 Results 36 Chapter 5 Conclusion and Future Work 39 Bibliography 4