Bridging the Gap Between General-Purpose and Domain-Specific Compilers with Synthesis

Authors Alvin Cheung, Shoaib Kamil, Armando Solar-Lezama



PDF
Thumbnail PDF

File

LIPIcs.SNAPL.2015.51.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Author Details

Alvin Cheung
Shoaib Kamil
Armando Solar-Lezama

Cite AsGet BibTex

Alvin Cheung, Shoaib Kamil, and Armando Solar-Lezama. Bridging the Gap Between General-Purpose and Domain-Specific Compilers with Synthesis. In 1st Summit on Advances in Programming Languages (SNAPL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 32, pp. 51-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.SNAPL.2015.51

Abstract

This paper describes a new approach to program optimization that allows general purpose code to benefit from the optimization power of domain-specific compilers. The key to this approach is a synthesis-based technique to raise the level of abstraction of general-purpose code to enable aggressive domain-specific optimizations. We have been implementing this approach in an extensible system called Herd. The system is designed around a collection of parameterized kernel translators. Each kernel translator is associated with a domain-specific compiler, and the role of each kernel translator is to scan the input code in search of code fragments that can be optimized by the domain-specific compiler embedded within each kernel translator. By leveraging general synthesis technology, it is possible to have a generic kernel translator that can be specialized by compiler developers for each domain-specific compiler, making it easy to build new domain knowledge into the overall system. We illustrate this new approach to build optimizing compilers in two different domains, and highlight research challenges that need to be addressed in order to achieve the ultimate vision.
Keywords
  • compilers
  • domain-specific languages
  • program synthesis
  • cross compilation
  • verification

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Rajeev Alur, Rastislav Bodík, Garvit Juniwal, Milo M. K. Martin, Mukund Raghothaman, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. Syntax-guided synthesis. In Formal Methods in Computer-Aided Design, FMCAD 2013, Portland, OR, USA, October 20-23, 2013, pages 1-17, 2013. Google Scholar
  2. Jason Ansel, Shoaib Kamil, Kalyan Veeramachaneni, Jonathan Ragan-Kelley, Jeffrey Bosboom, Una-May O'Reilly, and Saman Amarasinghe. Opentuner: An extensible framework for program autotuning. In Proceedings of the 23rd International Conference on Parallel Architectures and Compilation, pages 303-316, 2014. Google Scholar
  3. Gilles Barthe, Juan Manuel Crespo, Sumit Gulwani, Cesar Kunz, and Mark Marron. From relational verification to simd loop synthesis. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 123-134, 2013. Google Scholar
  4. Gerald Baumgartner, Alexander Auer, David E. Bernholdt, Alina Bibireata, Venkatesh Choppella, Daniel Cociorva, Xiaoyang Gao, Robert J. Harrison, So Hirata, Sriram Krishnamoorthy, Sandhya Krishnan, Chi chung Lam, Qingda Lu, Marcel Nooijen, Russell M. Pitzer, J. Ramanujam, P. Sadayappan, Alexander Sibiryakov, D. E. Bernholdt, A. Bibireata, D. Cociorva, X. Gao, S. Krishnamoorthy, and S. Krishnan. Synthesis of high-performance parallel programs for a class of ab initio quantum chemistry models. In Proceedings of the IEEE, page 2005, 2005. Google Scholar
  5. Toby Bloom and Stanley B. Zdonik. Issues in the design of object-oriented database programming languages. In Proceedings of the Conference on Object-oriented Programming Systems, Languages and Applications, OOPSLA'87, pages 441-451, 1987. Google Scholar
  6. Rastislav Bodík and Barbara Jobstmann. Algorithmic program synthesis: introduction. STTT, 15(5-6):397-411, 2013. Google Scholar
  7. Bryan Catanzaro, Shoaib Kamil, Yunsup Lee, Krste Asanović, James Demmel, Kurt Keutzer, John Shalf, Ka thy Yelick, and Armando Fox. SEJITS: Getting productivity and performance with selective embedded JIT specialization. In Workshop on Programming Models for Emerging Architectures (PMEA 2009), Raleigh, NC, October 2009. Google Scholar
  8. Hassan Chafi, Arvind K. Sujeeth, Kevin J. Brown, HyoukJoong Lee, Anand R. Atreya, and Kunle Olukotun. A domain-specific approach to heterogeneous parallelism. In Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, PPoPP'11, New York, NY, USA, 2011. ACM. Google Scholar
  9. Alvin Cheung, Armando Solar-Lezama, and Samuel Madden. Optimizing database-backed applications with query synthesis. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 3-14, 2013. Google Scholar
  10. M. Christen, O. Schenk, and H. Burkhart. Patus: A code generation and autotuning framework for parallel iterative stencil computations on modern microarchitectures. In Parallel Distributed Processing Symposium (IPDPS), 2011 IEEE International, pages 676-687, May 2011. Google Scholar
  11. Leonardo Dagum and Ramesh Menon. Openmp: an industry standard api for shared-memory programming. Computational Science & Engineering, IEEE, 5(1):46-55, 1998. Google Scholar
  12. The django project. URL: http://www.djangoproject.com.
  13. Sumit Gulwani. Dimensions in program synthesis. In Proceedings of 10th International Conference on Formal Methods in Computer-Aided Design, page 1, 2010. Google Scholar
  14. Sumit Gulwani, Susmit Jha, Ashish Tiwari, and Ramarathnam Venkatesan. Synthesis of loop-free programs. In Proceedings of the 32Nd ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 62-73, 2011. Google Scholar
  15. Hibernate. URL: http://hibernate.org.
  16. F. Irigoin and R. Triolet. Supernode partitioning. In Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'88, pages 319-329, New York, NY, USA, 1988. ACM. Google Scholar
  17. Java Persistence API. URL: http://jcp.org/aboutJava/communityprocess/final/jsr317/index.html.
  18. Shoaib Kamil, Cy Chan, Leonid Oliker, John Shalf, and Samuel Williams. An auto-tuning framework for parallel multicore stencil computations. In IPDPS, pages 1-12, 2010. Google Scholar
  19. David Maier. Representing database programs as objects. In François Bancilhon and Peter Buneman, editors, Advances in Database Programming Languages, pages 377-386, New York, NY, USA, 1990. ACM. Google Scholar
  20. Saeed Maleki, Yaoqing Gao, Maria J. Garzarán, Tommy Wong, and David A. Padua. An evaluation of vectorizing compilers. In Proceedings of the 2011 International Conference on Parallel Architectures and Compilation Techniques, PACT'11, pages 372-382, Washington, DC, USA, 2011. IEEE Computer Society. Google Scholar
  21. Microsoft Entity Framework. URL: http://msdn.microsoft.com/en-us/data/ef.aspx.
  22. Mohanish Narayan. Polyopt/fortran: A polyhedral optimizer for fortran program. Master’s thesis, Ohio State University, 2012. Google Scholar
  23. Markus Püschel, José M. F. Moura, Jeremy Johnson, David Padua, Manuela Veloso, Bryan Singer, Jianxin Xiong, Franz Franchetti, Aca Gacic, Yevgen Voronenko, Kang Chen, Robert W. Johnson, and Nicholas Rizzolo. SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE, special issue on "Program Generation, Optimization, and Adaptation", 93(2):232- 275, 2005. Google Scholar
  24. Jonathan Ragan-Kelley, Andrew Adams, Sylvain Paris, Marc Levoy, Saman Amarasinghe, and Frédo Durand. Decoupling algorithms from schedules for easy optimization of image processing pipelines. ACM Trans. Graph., 31(4):32:1-32:12, July 2012. Google Scholar
  25. Tiark Rompf and Martin Odersky. Lightweight modular staging: A pragmatic approach to runtime code generation and compiled dsls. In Proceedings of the Ninth International Conference on Generative Programming and Component Engineering, GPCE'10, 2010. Google Scholar
  26. Ruby on Rails. URL: http://rubyonrails.org.
  27. Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic superoptimization. In Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 305-316, 2013. Google Scholar
  28. Armando Solar-Lezama, Liviu Tancau, Rastislav Bodík, Sanjit A. Seshia, and Vijay A. Saraswat. Combinatorial sketching for finite programs. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 404-415, 2006. Google Scholar
  29. Yuan Tang, Rezaul Chowdhury, Bradley C. Kuszmaul, Chi keung Luk, and Charles E. Leiserson. The pochoir stencil compiler. In In SPAA, 2011. Google Scholar
  30. Sid-Ahmed-Ali Touati and Denis Barthou. On the decidability of phase ordering problem in optimizing compilation. In Proceedings of the 3rd Conference on Computing Frontiers, pages 147-156, 2006. Google Scholar
  31. Yuan Yu, Michael Isard, Dennis Fetterly, Mihai Budiu, Úlfar Erlingsson, Pradeep Kumar Gunda, and Jon Currey. Dryadlinq: A system for general-purpose distributed data-parallel computing using a high-level language. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI'08, pages 1-14, Berkeley, CA, USA, 2008. USENIX Association. Google Scholar
  32. Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. Spark: Cluster computing with working sets. In Proceedings of the 2Nd USENIX Conference on Hot Topics in Cloud Computing, HotCloud'10, pages 10-10, Berkeley, CA, USA, 2010. USENIX Association. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail