Journal of Computer Science and Technology ›› 2018, Vol. 33 ›› Issue (5): 940-965.doi: 10.1007/s11390-018-1867-7

• Computer Architecture and Systems • Previous Articles     Next Articles

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

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. Byte Frequency Based Indicators for Crypto-Ransomware Detection from Empirical Analysis [J]. Journal of Computer Science and Technology, 2022, 37(2): 423-442.
[2] Jian-Zhe Zhao, Xing-Wei Wang, Ke-Ming Mao, Chen-Xi Huang, Yu-Kai Su, and Yu-Chen Li. Correlated Differential Privacy of Multiparty Data Release in Machine Learning [J]. Journal of Computer Science and Technology, 2022, 37(1): 231-251.
[3] Yi Zhong, Jian-Hua Feng, Xiao-Xin Cui, Xiao-Le Cui. Machine Learning Aided Key-Guessing Attack Paradigm Against Logic Block Encryption [J]. Journal of Computer Science and Technology, 2021, 36(5): 1102-1117.
[4] Jian-Wei Cui, Wei Lu, Xin Zhao, Xiao-Yong Du. Efficient Model Store and Reuse in an OLML Database System [J]. Journal of Computer Science and Technology, 2021, 36(4): 792-805.
[5] Sara Elmidaoui, Laila Cheikhi, Ali Idri, Alain Abran. Machine Learning Techniques for Software Maintainability Prediction: Accuracy Analysis [J]. Journal of Computer Science and Technology, 2020, 35(5): 1147-1174.
[6] Andrea Caroppo, Alessandro Leone, Pietro Siciliano. Comparison Between Deep Learning Models and Traditional Machine Learning Approaches for Facial Expression Recognition in Ageing Adults [J]. Journal of Computer Science and Technology, 2020, 35(5): 1127-1146.
[7] Shu-Zheng Zhang, Zhen-Yu Zhao, Chao-Chao Feng, Lei Wang. A Machine Learning Framework with Feature Selection for Floorplan Acceleration in IC Physical Design [J]. Journal of Computer Science and Technology, 2020, 35(2): 468-474.
[8] Rui Ren, Jiechao Cheng, Xi-Wen He, Lei Wang, Jian-Feng Zhan, Wan-Ling Gao, Chun-Jie Luo. HybridTune: Spatio-Temporal Performance Data Correlation for Performance Diagnosis of Big Data Systems [J]. Journal of Computer Science and Technology, 2019, 34(6): 1167-1184.
[9] Lan Yao, Feng Zeng, Dong-Hui Li, Zhi-Gang Chen. Sparse Support Vector Machine with Lp Penalty for Feature Selection [J]. , 2017, 32(1): 68-77.
[10] Xin-Qi Bao, Yun-Fang Wu. A Tensor Neural Network with Layerwise Pretraining: Towards Effective Answer Retrieval [J]. , 2016, 31(6): 1151-1160.
[11] Najam Nazar, Yan Hu, He Jiang. Summarizing Software Artifacts: A Literature Review [J]. , 2016, 31(5): 883-909.
[12] Xi-Jin Zhang, Yi-Fan Lu, Song-Hai Zhang. Multi-Task Learning for Food Identification and Analysis with Deep Convolutional Neural Networks [J]. , 2016, 31(3): 489-500.
[13] Lixue Xia, Peng Gu, Boxun Li, Tianqi Tang, Xiling Yin, Wenqin Huangfu, Shimeng Yu, Yu Cao, Yu Wang, Huazhong Yang. Technological Exploration of RRAM Crossbar Array for Matrix-Vector Multiplication [J]. , 2016, 31(1): 3-19.
[14] Yi Yang, Chao Li, Huiyang Zhou. CUDA-NP: Realizing Nested Thread-Level Parallelism in GPGPU Applications [J]. , 2015, 30(1): 3-19.
[15] Liang-Jun Zang, Cong Cao, Ya-Nan Cao, Yu-Ming Wu, and Cun-Gen Cao. A Survey of Commonsense Knowledge Acquisition [J]. , 2013, 28(4): 689-719.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Zhou Quan; Wei Daozheng;. A Complete Critical Path Algorithm for Test Generation of Combinational Circuits[J]. , 1991, 6(1): 74 -82 .
[2] SHEN Yidong;. A General Scheme for Formalizing Defaults Usingthe Predicate ab(I,S)[J]. , 1999, 14(2): 159 -164 .
[3] Sheng-En Li and Shan Wang. Semi-Closed Cube: An Effective Approach to Trading Off Data Cube Size and Query Response Time[J]. , 2005, 20(3): 367 -372 .
[4] Hua Li, Shui-Cheng Yan, and Li-Zhong Peng[1]. Robust Non-Frontal Face Alignment with Edge Based Texture[J]. , 2005, 20(6): 849 -854 .
[5] Katerina Asdre and Stavros D. Nikolopoulos. P-Tree Structures and Event Horizon: Efficient Event-Set Implementations[J]. , 2006, 21(1): 19 -26 .
[6] Ye-Kui Wang. AVS-M: From Standards to Applications[J]. , 2006, 21(3): 332 -344 .
[7] Issam W. Damaj. Higher-Level Hardware Synthesis of the KASUMI Algorithm[J]. , 2007, 22(1): 60 -70 .
[8] Byron Choi, Gao Cong, Wenfei Fan, and Stratis D. Viglas. Updating Recursive XML Views of Relations[J]. , 2008, 23(4 ): 516 -537 .
[9] Xu Sun, Hou-Feng Wang, and Bo Wang. Predicting Chinese Abbreviations from Definitions: An Empirical Learning Approach Using Support Vector Regression[J]. , 2008, 23(4 ): 602 -611 .
[10] San-Cheng Peng, Student Member, CCF, Wei-Jia Jia, Member, ACM, Senior Member, IEEE, and Guo-Jun Wang, Senior Member, CCF. Survivability Evaluation in Large-Scale Mobile Ad-Hoc Networks[J]. , 2009, 24(4): 761 -774 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved