Statistical models to accelerate software development by means of iterative compilation

Agnieszka Kamińska; Włodzimierz Bielecki

doi:10.7494/csci.2016.17.3.407

Authors

Agnieszka Kamińska West Pomeranian University of Technology, Faculty of Computer Science and Information Technology, Szczecin
Włodzimierz Bielecki West Pomeranian University of Technology, Faculty of Computer Science and Information Technology, Szczecin

DOI:

https://doi.org/10.7494/csci.2016.17.3.407

Keywords:

program execution time, optimizing compilation, iterative compilation, statistical models, processor cache

Abstract

Minimization of data-processing time and reduction of software-development time are important practical problems to be tackled by modern computer science.
This paper presents the authors' proposal of a family of statistical models for the estimation of program execution time, which is an approach focused on both of the above problems at the same time. The family consists of a general model and specific models and has been elaborated based on empirical data collected for pattern-program loops representing some arbitrarily selected features related to the program structure and the specificity of a program-execution environment.
The paper presents steps to elaborate the aforementioned family as well as the results of the carried-out experimental research. The paper demonstrates how the elaborated models can be applied in iterative compilation for optimization purposes, allowing us to reduce the time of software development and produce code with minimal execution time.

Downloads

Download data is not yet available.

References

Aho A., Lam M., Sethi R., Ullman J.: Compilers: Principles, Techniques, and Tools. Addison Wesley, 2 ed., 2006.

Barthou D., Donadio S., Carribault P., Duchateau A., W. J.: Loop optimization using hierarchical compilation and kernel decomposition. In: Proceedings of the International Symposium on Code Generation and Optimization, pp. 170-184, 2007.

Barthou D., Donadio S., Duchateau A., Jalby W., Courtois E.: Iterative compilation with kernel exploration. In: Languages and Compilers for Parallel Computing, pp. 173-189, 2007.

Berlińska J.: Methods of creating statistical models characterizing parallel and distributed applications (in Polish). Politechnika Szczecińska, 2005.

Brandolese C., Fornaciari W., Salice F., Sciuto D.: Source-level execution time estimation of C programs. In: Proceedings of the ninth international symposium on Hardware/software codesign, pp. 98-103, 2001.

Coleman S., McKinley K.: Tile Size Selection Using Cache Organization and Data Layout. In: ACM SIGPLAN Notices, vol. 30, pp. 279-290, 1995.

Eiben A.E., Michalewicz Z., Schoenauer M., Smith J.E.: Parameter control in evolutionary algorithms. In: Parameter setting in evolutionary algorithms, pp. 19-46, 2007.

Esseghir K.: Improving data locality for caches. Rice University, 1993.

Fursin G.: Iterative Compilation and Performance Prediction for Numerical Applications. University of Edinburg, 2004.

Fursin G., O'Boyle M., Knijnenburg P.: Evaluating iterative compilation. In: Languages and Compilers for Parallel Computing, pp. 362-376, 2005.

Haoqiang J., Frumkin M., Yan J.: The OpenMP implementation of NAS parallel benchmarks and its performance. NASA Ames Research Center, 1999.

Ishizaka K., Obata M., Kasahara H.: Coarse grain task parallel processing with cache optimization on shared memory multiprocessor. In: Languages and Compilers for Parallel Computing, pp. 352-365, 2003.

Knijnenburg P., Kisuki T., O'Boyle M.: Iterative compilation. In: Embedded processor design challenges, pp. 171-187, 2002.

Lam M., Rothberg E., Wolf M.: The Cache Performance and Optimization of Blocked Algorithms. In: ACM SIGARCH Computer Architecture News, vol. 19, pp. 63-74, 1991.

Lokuciejewski P., Stolpe M., Morik K., Marwedel P.: Automatic Selection of Machine Learning Models for WCET-aware Compiler Heuristic Generation. In: Proceedings of the 4th Workshop on Statistical and Machine Learning Approaches to Architectures and Compilation (SMART), pp. 3-17, 2010.

NASA Advanced Supercomputing Division: NAS Parallel Benchmarks. http://www.nas.nasa.gov/publications/npb.html Accessed 28 July 2015.

OpenMP: The OpenMP API specification for parallel programming. http://www.openmp.org/. Accessed 28 July 2015.

Park E., Kulkarni S., Cavazos J.: An Evaluation of Different Modelling Techniques for Iterative Compilation. In: Proceedings of the 14th international conference on compilers, architectures and synthesis for embedded systems, pp. 65-74, 2011.

Temam O., Fricker C., Jalby W.: Cache interference phenomena. In: ACM SIGMETRICS Performance Evaluation Review, vol. 22, pp. 261-271, 1994.

Wolfe M.: High Performance Compilers for Parallel Computing. Addison-Wesley, 1996.