Dynamic tiling optimization for Polly compiler

• Autorzy: Adamski D. , Szydłowski M. , Jabłoński G. , Lasoń J.
• Języki publikacji: EN

Abstrakty

EN

This article presents dynamic tiling optimization for Polly compiler. It describes heuristic technique which can be applied to increase efficiency of tiling optimization. Proposed solution is based on open-source tools (LLVM and Polly compiler) and it proves that dynamic tiling optimization can be achieved by extraction code of tiled loop into seperate function. The compiler can generate multiple versions of the optimzed functions. Each of them is optimized by different tile size. The runtime decides during program’s execution which optimized version of the given function is the most appropriate.

Słowa kluczowe

EN

tiling optimization; compiler optimization; Polly compiler; LLVM

PL

optymalizacja kafelkowa; optymalizacja kompilatora; kompilator Polly; LLVM

• Wydawca: Lodz University of Technology. Department of Microelectronics and Computer Science
• Czasopismo: International Journal of Microelectronics and Computer Science
• Rocznik: 2017
• Tom: Vol. 8, nr 4
• Strony: 150--154
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Adamski D.

• Department of Microelectronics and Computer Computer Science, Lodz University of Technology, Poland, Wólczańska 221/223, 90-924 Lodz, Poland

autor

Szydłowski M.

• Department of Microelectronics and Computer Computer Science, Lodz University of Technology, Poland, Wólczańska 221/223, 90-924 Lodz, Poland

autor

Jabłoński G.

• Department of Microelectronics and Computer Computer Science, Lodz University of Technology, Poland, Wólczańska 221/223, 90-924 Lodz, Poland

autor

Lasoń J.

• Department of Microelectronics and Computer Computer Science, Lodz University of Technology, Poland, Wólczańska 221/223, 90-924 Lodz, Poland

Bibliografia

• [1] C. Carvahlo, “The gap between processor and memory speeds,” in Proceedings of the 3rd Internal Conference on Computer Architecture (ICCA’02). Department of Informatics, Minho University, 2002, pp. 27–34.
• [2] J. L. Hennessy and D. A. Patterson, Computer Architecture, Fifth Edition: A Quantative Approach, 5th ed. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2011.
• [3] Y. N. Srikant and P. Shankar, Eds., The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition. CRC Press, 2007.
• [4] M. Wolfe, “More iteration space tiling,” in Proceedings of the 1989 ACM/IEEE Conference on Supercomputing, ser. Supercomputing ’89. New York, NY, USA: ACM, 1989, pp. 655–664. [Online]. Available: http://doi.acm.org/10.1145/76263.76337.
• [5] A. LaMarca and R. E. Ladner, “The influence of caches on the performance of sorting,” J. Algorithms, vol. 31, no. 1, pp. 66–104, Apr. 1999. [Online]. Available: http://dx.doi.org/10.1006/jagm.1998.0985.
• [6] J. Shirako, K. Sharma, N. Fauzia, L.-N. Pouchet, J. Ramanujam, P. Sadayappan, and V. Sarkar, “Analytical bounds for optimal tile size selection,” in ETAPS International Conference on Compiler Construction (CC’12). Tallinn, Estonia: Springer Verlag, Mar. 2012.
• [7] M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, “Cacheoblivious algorithms,” in Proceedings of the 40th Annual Symposium on Foundations of Computer Science, ser. FOCS ’99. Washington, DC, USA: IEEE Computer Society, 1999, pp. 285–. [Online]. Available: http://dl.acm.org/citation.cfm?id=795665.796479.
• [8] A. M. Malik, “Optimal tile size selection problem using machine learning,” in Proceedings of the 2012 11th International Conference on Machine Learning and Applications - Volume 02, ser. ICMLA ’12. Washington, DC, USA: IEEE Computer Society, 2012, pp. 275–280. [Online]. Available: http://dx.doi.org/10.1109/ICMLA.2012.214.
• [9] M. Rahman, L.-N. Pouchet, and P. Sadayappan, “Neural network assisted tile size selection,” in International Workshop on Automatic Performance Tuning (IWAPT’2010). Berkeley, CA: Springer Verlag, Jun. 2010.
• [10] T. Grosser, A. Cohen, J. Holewinski, P. Sadayappan, and S. Verdoolaege, “Hybrid hexagonal/classical tiling for gpus,” in Proceedings of Annual IEEE/ACM International Symposium on Code Generation and Optimization, ser. CGO ’14. New York, NY, USA: ACM, 2014, pp. 66:66–66:75. [Online]. Available: http://doi.acm.org/10.1145/2544137.2544160.
• [11] T. Grosser, A. Größlinger, and C. Lengauer, “Polly – performing polyhedral optimizations on a low-level intermediate representation,” Parallel Processing Letters, vol. 22, no. 4, 2012. [Online]. Available: https://doi.org/10.1142/S0129626412500107.
• [12] C. Lattner and V. Adve, “LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation,” in Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO’04), Palo Alto, California, Mar 2004.
• [13] C. Lattner, “LLVM: An Infrastructure for Multi-Stage Optimization,” Master’s thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, Urbana, IL, Dec 2002, See http://llvm.cs.uiuc.edu.
• [14] D. Terpstra, H. Jagode, H. You, and J. Dongarra, “Collecting performance data with PAPI-C,” in Tools for High Performance Computing 2009, M. S. Müller, M. M. Resch, A. Schulz, and W. E. Nagel, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 157–173.
• [15] L.-N. Pouchet, “Polybench/C - the Polyhedral Benchmark suite,” http://www.cse.ohio-state.edu/ pouchet/software/polybench/, accessed: 2017-09-14.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).