Czasopismo | ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA | Rocznik 2016 - zeszyt 12

Polyhedral Source-to-Source Compiler

10.15199/13.2016.12.1

nr katalogowy: 102952
10.15199/13.2016.12.1

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. Keywords: polyhedral model, parallel programming, LLVM, OpenMP, OpenACC.Background and Motivation Compilation of a program is the process of translating an input source code, which is usually written in a human-readable form, into a target language, usually executable by the machine. Efficient compilation has become an increasingly difficult challenge with the evolution of computers and computing needs as well. In particular, the programmer expects the compiler to produce efficient code on a wide variety of architectures, extracting the most performance out of their resources. For many decades the speedup of programs’ execution could be obtained by using faster processors for execution of the same binary program. The new CPUs were equipped with the same instruction set so there was a little need to develop new optimization algorithms which could be better suited to new CPUs. This trend has been stopped because of thermal dissipation aspects and disproportionate cost of decreasing chip size. As a result, the processing units which are manufactured nowadays contain more functional units operating at the same speed as those from 10 years ago [5]. This change of computer architectures started the trend of increased parallelism in modern mac[...]

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.. Elektronika 12/2016 13
[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.

Jeśli masz wykupiony/przyznany dostęp - zaloguj się. Skorzystaj z naszych propozycji zakupu!

Publikacja


e-Publikacja (format pdf) - nr 102952 "Polyhedral Source-to-Sour..." licencja: Osobista Produkt cyfrowy	10.00 zł

Zeszyt


ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - e-zeszyt (pdf) 2016-12 licencja: Osobista Produkt cyfrowy	35.00 zł

Prenumerata

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

420.00 zł

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - papierowa prenumerata roczna	528.00 zł brutto 488.89 zł netto 39.11 zł VAT (stawka VAT 8%)
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - pakowanie i wysyłka	42.00 zł brutto 34.15 zł netto 7.85 zł VAT (stawka VAT 23%)

570.00 zł

ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
ELEKTRONIKA - KONSTRUKCJE, TECHNOLOGIE, ZASTOSOWANIA - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	636.00 zł brutto 588.89 zł netto 47.11 zł VAT (stawka VAT 8%)

636.00 zł

Zeszyt

2016-12

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma