More Web Proxy on the site http://driver.im/

article

POET: a scripting language for applying parameterized source-to-source program transformations

Author:

Qing YiAuthors Info & Claims

Software—Practice & Experience, Volume 42, Issue 6

Pages 675 - 706

https://doi.org/10.1002/spe.1089

Published: 01 June 2012 Publication History

Abstract

We present POET, a scripting language designed for applying advanced program transformations to code in arbitrary programming languages as well as building ad hoc translators between these languages. We have used POET to support a large number of compiler optimizations, including loop interchange, parallelization, blocking, fusion/fission, strength reduction, scalar replacement, SSE vectorization, among others, and to fully support the code generation of several domain-specific languages, including automatic tester/timer generation, and automatically translating a finite-state-machine-based behavior modeling language into C++/ Java code. This paper presents key design and implementation decisions of the POET language and show how to use various language features to significantly reduce the difficulty of supporting programmable compiler optimization for high performance computing and supporting ad hoc code generation for various domain-specific languages. Copyright © 2011 John Wiley & Sons, Ltd.

References

[1]

Daby C. Implementing UML statechart diagrams. {May 2004}.

[2]

Metamill software. {2008}.

[3]

Umodel. Altova Inc. {2011}.

[4]

Whaley RC, Petitet A, Dongarra J. Automated empirical optimizations of software and the ATLAS project. Parallel Computing 2001; 27(1):3–25.

[5]

Frigo M, Johnson S. FFTW: An adaptive software architecture for the FFT. Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Seattle, WA, vol. 3, 1998; 1381–1381.

[6]

S M, Q D. A source-to-source architecture for user-defined optimizations. Joint Modular Languages Conference Held in Conjunction with EuroPar'03, Austria, 2003.

[7]

Yi Q, Qasem A. Exploring the optimization space of dense linear algebra kernels. The 21th International Workshop on Languages and Compilers for Parallel Computing, Edmonton, Alberta, Canada, 2008.

Digital Library

[8]

Yi Q, Whaley C. Automated transformation for performance-critical kernels. ACM SIGPLAN Symposium on Library-Centric Software Design, Montreal, Canada, October 2007.

Digital Library

[9]

Magee J, Yi Q, Whaley RC. Automated timer generation for empirical tuning. The Fourth Workshop on Statistical and Machine Learning Approaches to ARchitecture and compilaTion, Pisa, Italy, 2010.

[10]

Yi Q, Niu J, Marneni AR. Collective specification and verification of behavioral models and object-oriented implementations. CS-TR ICSOFT'11: International Conference on Software and Data Technologies, Seville, Spain, July 2011.

[11]

Rahman SF, Guo J, Yi Q. Automated empirical tuning of scientific codes for performance and power consumption. HIPEAC: High-Performance and Embedded Architectures and Compilers, Heraklion, Greece, 2011.

[12]

Quinlan D, Schordan M, Yi Q, de Supinski B. Semantic-driven parallelization of loops operating on user-defined containers. 16th Annual Workshop on Languages and Compilers for Parallel Computing, College Station, TX, 2003.

[13]

Yi Q. Automated programmable control and parameterization of compiler optimizations. CGO: ACM/IEEE International Symposium on Code Generation and Optimization, 2011.

[14]

Levine JR, Mason T, Brown D. Lex & Yacc. O'Reilly & Associates: Sebastopol, CA, 1992.

[15]

Muchnick S. Advanced Compiler Design and Implementation. Morgan Kaufmann: San Francisco, 1997.

Digital Library

[16]

Qasem A, Guo J, Rahman F, Yi Q. Exposing tunable parameters in multi-threaded numerical code. Seventh IFIP International Conference on Network and Parallel Computing, Zhengzhou, China, 2010.

[17]

Yi Q, Quinlan D. Applying loop optimizations to object-oriented abstractions through general classification of array semantics. The 17th International Workshop on Languages and Compilers for Parallel Computing, West Lafayette, Indiana, U.S.A., 2004.

[18]

Cimatti A, Clarke E, Giunchiglia E, Giunchiglia F, Pistore M, Roveri M, Sebastiani R, Tacchella A. NuSMV version 2: An opensource tool for symbolic model checking. Proceedings of the International Conference on Computer-Aided Verification (CAV'02) (Lecture Notes in Computer Science, vol. 2404). Springer: Copenhagen, Denmark, 2002.

[19]

Baxter ID. Using transformation systems for software maintenance and reengineering. ICSE '01: Proceedings of the 23rd International Conference on Software Engineering. IEEE Computer Society: Washington, DC, U.S.A., 2001; 739–740.

[20]

Akers R, Baxter I, Mehlich M, Ellis B, Luecke K. Re-engineering C++ component models via automatic program transformation. 12th Working Conference on Reverse Engineering. IEEE: New York, 2005.

Digital Library

[21]

Futamura Y, Konishi Z, Glück R. Wsdfu: Program transformation system based on generalized partial computation. The Essence of Computation: Complexity, Analysis, Transformation. Springer, 2002; 358–378. ISBN: .

[22]

Balzer R, Goldman N, Wile D. On the transformational implementation approach to programming. ICSE '76: Proceedings of the Second International Conference on Software Engineering. IEEE Computer Society Press: Los Alamitos, CA, U.S.A., 1976; 337–344.

[23]

Bauer FL, Möller B, Partsch H, Pepper P. Formal program construction by transformations-computer-aided, intuition-guided programming. IEEE Transactions on Software Engineering 1989; 15(2):165–180.

Digital Library

[24]

Neighbors J. Software construction using components Ph d Thesis, ICS-TR-160, University of Californa at Irvine, 1980.

[25]

Freeman P. A conceptual analysis of the draco approach to constructing software systems. IEEE Transactions on Software Engineering 1987; 13(7):830–844.

Digital Library

[26]

Garlan D, Cai L, Nord RL. A transformational approach to generating application-specific environments. SDE 5: Proceedings of the Fifth ACM SIGSOFT Symposium on Software Development Environments. ACM Press: New York, NY, U.S.A., 1992; 68–77.

[27]

Sander I, Jantsch A. Transformation based communication and clock domain refinement for system design. DAC '02: Proceedings of the 39th Conference on Design Automation. ACM Press: New York, NY, U.S.A., 2002; 281–286.

[28]

Feather MS. A system for assisting program transformation. ACM Transactions on Programming Languages and Systems 1982; 4(1):1–20.

[29]

Fähndrich M, Carbin M, Larus JR. Reflective program generation with patterns. GPCE '06: Proceedings of the Fifth International Conference on Generative Programming and Component Engineering. ACM Press: New York, NY, U.S.A., 2006; 275–284.

[30]

Budinsky FJ, Finnie MA, Vlissides JM, Yu PS. Automatic code generation from design patterns. IBM System Journal 1996; 35(2):151–171.

[31]

Oh H, Ha S. Efficient code synthesis from extended dataflow graphs for multimedia applications. Design Automation Conference, New Orleans, LA, U.S.A., 2002.

[32]

Huang SS, Zook D, Smaragdakis Y. Statically safe program generation with safegen. Generative Programming and Component Engineering, Tallinn, Estonia, 2005.

[33]

Erwig M, Ren D. A rule-based language for programming software updates. SIGPLAN Notes 2002; 37(12):88–97.

[34]

Bravenboer M, Kalleberg KT, Vermaas R, Visser E. Stratego/XT 0.17. A language and toolset for program transformation. Science of Computer Programming 2008; 72(1–2).

[35]

Bagge OS, Kalleberg KT, Haveraaen M, Visser E. Design of the CodeBoost transformation system for domain-specific optimisation of C++ programs. Third International Workshop on Source Code Analysis and Manipulation (SCAM'03), Binkley D, Tonella P (eds). IEEE Computer Society Press: Amsterdam, The Netherlands, 2003; 65–75.

[36]

Beckmann O, Houghton A, Mellor M, Kelly PHJ. Run-time code generation in C++ as a foundation for domain-specific optimisation. Internationnal Seminar on Domain-Specific Program Generation (Lecture Notes in Computer Science, vol. 3016), Lengauer C, Batory D, Consel C, Odersky M (eds), Dagstuhl Castle, Germany, 23–28 March 2003. Revised Papers, 2004; 291–306.

[37]

Engler DR, Hsieh W, Kaashoek M. 'C: A language for high-level, efficient, and machine-independent code generation. POPL, St. Petersburg Beach, FL, 1996; 131–144.

[38]

Grant B, Mock M, Philipose M, Chambers C, Eggers SJ. DyC: An expressive annotation-directed dynamic compiler for C. Theoretical Computer Science 2000; 248(1–2):147–199.

[39]

Jones ND, Gomard CK, Sestoft P. Partial Evaluation and Automatic Program Generation. Prentice-Hall: Englewood Cliffs, NJ, 1993.

[40]

Püschel M, Moura JMF, Johnson J, Padua D, Veloso M, Singer BW, Xiong J, Franchetti F, Gačić A, Voronenko Y, Chen K, Johnson RW, Rizzolo N. SPIRAL: Code generation for DSP transforms. IEEE Special Issue on Program Generation, Optimization, and Adaptation, 2005; 93(2):232–275.

[41]

Bilmes J, Asanovic K, Chin C-W, Demmel J. Optimizing matrix multiply using phipac: A portable, high-performance, ansi c coding methodology. Proceedings of the 11th International Conference on Supercomputing. ACM Press: New York, NY, U.S.A., 1997; 340–347.

[42]

Ahmed N, Mateev N, Pingali K, Stodghill P. A framework for sparse matrix code synthesis from high-level specifications. Supercomputing 2000; 74.

[43]

Thibault SA, Marlet R, Consel C. Domain-specific languages: From design to implementation application to video device drivers generation. IEEE Transactions on Software Engineering 1999; 25(3):363–377.

Digital Library

[44]

Han S-C, Franchetti F, Püschel M. Program generation for the all-pairs shortest path problem. PACT '06: Proceedings of the 15th International Conference on Parallel Architectures and Compilation Techniques. ACM Press: New York, NY, U.S.A., 2006; 222–232.

[45]

Kisuki T, Knijnenburg P, O'Boyle M, Wijsho H. Iterative compilation in program optimization. Compilers for Parallel Computers, Aussois, 2000; 35–44.

[46]

Pike G, Hilfinger P. Better tiling and array contraction for compiling scientific programs. SC, Baltimore, MD, U.S.A., November 2002.

Digital Library

[47]

Stephenson M, Amarasinghe S. Predicting unroll factors using supervised classification. CGO, San Jose, CA, U.S.A., March 2005.

Digital Library

[48]

Fursin G, Cohen A, O'Boyle M, Temam O. A practical method for quickly evaluating program optimizations. HiPEAC, Barcelona, Spain, November 2005.

Digital Library

[49]

Pan Z, Eigenmann R. Fast automatic procedure-level performance tuning. Proceedings of the Parallel Architectures and Compilation Techniques, Seattle, WA, 2006.

Digital Library

[50]

Qasem A, Kennedy K, Mellor-Crummey J. Automatic tuning of whole applications using direct search and a performance-based transformation system. Proceedings of the LACSI Symposium. Los Alamos Computer Science Institute: Los Alamos, NM, 2004.

[51]

O'Boyle M, Motogelwa N, Knijnenburg P. Feedback assisted iterative compilation. Languages and Compilers for Parallel Computing, Yorktown Heights, NY, 2000.

[52]

Qasem A, Kennedy K, Mellor-Crummey J. Automatic tuning of whole applications using direct search and a performance-based transformation system. The Journal of Supercomputing 2006; 36(2):183–196.

[53]

Cohen A, Sigler M, Girbal S, Temam O, Parello D, Vasilache N. Facilitating the search for compositions of program transformations. ICS '05: Proceedings of the 19th Annual International Conference on Supercomputing. ACM: New York, NY, U.S.A., 2005; 151–160.

[54]

Vuduc R, Demmel J, Bilmes J. Statistical models for automatic performance tuning. International Journal of High Performance Computing Applications 2004; 18(1):65–94.

[55]

Qasem A, Kennedy K. Profitable loop fusion and tiling using model-driven empirical search. Proceedings of the 20th ACM International Conference on SuperComputing (ICS'06), Cairns, Australia, June 2006.

Digital Library

[56]

Yotov K, Li X, Ren G, Garzaran M, Padua D, Pingali K, Stodghill P. A comparison of empirical and model-driven optimization. ACM SIGPLAN Noices 2003; 38(5):63–76.

[57]

Chen C, Chame J, Hall M. Combining models and guided empirical search to optimize for multiple levels of the memory hierarchy. International Symposium on Code Generation and Optimization, San Jose, CA, March 2005.

Digital Library

[58]

Lam M, Rothberg E, Wolf ME. The cache performance and optimizations of blocked algorithms. Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IV), Santa Clara, April 1991.

Digital Library

[59]

McKinley K, Carr S, Tseng C. Improving data locality with loop transformations. ACM Transactions on Programming Languages and Systems 1996; 18(4):424–453.

[60]

Wolfe MJ. More iteration space tiling. Proceedings of Supercomputing, Reno, November 1989.

[61]

Carr S, Kennedy K. Improving the ratio of memory operations to floating-point operations in loops. ACM Transactions on Programming Languages and Systems 1994; 16(6):1768–1810.

[62]

Pouchet L-N, Bastoul C, Cohen A, Vasilache N. Iterative optimization in the polyhedral model: Part i, one-dimensional time. Proceedings of the International Symposium on Code Generation and Optimization (CGO'07). IEEE Computer Society: Washington, DC, U.S.A., 2007; 144–156.

[63]

Tiwari A, Chen C, Chame J, Hall M, Hollingsworth JK. A scalable auto-tuning framework for compiler optimization. IPDPS '09: Proceedings of the 2009 IEEE International Symposium on Parallel and Distributed Processing. IEEE Computer Society: Washington, DC, U.S.A., 2009; 1–12.

[64]

Bondhugula U, Hartono A, Ramanujam J, Sadayappan P. A practical automatic polyhedral parallelizer and locality optimizer. Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'08). ACM: New York, NY, U.S.A., 2008; 101–113.

Digital Library

[65]

Pugh W. Uniform techniques for loop optimization. Proceedings of the 1991 ACM International Conference on Supercomputing, Cologne, June 1991.

Digital Library

[66]

Ahmed N, Mateev N, Pingali K. Synthesizing transformations for locality enhancement of imperfectly-nested loop nests. Proceedings of the 2000 ACM International Conference on Supercomputing, Santa Fe, New Mexico, May 2000.

Digital Library

[67]

Lim AW, Cheong GI, Lam MS. An affine partitioning algorithm to maximize parallelism and minimize communication. Proceedings of the 13th ACM SIGARCH International Conference on Supercomputing, Rhodes, Greece, June 1999.

Digital Library

[68]

Pugh W, Rosser E. Iteration Space Slicing For Locality. LCPC'99, La Jolla/San Diego, CA, July 1999.

[69]

Yi Q, Kennedy K, Adve V. Transforming complex loop nests for locality. The Journal of Supercomputing 2004; 27:219–264.

[70]

Vandierendonck H, Rul S, De Bosschere K. The paralax infrastructure: automatic parallelization with a helping hand. Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques (PACT'10). ACM: New York, NY, U.S.A., 2010; 389–400.

[71]

Dave C, Bae H, Min S-J, Lee S, Eigenmann R, Midkiff S. Cetus: A source-to-source compiler infrastructure for multicores. IEEE Computer 2009; 42:36–42.

[72]

The Open64 Compiler. Available at: {2011}.

[73]

Dagum L, Menon R. Openmp: An industry standard api for shared-memory programming. Computational Science and Engineering, IEEE 1998; 5(1):46–55.

[74]

Donadio S, Brodman J, Roeder T, Yotov K, Barthou D, Cohen A, Garzarán MJ, Padua D, Pingali K. A language for the compact representation of multiple program versions. LCPC, Hawthorne, NY, October 2005.

[75]

Hall M, Chame J, Chen C, Shin J, Rudy G, Khan MM. Loop transformation recipes for code generation and auto-tuning. LCPC, Newark, DE, U.S.A., October 2009.

Cited By

Bansal MHsu OOlukotun KKjolstad F(2023)Mosaic: An Interoperable Compiler for Tensor AlgebraProceedings of the ACM on Programming Languages10.1145/35912367:PLDI(394-419)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591236
Vendramini VGoldman AMounié GCavalcante EDantas FBatista T(2020)Improving mobile app development using transpilers with maintainable outputsProceedings of the XXXIV Brazilian Symposium on Software Engineering10.1145/3422392.3422426(354-363)Online publication date: 21-Oct-2020
https://dl.acm.org/doi/10.1145/3422392.3422426
Chelini LGysi TGrosser TKong MCorporaal HSarkar VKim H(2020)Automatic Generation of Multi-Objective Polyhedral Compiler TransformationsProceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques10.1145/3410463.3414635(83-96)Online publication date: 30-Sep-2020
https://dl.acm.org/doi/10.1145/3410463.3414635
Show More Cited By

POET: a scripting language for applying parameterized source-to-source program transformations
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages

Recommendations

Source-to-Source Compilation via Submodules
ELS2016: Proceedings of the 9th European Lisp Symposium on European Lisp Symposium

Racket's macro system enables language extension and definition primarily for programs that are run on the Racket virtual machine, but macro facilities are also useful for implementing languages and compilers that target different platforms. Even when ...
Mixing source and bytecode: a case for compilation by normalization

Language extensions increase programmer productivity by providing concise, often domain-specific syntax, and support for static verification of correctness, security, and style constraints. Language extensions can often be realized through translation ...
Mixing source and bytecode: a case for compilation by normalization
OOPSLA '08: Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications

Language extensions increase programmer productivity by providing concise, often domain-specific syntax, and support for static verification of correctness, security, and style constraints. Language extensions can often be realized through translation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Software

Software Volume 42, Issue 6

June 2012

126 pages

ISSN:0038-0644

EISSN:1097-024X

Issue’s Table of Contents

Publisher

John Wiley & Sons, Inc.

United States

Publication History

Published: 01 June 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bansal MHsu OOlukotun KKjolstad F(2023)Mosaic: An Interoperable Compiler for Tensor AlgebraProceedings of the ACM on Programming Languages10.1145/35912367:PLDI(394-419)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591236
Vendramini VGoldman AMounié GCavalcante EDantas FBatista T(2020)Improving mobile app development using transpilers with maintainable outputsProceedings of the XXXIV Brazilian Symposium on Software Engineering10.1145/3422392.3422426(354-363)Online publication date: 21-Oct-2020
https://dl.acm.org/doi/10.1145/3422392.3422426
Chelini LGysi TGrosser TKong MCorporaal HSarkar VKim H(2020)Automatic Generation of Multi-Objective Polyhedral Compiler TransformationsProceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques10.1145/3410463.3414635(83-96)Online publication date: 30-Sep-2020
https://dl.acm.org/doi/10.1145/3410463.3414635
Wang TJain NBoehme DBeckingsale DMueller FGamblin TAyguadé EHwu WBadia RHofstee H(2020)CodeSeerProceedings of the 34th ACM International Conference on Supercomputing10.1145/3392717.3392741(1-11)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1145/3392717.3392741
(2019)Using the loop chain abstraction to schedule across loops in existing codeInternational Journal of High Performance Computing and Networking10.5555/3302714.330272013:1(86-104)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3302714.3302720
Chelini LZinenko OGrosser TCorporaal H(2019)Declarative Loop Tactics for Domain-specific OptimizationACM Transactions on Architecture and Code Optimization10.1145/337226616:4(1-25)Online publication date: 26-Dec-2019
https://dl.acm.org/doi/10.1145/3372266
Wang TJain NBeckingsale DBoehme DMueller FGamblin T(2019)FuncyTunerProceedings of the 48th International Conference on Parallel Processing10.1145/3337821.3337842(1-10)Online publication date: 5-Aug-2019
https://dl.acm.org/doi/10.1145/3337821.3337842
Zhang JYi QDechev DZimmermann TLawall JMarinov D(2019)Automating non-blocking synchronization in concurrent data abstractionsProceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2019.00074(735-747)Online publication date: 10-Nov-2019
https://dl.acm.org/doi/10.1109/ASE.2019.00074
Davis EStrout MOlschanowsky CKnoop JSchordan MJohnson TO'Boyle M(2018)Transforming loop chains via macro dataflow graphsProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168832(265-277)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168832
Laborde PFeldman SDechev D(2017)A Wait-Free Hash MapInternational Journal of Parallel Programming10.1007/s10766-015-0376-345:3(421-448)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s10766-015-0376-3
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents