以人工智慧揀選函式層級最佳化演算法之編譯器框架

ABC: An AI-Boosted Compiler Framework for Selecting Function-Level Optimizations

張家榮(Jia-Rung Chang)

指導教授 ： 游逸平

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2018年)

摘要

揀選編譯器最佳化組合除了是一件非常實務的經驗，更需要系統性與統計性的分析。過去的研究已經證明了，若是能夠針對每個編譯模組施加更適當的最佳化組合，能夠得到良好的效能改善。本篇論文提出了稱為ABC 的框架，將編譯粒度從模組提高至函數，並提出一個藉由考量最佳化演算法語意控制流的全新程式特徵提取方式，搭配強化學習框架，以預測程式內每一個函數的最佳化演算法組合及順序。有了ABC，我們將能標準化的訓練預測模型的流程，藉此提升執行效能。實驗顯示，ABC 框架，對於用以訓練程式，能使大約73% 的程式效能優於“-O3”，整體而言，得到了比“-O3”提升幾何平均1.9% 的執行效能；對於未曾訓練的程式，能使大約64% 的程式效能更勝於“-O3”，整體而言，得到了比“-O3” 提升幾何平均1.5%的執行效能；然而不可避免的會有編譯時期的時間成本，相較於“-O3”的編譯時間，平均帶來了7.4 倍至91.0 倍的編譯時間，但我們依然認為這是可以被普遍接受的成本。

關鍵字

強化學習 ； 函式層級最佳化 ； 編譯器最佳化組合 ； 程式特徵擷取

並列摘要

Selecting the best compiler optimization algorithms for a given program needs not only empirical experiences but also statistical and systematic approaches for the problem. Lots of researches have shown that individually selecting proper combinations of optimization algorithms for each compilation module of a program can boost its performance. In this paper, we propose an optimization selection framework, called ABC, that raises the granularity of optimization selection from module-level to function-level. ABC provides a new perspective for feature extraction from the programs to optimize by considering the control-flow semantics of compiler optimization algorithms, and adopts reinforcement learning techniques to select a good combination of optimization algorithms with considering the order for each function of a given program. With the ABC framework, we are able to standardize the process of training different one-shot prediction models for different processors. Experiments demonstrated that the proposed ABC framework improved the execution performance. For the training programs, ABC made over 73% of the programs get speedup, and all the programs got a geometric average improvement of 1.9% compared to “-O3”. For the unseen programs, ABC made over 64% of the programs get speedup, and all the programs got a geometric average improvement of 1.5% compared to “-O3”. However, the compilations were inevitably slowed down by 7.4x–91.0x, compared with the results when using the optimization level of “-O3”, which is considered aggressive and commonly used.

並列關鍵字

Reinforcement Learning ； Function-Level Optimization ； Compiler Optimization Selection ； Extracting Code Features

參考文獻

[1] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur, J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner, P. Tucker, V. Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng, “Tensorflow: A system for large-scale machine learning,” in Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation, ser. OSDI ’16. Berkeley, CA, USA: USENIX Association, 2016, pp. 265–283. [Online]. Available: http://dl.acm.org/citation.cfm?id=3026877.3026899

[2] F. Agakov, E. Bonilla, J. Cavazos, B. Franke, G. Fursin, M. F. P. O’Boyle, J. Thomson, M. Toussaint, and C. K. I. Williams, “Using machine learning to focus iterative optimization,” in Proceedings of the International Symposium on Code Generation and Optimization, ser. CGO ’06. Washington, DC, USA: IEEE Computer Society, 2006, pp. 295–305. [Online]. Available: http://dx.doi.org/10.1109/CGO.2006.37

[3] J. Ansel, S. Kamil, K. Veeramachaneni, J. Ragan-Kelley, J. Bosboom, U.-M. O’Reilly, and S. Amarasinghe, “Opentuner: An extensible framework for program autotuning,” in Proceedings of the 23rd International Conference on Parallel Architectures and Compilation, ser. PACT ’14. New York, NY, USA: ACM, 2014, pp. 303–316. [Online]. Available: http://doi.acm.org/10.1145/2628071.2628092

[4] L. C. Baird, “Reinforcement learning in continuous time: advantage updating,” in Neural Networks, 1994. IEEE World Congress on Computational Intelligence., 1994 IEEE International Conference on, vol. 4, Jun 1994, pp. 2448–2453 vol.4.

[5] G. Bashkansky and Y. Yaari, “Black box approach for selecting optimization options using budget-limited genetic algorithms,” 2007.