计算机科学技术学报 ›› 2018,Vol. 33 ›› Issue (5): 940-965.doi: 10.1007/s11390-018-1867-7

• Computer Architecture and Systems • 上一篇    下一篇

另一种智能代码生成系统:一种灵活低成本解决方案

João Fabrício Filho1,2, Luis Gustavo Araujo Rodriguez1, Anderson Faustino da Silva1   

  1. 1 Department of Informatics, State University of Maringá, Maringá-PR 87020-900, Brazil;
    2 Federal University of Technology-Paraná, Campo Mourão-PR 87301-899, Brazil
  • 收稿日期:2017-05-27 修回日期:2018-05-10 出版日期:2018-09-17 发布日期:2018-09-17
  • 作者简介:João Fabrício Filho is currently an IT analyst of Federal University of Technology-Paraná, Campo Mourão-PR, and a Ph.D. student in computer science at the University of Campinas, Campinas. He received his Bachelor's degree in informatics and Master's degree in computer science from State University of Maringá, Maringá-PR, in 2014 and 2016, respectively. His research interests include high performance computing, approximate computing, parallel programming and compilers.

Yet Another Intelligent Code-Generating System: A Flexible and Low-Cost Solution

João Fabrício Filho1,2, Luis Gustavo Araujo Rodriguez1, Anderson Faustino da Silva1   

  1. 1 Department of Informatics, State University of Maringá, Maringá-PR 87020-900, Brazil;
    2 Federal University of Technology-Paraná, Campo Mourão-PR 87301-899, Brazil
  • Received:2017-05-27 Revised:2018-05-10 Online:2018-09-17 Published:2018-09-17

现代编译器采用多种代码转换算法提升目标代码的质量。然而,一个复杂问题是如何决定必须使用哪些转换算法。它的复杂性在于三个方面:大量的转换算法,多种组合可能性,和一些配置可能性。近年来,相关文献已经陈述了多种智能系统。其目的是检索转换算法并将他们应用到某一特定项目。本文提出了一种灵活,低成本,智能的系统,通过考虑项目的特定特征,它可以为某个输入项目识别转换算法。该系统参数化选择灵活和计算成本低廉。此外,它可以最大化可用计算资源的挖掘。该系统应用于低能级虚拟机器设备。结果表明较其他系统而言,它的性能可以提升21.36%。此外,相对于低能级虚拟机器设备中最激进编译器优化等级,其平均改善率到达了17.72%。

关键词: 编译器, 代码转换, 迭代编译, 知识表征, 机器学习

Abstract: Modern compilers apply various code transformation algorithms to improve the quality of the target code. However, a complex problem is to determine which transformation algorithms must be utilized. This is difficult because of three reasons:a number of transformation algorithms, various combination possibilities, and several configuration possibilities. Over the last few years, various intelligent systems were presented in the literature. The goal of these systems is to search for transformation algorithms and thus apply them to a certain program. This paper proposes a flexible, low-cost and intelligent system capable of identifying transformation algorithms for an input program, considering the program's specific features. This system is flexible for parameterization selection and has a low-computational cost. In addition, it has the capability to maximize the exploration of available computational resources. The system was implemented under the Low Level Virtual Machine infrastructure and the results indicate that it is capable of exceeding, up to 21.36%, performance reached by other systems. In addition, it achieved an average improvement of up to 17.72% over the most aggressive compiler optimization level of the Low Level Virtual Machine infrastructure.

Key words: compiler, code transformation, iterative compilation, knowledge representation, machine learning

[1] Ula M, Mursyidah, Hendriana Y, Hardi R. An expert system for early diagnose of vitamins and minerals deficiency on the body. In Proc. the International Conference on Information Technology Systems and Innovation, Oct. 2016.
[2] Muntean M V, Donea A. A hybrid intelligent agent based expert system for GPS databases. In Proc. the 8th International Conference on Electronics, Computers and Artificial Intelligence, June 30-July 2, 2016.
[3] Nascimento R J O, Fonseca C A G, Medeiros Neto F D. Using expert systems for investigating the impact of architectural anomalies on software reuse. IEEE Latin America Transactions, 2017, 15(2):374-379.
[4] Tartara M, Reghizzi S C. Continuous learning of compiler heuristics. ACM Transactions on Architecture and Code Optimization, 2013, 9(4):46:1-46:25.
[5] Aho A V, Sethi R, Ullman J D. Compilers:Principles, Techniques and Tools. Prentice Hall, 2006.
[6] Cooper K, Torczon L. Engineering a Compiler (2nd edition). Morgan Kaufmann, USA, 2011.
[7] Muchnick S S. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1997.
[8] Pan Z, Eigenmann R. Fast and effective orchestration of compiler optimizations for automatic performance tuning. In Proc. the International Symposium on Code Generation and Optimization, March 2006, pp.319-332.
[9] Park E, Kulkarni S, Cavazos J. An evaluation of different modeling techniques for iterative compilation. In Proc. the 14th International Conference on Compilers, Architectures and Synthesis for Embedded Systems, Oct. 2011, pp.65-74.
[10] Purini S, Jain L. Finding good optimization sequences covering program space. ACM Transactions on Architecture and Code Optimization, 2013, 9(4):56:1-56:23.
[11] Cavazos J, Fursin G, Agakov F, Bonilla E, O'Boyle M F P, Temam O. Rapidly selecting good compiler optimizations using performance counters. In Proc. the International Symposium on Code Generation and Optimization, March 2007, pp.185-197.
[12] Lima E D, Souza Xavier T C, Silva A F, Ruiz L B. Compiling for performance and power efficiency. In Proc. the 23rd International Workshop on Power and Timing Modeling, Optimization and Simulation., Sept. 2013, pp.142-149.
[13] Queiroz Junior N L, Silva A F. Finding good compiler optimization sets-A case-based reasoning approach. In Proc. the 17th International Conference on Enterprise Information Systems, Apr. 2015, pp.504-515.
[14] Lattner C, Adve V. LLVM:A compilation framework for lifelong program analysis & transformation. In Proc. the International Symposium on Code Generation and Optimization, Mar. 2004, pp.75-86.
[15] Martins L G A, Nobre R, Cardoso J M P, Delbem A C B, Marques E. Clustering-based selection for the exploration of compiler optimization sequences. ACM Transactions on Architecture and Code Optimization, 2016, 13(1):8:1-8:28.
[16] Namolaru M, Cohen A, Fursin G, Zaks A, Freund A. Practical aggregation of semantical program properties for machine learning based optimization. In Proc. the International Conference on Compilers Architectures and Synthesis for Embedded Systems, Oct. 2010, pp.197-206.
[17] Sanches A, Cardoso J M P. On identifying patterns in code repositories to assist the generation of hardware templates. In Proc. the International Conference on Field Programmable Logic and Applications, Aug.31-Sept.21, 2010, pp.267-270.
[18] Wu Y, Larus J R. Static branch frequency and program profile analysis. In Proc. the International Symposium on Microarchitecture, Nov.30-Dec.2, 1994.
[19] Ball T, Larus J R. Branch prediction for free. ACM SIGPLAN Notices, 1993, 28(6):300-313.
[20] Shafer G. A Mathematical Theory of Evidence. Princeton University Press, 1976.
[21] Scholkopf B, Smola A J. Learning with Kernels-Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, San Francisco, CA, USA, 2002.
[22] Needleman S B, Wunsch C D. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 1970, 48(3):443-453.
[23] Tanenbaum A S, Goodman J R. Structured Computer Organization. Prentice Hall PTR, Upper Saddle River, NJ, USA, 1998.
[24] Patterson D A, Hennessy J L. Computer Organization and Design:The Hardware/Software Interface (5th edition). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2013.
[25] Chen Y, Fang S, Eeckhout L, Temam O, Wu C. Iterative optimization for the data center. ACM SIGPLAN Notices, 2012, 47(4):49-60.
[26] Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, Blondel M, Prettenhofer P, Weiss R, Dubourg V, VanderPlas J, Passos A, Cournapeau D, Brucher M, Perrot M, Duchesnay E. Scikit-learn:Machine learning in Python. Journal of Machine Learning Research, 2011, 12:2825-2830.
[27] Kulkarni P A, Whalley D B, Tyson G S, Davidson J W. Practical exhaustive optimization phase order exploration and evaluation. ACM Transactions on Architecture and Code Optimization, 2009, 6(1):1-36.
[28] Foleiss J H, Silva A F, Ruiz L B. An experimental evaluation of compiler optimizations on code size. In Proc. the 15th Brazilian Symposium on Programming Languages, Sept. 2011.
[29] Haneda M, Knijnenburg P M W, Wijshoff H A G. Generating new general compiler optimization settings. In Proc. the Annual International Conference on Supercomputing, June 2005, pp.161-168.
[30] Long S, Fursin G. A heuristic search algorithm based on unified transformation framework. In Proc. the International Conference Workshops on Parallel Processing, June 2005, pp.137-144.
[31] Cooper K D, Grosul A, Harvey T J, Reeves S, Subramanian D, Torczon L, Waterman T. Exploring the structure of the space of compilation sequences using randomized search algorithms. Journal of Supercomputing, 2006, 36(2):135-151.
[32] Kulkarni P A, Hines S R, Whalley D B, Hiser J D, Davidson J W, Jones D L. Fast and efficient searches for effective optimization-phase sequences. ACM Transactions on Architecture and Code Optimization, 2005, 2(2):165-198.
[33] Che Y, Wang Z. A lightweight iterative compilation approach for optimization parameter selection. In Proc. the 1st International Multi-Symposiums on Computer and Computational Sciences, Volume 1, June 2006, pp.318-325.
[34] Zhou Y Q, Lin N W. A study on optimizing execution time and code size in iterative compilation. In Proc. the International Conference on Innovations in Bio-Inspired Computing and Applications, Sept. 2012, pp.104-109.
[35] Cohen A, Sigler M, Girbal S, Temam O, Parello D, Vasilache N. Facilitating the search for compositions of program transformations. In Proc. the 19th International Conference on Supercomputing, June 2005, pp.151-160.
[36] Pouchet L N, Bastoul C, Cohen A, Vasilache N. Iterative optimization in the polyhedral model:Part I, one-dimensional time. In Proc. the International Symposium on Code Generation and Optimization, March 2007, pp.144-156.
[37] Pouchet L N, Bastoul C, Cohen A, Cavazos J. Iterative optimization in the polyhedral mode:Part Ⅱ, multidimensional time. In Proc. the ACM SIGPLAN Conference on Programming Language Design and Implementation, June 2008, pp.90-100.
[38] Cui H, Xue J,Wang L, Yang Y, Feng X, Fan D. Extendable pattern-oriented optimization directives. ACM Transaction on Architecture and Code Optimization, Sept. 2012, 9(3):Article No. 14.
[39] Long S, O'Boyle M. Adaptive Java optimisation using instance-based learning. In Proc. the 18th International Conference on Supercomputing, June 26-July 1, 2004, pp.237-246.
[40] Agakov F, Bonilla E, Cavazos J, Franke B, Fursin G, O'Boyle M F P, Thomson J, Toussaint M, Williams C K I. Using machine learning to focus iterative optimization. In Proc. the International Symposium on Code Generation and Optimization, March 2006, pp.295-305.
[41] Park E, Cavazos J, Alvarez M A. Using graph-based program characterization for predictive modeling. In Proc. the International Symposium on Code Generation and Optimization, March 2012, pp.196-206.
[42] Martins L G, Nobre R, Delbem A C, Marques E, Cardoso J M P. Exploration of compiler optimization sequences using clustering-based selection. ACM SIGPLAN Notices, 2014, 49(5):63-72.
[1] Geun Yong Kim, Joon-Young Paik, Yeongcheol Kim, and Eun-Sun Cho. 基于字节频率特征码的勒索病毒检测方法[J]. 计算机科学技术学报, 2022, 37(2): 423-442.
[2] 赵建喆, 王兴伟, 毛克明, 黄辰希, 苏昱恺, 李宇宸. 机器学习中基于相关差分隐私保护的多方数据发布方法[J]. 计算机科学技术学报, 2022, 37(1): 231-251.
[3] Yi Zhong, Jian-Hua Feng, Xiao-Xin Cui, Xiao-Le Cui. 机器学习辅助的抗逻辑块加密密钥猜测攻击范式[J]. 计算机科学技术学报, 2021, 36(5): 1102-1117.
[4] Sara Elmidaoui, Laila Cheikhi, Ali Idri, Alain Abran. 用于软件可维护性预测的机器学习技术:精度分析[J]. 计算机科学技术学报, 2020, 35(5): 1147-1174.
[5] Andrea Caroppo, Alessandro Leone, Pietro Siciliano. 用于老年人面部表情识别的深度学习模型和传统机器学习方法的对比研究[J]. 计算机科学技术学报, 2020, 35(5): 1127-1146.
[6] Shu-Zheng Zhang, Zhen-Yu Zhao, Chao-Chao Feng, Lei Wang. 基于的特征选择的用于加速芯片物理设计Floorplan的机器学习框架[J]. 计算机科学技术学报, 2020, 35(2): 468-474.
[7] Rui Ren, Jiechao Cheng, Xi-Wen He, Lei Wang, Jian-Feng Zhan, Wan-Ling Gao, Chun-Jie Luo. HybridTune:基于时空数据关联的大数据系统性能诊断[J]. 计算机科学技术学报, 2019, 34(6): 1167-1184.
[8] Lan Yao, Feng Zeng, Dong-Hui Li, Zhi-Gang Chen. 基于Lp正则化的稀疏支持向量机特征选择算法[J]. , 2017, 32(1): 68-77.
[9] 包新启, 吴云芳. 面向问题检索的层级自训练张量神经网络模型[J]. , 2016, 31(6): 1151-1160.
[10] Najam Nazar, Yan Hu, He Jiang. 软件工件摘要方法综述[J]. , 2016, 31(5): 883-909.
[11] Xi-Jin Zhang, Yi-Fan Lu, Song-Hai Zhang. 用于食品识别和分析的深度卷积神经网络多任务学习[J]. , 2016, 31(3): 489-500.
[12] Jing Li, Lei Liu, Yuan Wu, Xiang-Hua Liu, Yi Gao, Xiao-Bing Feng, Cheng-Yong Wu. 基于制导的GPU共享内存相关优化[J]. , 2016, 31(2): 235-252.
[13] Lixue Xia, Peng Gu, Boxun Li, Tianqi Tang, Xiling Yin, Wenqin Huangfu, Shimeng Yu, Yu Cao, Yu Wang, Huazhong Yang. 忆阻器阵列矩阵向量乘的设计空间优化[J]. , 2016, 31(1): 3-19.
[14] Yi Yang, Chao Li, Huiyang Zhou. CUDA-NP:在GPGPGUs平台上实现嵌套的线程级别并行化[J]. , 2015, 30(1): 3-19.
[15] Jun-Fa Liu, Wen-Jing He, Tao Chen, and Yi-Qiang Chen. 由流形约束实现人脸知识迁移的三维卡通重建方法[J]. , 2013, 28(3): 479-489.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 周权; 魏道政;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[2] 沈一栋;. A General Scheme for Formalizing Defaults Usingthe Predicate ab(I,S)[J]. , 1999, 14(2): 159 -164 .
[3] . 半封闭数据立方体:一种有效平衡数据立方体体积和查询响应时间的实现方法[J]. , 2005, 20(3): 367 -372 .
[4] . 基于边缘纹理驱动模型的贝叶斯人脸定位[J]. , 2005, 20(6): 849 -854 .
[5] . 暂缺[J]. , 2006, 21(1): 19 -26 .
[6] . AVS-M:从标准到应用[J]. , 2006, 21(3): 332 -344 .
[7] . KASUM算法的更高水平的硬件综合实现方法[J]. , 2007, 22(1): 60 -70 .
[8] . 暂缺[J]. , 2008, 23(4 ): 516 -537 .
[9] . 缩略语预测:基于支持向量回归的统计学习方法[J]. , 2008, 23(4 ): 602 -611 .
[10] 彭三城, 贾维嘉, 王国军. 大规模移动自组网抗毁性评估[J]. , 2009, 24(4): 761 -774 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn
总访问量: