臺灣博碩士論文加值系統

編譯器針對特定的程式以何種排列組合方式以及參數套用最佳化函數能得到最優秀的最佳化的效果一直以來都是一項難解的問題。
有許多研究以各種角度切入嘗試解決這個問題，例如關於最佳化的選擇、最佳化的順序以及參數的選擇，並使用了許多不同的演算法。
常見的方式是使用各式程式分析的方式觀測程式，並以機器學習的方式找尋這些特徵與編譯器最佳化之間的關係。
或者利用演化計算的方式搜尋近似最佳解。
然而隨著各式最佳化函數的數量逐漸攀升，關於此問題的搜索空間不斷膨脹。
因此近年隨著神經網路學習的研究發展，將程式碼作為輸入使神經網路協助發現特徵成為新的研究方向。
然而學習演算法需要龐大的學習資料，且製作學習資料十分費時，因此常以演化計算的方式輔助製作。
我們觀察到由演化演算法產生的序列經常能夠產生有用組合，但同時還包含了對於程式最佳化無效的最佳化函數。
若學習資料序列中皆含有大量的無效最佳化函數，將會成為學習資料中的雜訊影響學習的效率。
因此在先前的研究中提出了Reduced O3 subsequence labeling (RO3SL)問題以收集不含無效最佳化函數的序列作為合適的學習資料，並以一個基因演算法嘗試解決這個問題。
我們在此實驗的基礎之上提出了演算法的改進，使基因演算法產生的結果更適合作為學習資料。
實驗結果顯示在保持著同樣的無效最佳化比例之下，經過評估並刪除結果序列中的無效最佳化函數之後，平均長度由4.25個最佳化函數提升至6.75個最佳化函數。
另外經過改進的演算法減少了原先不斷削減長度的程度後，對於問題的探索能夠從探索短序列轉而增加對於相同長度周邊的探索性，尋找更多保持一定最佳化能力的簡化O3子序列。
我們認為經過改良的演算法更好的解決了RO3SL問題，所產生的結果序列作為預測最佳化函數序列的學習資料相較於先前的研究更加合適。

It has always been a tough challenge for compilers to select the best optimization for a particular program.
Many studies have attempted to solve this problem from various perspectives, including phase ordering, phase selection, and parameter
selection, and many methodologies have been used to solve the problem.
A common example is to analyze a program using some program analysis techniques and then use machine learning techniques to see how
these features relate to optimization options. It is also common to use evolutionary algorithms to find approximate optimal solutions.
However, there still remains the problem of large search space.
With the advent of deep learning techniques, using deep learning algorithms to extract features from program source code automatically
has become a new direction of research.
However, deep learning algorithms requires a large amount of training data, and generating the training data for such a problem could be
time-consuming. Moreover, we observed that optimization sequences generated by evolutionary algorithms usually contains useless passes,
and these useless passes are considered noises during the machine learning process.
A previous study has focused on this problem and proposed a reduced O3 subsequence labeling (RO3SL) problem to collect optimization
sequences that contain no useless pass and treat them as appropriate training data. A generic algorithm was used to solve the RO3SL
problem. In this thesis, we propose an improved generic algorithm to better solve the RO3SL problem. Experiments demonstrate that
our proposed algorithm increased the average length of generated optimization sequences from 4.25 to 6.75 while avoiding useless passes
to be involved in the generated sequences. In addition, the proposed algorithm also reduced the number of superfluous sequences being
generated, thereby exploring more reduced O3 subsequences.
We believe that the proposed algorithm better solve the RO3SL problem and the optimization sequences generated by the algorithm could be
a better set of training data for solving the optimization sequence prediction problem.

中文摘要 i
英文摘要 ii
目錄 iii
圖目錄 v
表目錄 vi
一、 研究介紹 1
1.1 研究介紹 1
1.2 研究動機 2
1.3 貢獻 3
1.4 總覽 3
二、 研究背景 4
2.1 先前的研究 4
2.1.1 介紹 4
2.1.2 RO3SL 5
2.1.3 交配與突變 7
2.2 SPEA2+ 7
2.2.1 環境選擇 7
2.2.2 檔案留存 10
三、 研究方法 11
3.1 SPEA2+ 演算法 11
3.1.1 目標向量與目標檔案 11
3.1.2 設計變數檔案 12
3.2 空序列 12
3.3 有效收斂 13
四、 實驗 16
4.1 評估方法 18
4.2 實驗結果 20
五、 文獻探討 25
六、 結論與未來展望 27
6.1 結論 27
6.2 未來展望 27
參考文獻 28

[1] A. H. Ashouri, W. Killian, J. Cavazos, G. Palermo, and C. Silvano, “A survey on
compiler autotuning using machine learning,” ACM Comput. Surv., vol. 51, no. 5, sep
2018. [Online]. Available: https://doi-org.ezproxy.lib.nctu.edu.tw/10.1145/3197978
[2] G. Fursin, Y. Kashnikov, A. W. Memon, Z. Chamski, O. Temam, M. Namolaru, E. YomTov, B. Mendelson, A. Zaks, E. Courtois, F. Bodin, P. Barnard, E. Ashton, E. Bonilla,
J. Thomson, C. K. I. Williams, and M. O’Boyle, “Milepost gcc: Machine learning enabled
self-tuning compiler,” International Journal of Parallel Programming, vol. 39, no. 3, pp.
296–327, Jun 2011. [Online]. Available: https://doi.org/10.1007/s10766-010-0161-2
[3] T. Ben-Nun, A. S. Jakobovits, and T. Hoefler, “Neural code comprehension: A learnable
representation of code semantics,” in Proceedings of the 32nd International Conference
on Neural Information Processing Systems, ser. NIPS’18. Red Hook, NY, USA: Curran
Associates Inc., 2018, p. 3589–3601.
[4] Y.-P. You and Y.-C. Su, “Reduced o3 subsequence labelling: a stepping stone towards
optimisation sequence prediction,” Connection Science, vol. 0, no. 0, pp. 1–18, 2022.
[Online]. Available: https://doi.org/10.1080/09540091.2022.2044761
[5] D. DeFreez, A. V. Thakur, and C. Rubio-González, “Path-based function embedding
and its application to error-handling specification mining,” in Proceedings of the 2018
26th ACM Joint Meeting on European Software Engineering Conference and Symposium
on the Foundations of Software Engineering, ser. ESEC/FSE 2018. New York, NY,
USA: Association for Computing Machinery, 2018, p. 423–433. [Online]. Available:
https://doi-org.ezproxy.lib.nctu.edu.tw/10.1145/3236024.3236059
[6] U. Alon, M. Zilberstein, O. Levy, and E. Yahav, “A general path-based representation for
predicting program properties,” in Proceedings of the 39th ACM SIGPLAN Conference
on Programming Language Design and Implementation, ser. PLDI 2018. New York, NY, USA: Association for Computing Machinery, 2018, p. 404–419. [Online]. Available:
https://doi-org.ezproxy.lib.nctu.edu.tw/10.1145/3192366.3192412
[7] U. Alon, M. Zilberstein, O. Levy, and E. Yahav, “Code2vec: Learning distributed
representations of code,” Proc. ACM Program. Lang., vol. 3, no. POPL, jan 2019.
[Online]. Available: https://doi.org/10.1145/3290353
[8] A. Brauckmann, A. Goens, S. Ertel, and J. Castrillon, “Compiler-based graph
representations for deep learning models of code,” in Proceedings of the 29th
International Conference on Compiler Construction, ser. CC 2020. New York, NY,
USA: Association for Computing Machinery, 2020, p. 201–211. [Online]. Available:
https://doi-org.ezproxy.lib.nctu.edu.tw/10.1145/3377555.3377894
[9] S. Dey, A. K. Singh, D. K. Prasad, and K. D. Mcdonald-Maier, “Socodecnn: Program
source code for visual cnn classification using computer vision methodology,” IEEE Access, vol. 7, pp. 157 158–157 172, 2019.
[10] C. Cummins, P. Petoumenos, Z. Wang, and H. Leather, “End-to-end deep learning of optimization heuristics,” in 2017 26th International Conference on Parallel Architectures and
Compilation Techniques (PACT), 2017, pp. 219–232.
[11] A. Haj-Ali, N. K. Ahmed, T. Willke, Y. S. Shao, K. Asanovic, and I. Stoica,
“Neurovectorizer: End-to-end vectorization with deep reinforcement learning,” in
Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and
Optimization, ser. CGO 2020. New York, NY, USA: Association for Computing
Machinery, 2020, p. 242–255. [Online]. Available: https://doi-org.ezproxy.lib.nctu.edu.
tw/10.1145/3368826.3377928
[12] M. Kim, T. Hiroyasu, M. Miki, and S. Watanabe, “SPEA2+: improving the performance
of the strength Pareto evolutionary algorithm 2,” in PPSN, 2004.
[13] S. VenkataKeerthy, R. Aggarwal, S. Jain, M. S. Desarkar, R. Upadrasta, and
Y. N. Srikant, “Ir2vec: Llvm ir based scalable program embeddings,” ACM Trans. Archit. Code Optim., vol. 17, no. 4, dec 2020. [Online]. Available: https:
//doi-org.ezproxy.lib.nctu.edu.tw/10.1145/3418463
[14] R. Mammadli, A. Jannesari, and F. A. Wolf, “Static neural compiler optimization via deep
reinforcement learning,” 2020 IEEE/ACM 6th Workshop on the LLVM Compiler Infrastructure in HPC (LLVM-HPC) and Workshop on Hierarchical Parallelism for Exascale
Computing (HiPar), pp. 1–11, 2020.
[15] E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm,” TIK-report, vol. 103, 2001.
[16] Y. Liu, H. Ishibuchi, G. G. Yen, Y. Nojima, and N. Masuyama, “Handling imbalance between convergence and diversity in the decision space in evolutionary multimodal multiobjective optimization,” IEEE Transactions on Evolutionary Computation, vol. 24, no. 3,
pp. 551–565, 2020.
[17] A. Hussain, Y. Muhammad, and M. Sajid, “An efficient genetic algorithm for numerical
function optimization with two new crossover operators,” International Journal of Mathematical Sciences and Computing, vol. 4, pp. 41–55, 2018.