Polyhedral Source-to-Source Compile

• Autorzy: Adamski D. , Jabłoński G. , Perek P. , Napieralski A.

Identyfikatory

DOI

10.15199/13.2016.12.1

Warianty tytułu

PL

Polihedralny kompilator typu source-to-source

• Języki publikacji: EN

Abstrakty

EN

This paper describes a novel Polyhedral Source-to-Source Compiler (PSSC) that enables automatic recognition of parallel regions of C/C++ code and annotating them with OpenMP/OpenACC pragmas. The proposed source-to-source compiler uses polyhedral model to detect and optimize parallel loops. Loop optimization is done on intermediate code representation by Polly compiler and then it is mapped to original source code. This approach allows combining the simplicity and efficiency of Intermediate Representation (IR) code optimization with readability of output code. Experimental results show that the proposed compiler is able to reach the comparable performance to the original Polly compiler.

PL

Artykuł opisuje nowatorski kompilator typu source-to-source, który wykorzystuje model polihedralny do automatycznego wykrywania kodu C/C++, który może być wykonywany równolegle. Fragmenty kodu źródłowego, które mogą zostać zrównoleglone, są opatrywane pragmami OpenMP/OpenACC. Opisywany kompilator śledzi zmiany jakie zostały wprowadzone w kodzie pośrednim przez kompilator Polly, a następnie odwzoruje te transformacje w kodzie źródłowym. Przedstawione w artykule podejście umożliwia połączenie zalet wynikających z optymalizowania kodu pośredniego z możliwością łatwego przenoszenia na różne platformy kodu wysokopoziomowego. Przeprowadzone pomiary wydajności wykazały, że opracowany kompilator pozwala zrównoleglić kod wysokopoziomowy równie wydajnie jak bazowy kompilator Polly.

Słowa kluczowe

EN

polyhedral model; parallel programming; LLVM; OpenMP; OpenACC

PL

model polihedralny; programowanie równoległe; LLVM; OpenMP; OpenACC

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2016
• Tom: Vol. 57, nr 12
• Strony: 3--13
• Opis fizyczny: Bibliogr. 29 poz., wykr., tab.

Twórcy

autor

Adamski D.

• Lodz University of Technology, Department of Microelectronics and Computer Science

autor

Jabłoński G.

• Lodz University of Technology, Department of Microelectronics and Computer Science

autor

Perek P.

• Lodz University of Technology, Department of Microelectronics and Computer Science

autor

Napieralski A.

• Lodz University of Technology, Department of Microelectronics and Computer Science

Bibliografia

• [1] A. Kotha, T. Creech and R. Barua, 2013 „AESOP: The Autoparallelizing Compiler for Shared Memory Computers.” Tech. rep., Department of Electrical and Computer Engineering, University of Maryland.
• [2] A. Piotrowski, D. Makowski, G. Jablonski, S. Tarnowski and A. Napieralski. 2008. „Hardware fault tolerance implemented in software at the compiler level with special emphasis on array-variable protection.” Mixed Design of Integrated Circuits and Systems, 2008. MIXDES 2008. 15th International Conference on. 115–119.
• [3] Alexander Schrijver. 1986. Theory of linear and integer programming. New York, NY, USA: John Wiley & Sons, Inc..
• [4] Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman. 2006. Compilers: Principles, Techniques, and Tools (2Nd Edition). Boston, MA: Addison-Wesley Longman Publishing Co., Inc.
• [5] Andrew B. Kahng. 2013. „The ITRS Design Technology and System Drivers Roadmap: Process and Status.” Proceedings of the 50th Annual Design Automation Conference. Austin: ACM, 34:1–34:6.
• [6] Aparna Kotha, Kapil Anand, Matthew Smithson, Greeshma Yellareddy and Rajeev Barua. 2010. „Automatic Parallelization in a Binary Rewriter.” Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture. Washington, DC: IEEE Computer Society, 547–557.
• [7] Cedric Bastoul. 2004. „Code Generation in the Polyhedral Model Is Easier Than You Think.” Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques. Washington, DC: IEEE Computer Society, 7–16.
• [8] Cedric Bastoul et al. 2003.„Putting Polyhedral Loop Transformations to Work.” In Workshop on Languages and Compilers for Parallel Computing (LCPC’03), LNCS. 209–225.
• [9] Cédric Bastoul. 2004, „Improving Data Locality in Static Control Programs.” Ph.D. dissertation, University Paris 6, Pierre et Marie Curie, France.
• [10] Chris Lattner and Vikram Adve. 2004, „LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation.” Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO’04). Palo, Alto.
• [11] Chris Lattner. „LLVM: 2002 An Infrastructure for Multi-Stage Optimization.” Master’s thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, Urbana, I.
• [12] Ken Kennedy i John R. Allen. 2002. Optimizing compilers for modern architectures: a dependence-based approach. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc..
• [13] Khaled ElWazeer, Kapil Anand, Aparna Kotha, Matthew Smithson i Rajeev Barua. 2013 „Scalable Variable and Data Type Detection in a Binary Rewriter.” SIGPLAN Not. (ACM) 48: 51–60.
• [14] Konrad Trifunovic et al.. 2010 „GRAPHITE Two Years After: First Lessons Learned From Real-World Polyhedral Compilation.” GCC Research Opportunities Workshop (GROW’10). Pisa, Itali.
• [15] Louis-Noël Pouchet. 2010. „Interative Optimization in the Polyhedral Model.” Ph.D. dissertation, University of Paris-Sud 11, Orsay, Franc.
• [16] Polybench/C - the Polyhedral Benchmark suite. 31 10 2016. http://web.cse.ohio-state.edu/~pouchet/software/polybench/ (accessed: 10 31, 2016).
• [17] Pouchet Louis-Noel. 31 10 2016. http://web.cse.ohio-state. edu/~pouchet/software/polyopt/polyopt.html (accessed: 10 31, 2016).
• [18] Mehdi Amini. 2012 „Source-to-Source Automatic Program Transformations for GPU-like Hardware Accelerators.” Ph.D. dissertation, Paris Institute of Technology, Fontainebleau, Franc.
• [19] Patrice Quinton and Vincent Van Dongen. (1989) „The Mapping of Linear Recurrence Equations on Regular Arrays.” Journal of VLSI Signal Processing 1: 95–113.
• [20] Paul Feautrier. (1988) „Parametric Integer Programming.” RAIRO Recherche Op’erationnelle 22.
• [21] Richard M. Karp, Raymond E. Miller i Schmuel Winograd. 1967: „The organization of computations for uniform recurrence equations.” J. ACM, 563–590.
• [22] Source Level Debugging with LLVM. 31 10 2016. http://llvm.org/docs/SourceLevelDebugging.html (data uzyskania dostępu: 10 31, 2016).
• [23] Sven Verdoolaege and Tobias Grosser. 2012, „Polyhedral Extraction Tool.” Second International Workshop on Polyhedral Compilation Techniques (IMPACT’12). Paris.
• [24] Sven Verdoolaege. „isl: 2010. An integer set library for the polyhedral model.” Redakcja: Komei Fukuda, Joris van der Hoeven, Michael Joswig i Nobuki Takayama. Lecture Notes in Computer Science, International Congress on Mathematical Software (ICMS 2010), Kobe, Japan, 13–17 September 2010. Springer, 299–302.
• [25] Sylvain Girbal et al. (2006) „Semi-automatic composition of loop transformations for deep parallelism and memory hierarchies.” Intl J. of Parallel Programming 34: 261–317.
• [26] Tobias Christian Grosser. 2011 „Enabling Polyhedral Optimizations in LLVM.” Master’s thesis, Department of Informatics and Mathematics, University of Passau.
• [27] U day Bondhugula, Albert Hartono, J. Ramanujam i P. Sadayappan. 2008. „A practical automatic polyhedral parallelizer and locality optimizer.” Proceedings of the 2008 ACM SIGPLAN conference on Programming language design and implementation. New York, NY, USA: ACM, 101–113.
• [28] U day Kumar Reddy Bondhugula. 2008. Effective automatic parallelization and locality optimization using the polyhedral model. Ph.D. dissertation, Ohio State University, Columbus, OH: Ohio State University.
• [29] Y. Yaacoby i P. R. Cappello. 1988. „Scheduling a system of affine recurrence equations onto a systolic array.” Systolic Arrays, 1988., Proceedings of the International Conference on. 373–382.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).