臺灣博碩士論文加值系統

現代的編譯器通常提供大量的編譯最佳化選項，協助使用者微調程式發揮最大的效能。然而要妥善應用這些最佳化選項，必須具備編譯最佳化方面的知識，所以大多數的使用者並沒有足夠的能力使用這些最佳化選項。Iterative Compilation是目前常用於為一個程式搜尋最佳編譯選項組合的方法。在編譯最佳化方面有幾個令人感興趣的目標，如：執行時間、編譯時間、目的碼大小、記憶體用量、能源消耗及其他計算資源。本研究將目前廣為使用的多目標演化式演算法 NSGA-II和MOEA/D，針對執行時間以及目的碼大小進行迭代式編譯。實驗結果顯示，兩個演算法所選擇的最佳化組合皆優於隨機搜尋獲得的結果，也優於編譯器內建的最佳化等級。

Modern compilers usually provide a large number of optimization options to aid users to fine tune their programs for the best performance. However, applying such optimization options involves complex knowledge about compiler optimization, so most users do not have the capability to utilize these optimization options. Iterative Compilation is currently the most common approach to searching for the optimal set of optimization options for a program. There are several interesting performance metrics in compiler optimization: execution time, compilation time, code size, memory space, power consumption, and other computing resources. This research investigates multi-objective optimization of execution time and code size in Iterative Compilation using the popular multi-objective evolutionary algorithms NSGA-II and MOEA/D. The experimental results show that the optimization sequences chosen by both algorithms are superior to the ones generated by the random search algorithm and the ones corresponding to the optimization levels provided by the compiler.

第一章 概論 1
第二章 背景 3
2.1. GCC 架構 3
2.1.1. 前端 3
2.1.2. 中介端 4
2.1.3. 後端 4
2.1.4. GCC最佳化選項 4
2.1.5. 本研究考量的最佳化選項 7
2.2. 迭代式編譯 7
2.3. 小結 8
第三章 多目標最佳化 9
3.1. 基礎概念 9
3.1.1. 多目標最佳化問題 9
3.1.2. 支配 9
3.1.3. Pareto Optimality 10
3.2. 多目標最佳化之效能評估 11
3.2.1. Hypervolume 11
3.3. 演化式演算法 13
3.3.1. NSGA-II 14
3.3.2. MOEA/D 17
第四章 實驗設定 22
4.1. 系統架構 22
4.2. 搜尋演算法設定 23
4.2.1. 最佳化目標計算法 23
4.2.2. 隨機搜尋設定 23
4.2.3. 演化式演算法設定 24
4.3. 環境設定 24
第五章 實驗結果及分析 26
5.1. 隨機搜尋法 26
5.2. 更新群體方式對MOEA/D的影響 27
5.3. 演算法比較 28
5.3.1. Hypervolume 30
第六章 結論與未來展望 32
6.1. 結論 32
6.2. 未來展望 32
參考文獻 34

[1]T. Kisuki, P. M. W. Knijnenburg, M. F. P. O’Boyle, F. Bodin, and H. A. G. Wijshoff, “A Feasibility Study in Iterative Compilation,” in Proceedings of the Second International Symposium on High Performance Computing, 1999, pp. 121-132.
[2]K. D. Cooper et al., “Exploring the structure of the space of compilation sequences using randomized search algorithms,” The Journal of Supercomputing, vol. 36, no. 2, pp. 135-151, 2006.
[3]L. Almagor et al., “Finding effective compilation sequences,” in Proceedings of the 2004 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems, 2004, vol. 39, no. 7, pp. 231-239.
[4]T. Kisuki, P. M. W. Knijnenburg, M. F. P. O’Boyle, and H. A. G. Wijshoff, “Iterative Compilation in Program Optimization,” in Proceedings of Compilers for Parallel Computers, 2000, pp. 35-44.
[5]C. Dubach, T. M. Jones, E. V. Bonilla, G. Fursin, and M. F. P. O’Boyle, “Portable compiler optimisation across embedded programs and microarchitectures using machine learning,” in Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture, 2009, pp. 78-88.
[6]G. Fursin et al., “Milepost GCC: Machine Learning Enabled Self-tuning Compiler,” International Journal of Parallel Programming, vol. 39, no. 3, pp. 296-327, 2011.
[7]F. Agakov et al., “Using Machine Learning to Focus Iterative Optimization,” in Proceedings of the International Symposium on Code Generation and Optimization, 2006, pp. 295-305.
[8]K. Hoste and L. Eeckhout, “Cole: compiler optimization level exploration,” in Proceedings of the 6th annual IEEE/ACM international symposium on Code generation and optimization, 2008, pp. 165-174.
[9]K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002.
[10]Q. Zhang and H. Li, “MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 6, pp. 712-731, Dec. 2007.
[11]K. D. Cooper, P. J. Schielke, and D. Subramanian, “Optimizing for reduced code space using genetic algorithms,” in Proceedings of the ACM SIGPLAN 1999 workshop on Languages, compilers, and tools for embedded systems, 1999, pp. 1-9.
[12]K. D. Cooper et al., “ACME: adaptive compilation made efficient,” in Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, 2005, pp. 69-77.
[13]G. Bashkansky and Y. Yaari, “Black box approach for selecting optimization options using budget-limited genetic algorithms,” in Workshop on Statistical and Machine learning approaches to ARchitectures and compilaTion, 2007.
[14]E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. G. da Fonseca, “Performance assessment of multiobjective optimizers: an analysis and review,” IEEE Transactions Evolutionary Computation, vol. 7, no. 2, pp. 117-132, 2003.
[15]Q. Zhang, W. Liu, and H. Li, “The performance of a new version of MOEA/D on CEC09 unconstrained MOP test instances,” in IEEE Congress on Evolutionary Computation, 2009, pp. 203-208.
[16]H. Li and D. Landa-Silva, “An adaptive evolutionary multi-objective approach based on simulated annealing,” IEEE Transactions on Evolutionary Computation, vol. 19, no. 4, pp. 561-595, 2011.
[17]M. T. Yourst, “PTLsim: A Cycle Accurate Full System x86-64 Microarchitectural Simulator,” in International Symposium on Performance Analysis of Systems and Software, 2007, pp. 23-34.
[18]M. R. Guthaus, J. S. Ringenberg, D. Ernst, T. M. Austin, T. Mudge, and R. B. Brown, “MiBench: A free, commercially representative embedded benchmark suite,” in IEEE 4th Annual Workshop on Workload Characterization, 2001, pp. 3-14.
[19]Q. Zhang, W. Liu, E. P. K. Tsang, and B. Virginas, “Expensive Multiobjective Optimization by MOEA/D With Gaussian Process Model,” IEEE Transactions on Evolutionary Computation, vol. 14, no. 3, pp. 456-474, 2010.
[20]J. Knowles and H. Nakayama, “Meta-Modeling in Multiobjective Optimization,” in Multiobjective Optimization, J. Branke, K. Deb, K. Miettinen, and R. Slowi’nski, Eds. Berlin, Heidelberg: Springer-Verlag, 2008, pp. 245-284.
[21]L. V. Santana-Quintero, A. A. Montaño, and C. A. C. Coello, “A Review of Techniques for Handling Expensive Functions in Evolutionary Multi-Objective Optimization,” in Computational Intelligence in Expensive Optimization Problems, Y. Tenne and C.-K. Goh, Eds. Springer Berlin Heidelberg, 2010, pp. 29-59.