https://dl.acm.org/doi/abs/10.1145/3674735 skip to main content ACM Digital Library home ACM Association for Computing Machinery corporate logo * Advanced Search * Browse * About * + Sign in + Register * * Advanced Search * Journals * Magazines * Proceedings * Books * SIGs * Conferences * People * * More * Search ACM Digital Library[ ] SearchSearch Advanced Search ACM Transactions on Architecture and Code Optimization * Journal Home * Just Accepted * Latest Issue * * Archive * Authors + Author Guidelines + Submission Site + ACM Author Policies * Editors + Editorial Board + Editor Guide + Associate Editors Welcome Video * Reviewers + Information and Guidelines + Distinguished Reviewers + Submission Site * About + Charter + About TACO + Announcements + Abstracting/Indexing + TACO Author List + TACO Affiliations + ACM Award Winners * Open Access + TACO Open Access + ACM Open Access * Contact Us * More * Home * ACM Journals * ACM Transactions on Architecture and Code Optimization * Just Accepted * A Survey of General-purpose Polyhedral Compilers research-article Open access Share on * * * * * * Just Accepted A Survey of General-purpose Polyhedral Compilers Authors: [default-pr]Arun Thangamani, [contrib-81]Vincent Loechner, and [default-pr]Stephane GenaudAuthors Info & Claims ACM Transactions on Architecture and Code Optimization Accepted on 05 June 2024 https://doi.org/10.1145/3674735 Online AM: 22 June 2024 Publication History * 0citation * 68 * Downloads Metrics Total Citations0 Total Downloads68 Last 12 Months68 Last 6 weeks68 Get Citation Alerts New Citation Alert added! This alert has been successfully added and will be sent to: You will be notified whenever a record that you have chosen has been cited. To manage your alert preferences, click on the button below. Manage my Alerts New Citation Alert! Please log in to your account PDFeReader * Contents ACM Transactions on Architecture and Code Optimization Just Accepted PREVIOUS ARTICLE Lavender: An Efficient Resource Partitioning Framework for Large-Scale Job Colocation Previous NEXT ARTICLE Sectored DRAM: A Practical Energy-Efficient and High-Performance Fine-Grained DRAM Architecture Next + Abstract + References ACM Digital Library * + Information & Contributors + Bibliometrics & Citations + View Options + References + Media + Tables + Share Abstract Since the 1990's many implementations of polyhedral compilers have been written and distributed, either as source-to-source translating compilers or integrated into wider purpose compilers. This paper provides a survey on those various available implementations as of today, 2024. We list and describe most commonly available polyhedral schedulers and compiler implementations. Then, we compare the general-purpose polyhedral compilers using two main criteria, robustness and performance, on the PolyBench/C set of benchmarks. References [1] 2014. Candl - Data Dependence Analysis Tool in the Polyhedral Model. https://github.com/periscop/candl. Google Scholar [2] Saleh M. Alnaeli, Abdulkareem Alali, and Jonathan I. Maletic. 2012. Empirically Examining the Parallelizability of Open Source Software System. In Proceedings of the 2012 19th Working Conference on Reverse Engineering (WCRE '12). IEEE Computer Society, USA, 377-386. https:// doi.org/10.1109/WCRE.2012.47 Digital Library Google Scholar [3] Matthew Arnold, Michael Hind, and Barbara G. Ryder. 2001. An Empirical Study of Selective Optimization. In Languages and Compilers for Parallel Computing, Samuel P. Midkiff, Jose E. Moreira, Manish Gupta, Siddhartha Chatterjee, Jeanne Ferrante, Jan Prins, William Pugh, and Chau-Wen Tseng (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 49-67. Google Scholar [4] Amir H. Ashouri, William Killian, John Cavazos, Gianluca Palermo, and Cristina Silvano. 2018. A Survey on Compiler Autotuning Using Machine Learning. ACM Comput. Surv. (2018), 42 pages. https://doi.org/10.1145 /3197978 Digital Library Google Scholar [5] David F. Bacon, Susan L. Graham, and Oliver J. Sharp. 1994. Compiler Transformations for High-Performance Computing. ACM Comput. Surv. 26, 4 (dec 1994), 345-420. https://doi.org/10.1145/197405.197406 Digital Library Google Scholar [6] Riyadh Baghdadi, Jessica Ray, Malek Ben Romdhane, Emanuele Del Sozzo, Abdurrahman Akkas, Yunming Zhang, Patricia Suriana, Shoaib Kamil, and Saman Amarasinghe. 2019. Tiramisu: A Polyhedral Compiler for Expressing Fast and Portable Code. In IEEE/ACM International Symposium on Code Generation and Optimization. Google Scholar [7] Riyadh Baghdadi, Jessica Ray, Malek Ben Romdhane, Emanuele Del Sozzo, Abdurrahman Akkas, Yunming Zhang, Patricia Suriana, Shoaib Kamil, and Saman Amarasinghe. 2019. Tiramisu Compiler. https://github.com/ Tiramisu-Compiler/tiramisu. Google Scholar [8] Cedric Bastoul. 2004. Code Generation in the Polyhedral Model Is Easier Than You Think. In PACT'13 IEEE International Conference on Parallel Architecture and Compilation Techniques. Juan-les-Pins, France, 7-16. Google Scholar [9] C. Bastoul. 2008. Extracting polyhedral representation from high level languages. Technical Report. LRI, Paris-Sud University. Google Scholar [10] C. Bastoul. 2011. OpenScop: A Specification and a Library for Data Exchange in Polyhedral Compilation Tools. Technical Report. Paris-Sud University, France. Google Scholar [11] Uday Bondhugula, Albert Hartono, J. Ramanujam, and P. Sadayappan. 2008. A Practical Automatic Polyhedral Parallelizer and Locality Optimizer. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation(Tucson, AZ, USA) (PLDI '08). ACM, New York. https://doi.org/10.1145/1375581.1375595 Digital Library Google Scholar [12] Chun Chen, Jacqueline Chame, and Mary Hall. 2008. CHiLL: A framework for composing high-level loop transformations. Technical Report. University of Southern California. Google Scholar [13] Junjie Chen, Jibesh Patra, Michael Pradel, Yingfei Xiong, Hongyu Zhang, Dan Hao, and Lu Zhang. 2020. A Survey of Compiler Testing. ACM Comput. Surv. 53, 1, Article 4 (feb 2020), 36 pages. https://doi.org/ 10.1145/3363562 Digital Library Google Scholar [14] Philippe Clauss, Matthew Wahab, Juan Manuel Martinez Caamano, Aravind Sukumaran-Rajam, Artiom Baloian, Manuel Selva, and Raquel Lazcano. 2017. APOLLO: Automatic speculative POLyhedral Loop Optimizer. https: //webpages.gitlabpages.inria.fr/apollo/about. Google Scholar [15] G. Consolaro, Z. Zhang, H. Razanajato, N. Lossing, N. Tchoulak, A. Susungi, A. Araujo Alves, R. Zhang, D. Barthou, C. Ancourt, and C. Bastoul. 2024. PolyTOPS: Reconfigurable and Flexible Polyhedral Scheduler. In IEEE/ACM International Symposium on Code Generation and Optimization. https://doi.org/10.1109/CGO57630.2024.10444791 Crossref Google Scholar [16] GCC Compiler developers. 2011. GCC - The GNU Compiler Collection. https://gcc.gnu.org/. Google Scholar [17] Linux developers. 2022. perf profiling tool. https:// perf.wiki.kernel.org/index.php/Main_Page Google Scholar [18] NASA Advanced Supercomputing Division. -. NAS Parallel Benchmarks. https://www.nas.nasa.gov/software/npb.html. Google Scholar [19] Paul Feautrier. 1992. Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time. International Journal of Parallel Programming 21, 6 (01 Dec 1992), 389-420. https:/ /doi.org/10.1007/BF01379404 Crossref Google Scholar [20] P. Feautrier, J. Collard, and C. Bastoul. 2002. Solving systems of affine (in)equalities. Technical Report. PRiSM, Versailles University. Google Scholar [21] Paul Feautrier and Christian Lengauer. 2011. Polyhedron Model. In Encyclopedia of Parallel Computing, David Padua (Ed.). Springer US, Boston, MA, 1581-1592. https://doi.org/10.1007/978-0-387-09766-4_502 Crossref Google Scholar [22] Romain Fontaine, Laure Gonnord, and Lionel Morel. 2018. Polyhedral Dataflow Programming: A Case Study. In 2018 30th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD). 171-179. https://doi.org/10.1109/CAHPC.2018.8645947 Crossref Google Scholar [23] Tobias Grosser, Armin Grosslinger, and Christian Lengauer. 2012. Polly - Performing Polyhedral Optimizations on a Low-Level Intermediate Representation.Parallel Process. Lett. 22, 4 (2012). https://doi.org/ 10.1142/S0129626412500107 Crossref Google Scholar [24] PolyMage lab developers. 2023. PolyMage. https://www.polymagelabs.com /. Google Scholar [25] Lawrence Livermore National Laboratory. 1993. Livermore Benchmarks. https://netlib.org/benchmark/livermore. Google Scholar [26] Polly Labs. 2014. Integer Set Library. https://www.openhub.net/p/isl. Google Scholar [27] Chris Lattner and Vikram Adve. 2004. LLVM: A Compilation Framework for Lifelong Program Analysis and Transformation. In CGO. San Jose, CA, USA, 75-88. Digital Library Google Scholar [28] Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, and Oleksandr Zinenko. 2021. MLIR: Scaling Compiler Infrastructure for Domain Specific Computation. In 2021 IEEE/ACM Int. Symp. on Code Generation and Optimization (CGO). 2-14. https:// doi.org/10.1109/CGO51591.2021.9370308 Digital Library Google Scholar [29] Corinna G. Lee. 1998. UTDSP Benchmark. https://www.eecg.utoronto.ca/ ~corinna/DSP/infrastructure/UTDSP.html. Google Scholar [30] Sang-Ik Lee, Troy A. Johnson, and Rudolf Eigenmann. 2004. Cetus - An Extensible Compiler Infrastructure for Source-to-Source Transformation. In Languages and Compilers for Parallel Computing, Lawrence Rauchwerger (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 539-553. Google Scholar [31] Mingzhen Li, Yi Liu, Xiaoyan Liu, Qingxiao Sun, Xin You, Hailong Yang, Zhongzhi Luan, Lin Gan, Guangwen Yang, and Depei Qian. 2021. The Deep Learning Compiler: A Comprehensive Survey. IEEE Transactions on Parallel and Distributed Systems 32, 3 (2021), 708-727. https:// doi.org/10.1109/TPDS.2020.3030548 Crossref Google Scholar [32] Vincent Loechner. 1999. PolyLib: a library of polyhedral functions. https://github.com/vincentloechner/polylib. Google Scholar [33] Benoit Meister, Nicolas Vasilache, David Wohlford, Muthu Manikandan Baskaran, Allen Leung, and Richard Lethin. 2011. R-Stream Compiler. Springer US, Boston, MA, 1756-1765. https://doi.org/10.1007/ 978-0-387-09766-4_515 Crossref Google Scholar [34] William S. Moses, Lorenzo Chelini, Ruizhe Zhao, and Oleksandr Zinenko. 2021. Polygeist: Raising C to Polyhedral MLIR. In 2021 30th International Conference on Parallel Architectures and Compilation Techniques (PACT). 45-59. https://doi.org/10.1109/ PACT52795.2021.00011 Crossref Google Scholar [35] Dheya Mustafa. 2022. A Survey of Performance Tuning Techniques and Tools for Parallel Applications. IEEE Access 10(2022), 15036-15055. https://doi.org/10.1109/ACCESS.2022.3147846 Crossref Google Scholar [36] Marek Palkowski, Tomasz Klimek, and Wlodzimierz Bielecki. 2015. TRACO: An automatic loop nest parallelizer for numerical applications. In 2015 Federated Conference on Computer Science and Information Systems (FedCSIS). 681-686. https://doi.org/10.15439/ 2015F34 Crossref Google Scholar [37] Philip Pfaffe, Tobias Grosser, and Martin Tillmann. 2019. Efficient Hierarchical Online-Autotuning: A Case Study on Polyhedral Accelerator Mapping. In Proceedings of the ACM International Conference on Supercomputing (Phoenix, Arizona) (ICS '19). ACM, New York, 354-366. https://doi.org/10.1145/3330345.3330377 Digital Library Google Scholar [38] Arjun Pitchanathan, Christian Ulmann, Michel Weber, Torsten Hoefler, and Tobias Grosser. 2021. FPL: fast Presburger arithmetic through transprecision. Proc. ACM Program. Lang. 5, OOPSLA (2021). https:// doi.org/10.1145/3485539 Digital Library Google Scholar [39] Sebastian Pop, Albert Cohen, Cedric Bastoul, Sylvain Girbal, Georges-Andre Silber, and Nicolas Vasilache. 2006. GRAPHITE : Polyhedral Analyses and Optimizations for GCC. Google Scholar [40] Louis-Noel Pouchet. 2012. PoCC - The Polyhedral Compiler Collection. http://web.cs.ucla.edu/~pouchet/software/pocc/. Google Scholar [41] Louis-Noel Pouchet and al. 2022. PoCC version 1.6.0-alpha. http:// pocc.sf.net Google Scholar [42] Louis-Noel Pouchet, Uday Bondhugula, Cedric Bastoul, Albert Cohen, J. Ramanujam, P. Sadayappan, and Nicolas Vasilache. 2011. Loop Transformations: Convexity, Pruning and Optimization. In Proceedings of the 38th Symposium on Principles of Programming Languages. https:/ /doi.org/10.1145/1926385.1926449 Digital Library Google Scholar [43] Louis-Noel Pouchet and P. Sadayappan. 2022. PolyOpt: A Framework for Polyhedral Optimization in the ROSE compiler. https://github.com/ rose-compiler/rose/tree/v0.11.100.0/projects/PolyOpt2 Google Scholar [44] Louis-Noel Pouchet and Tomofumi Yuki. 2022. PolyBench/C version 4.2.1-beta. http://polybench.sf.net Google Scholar [45] William Pugh. 1992. A Practical Algorithm for Exact Array Dependence Analysis. Commun. ACM 35, 8 (aug 1992), 102-114. https://doi.org/ 10.1145/135226.135233 Digital Library Google Scholar [46] William Pugh and Evan Rosser. 1997. Iteration Space Slicing and Its Application to Communication Optimization. In Proceedings of the 11th International Conference on Supercomputing. 221-228. https://doi.org/ 10.1145/263580.263637 Digital Library Google Scholar [47] Pierre-Yves Peneau, Rabab Bouziane, Abdoulayse Gamatie, Erven Rohou, Florent Bruguier, Gilles Sassatelli, Lionel Torres, and Sophiane Senni. 2016. Loop optimization in presence of STT-MRAM caches: A study of performance-energy tradeoffs. In 2016 26th International Workshop on Power and Timing Modeling, Optimization and Simulation (PATMOS). 162-169. https://doi.org/10.1109/PATMOS.2016.7833682 Crossref Google Scholar [48] Dan Quinlan and Chunhua Liao. 2011. The ROSE source-to-source compiler infrastructure. In Cetus users and compiler infrastructure workshop, in conjunction with PACT, Vol. 2011. Citeseer, 1. Google Scholar [49] Xiaolei Ren, Michael Ho, Jiang Ming, Yu Lei, and Li Li. 2021. Unleashing the Hidden Power of Compiler Optimization on Binary Code Difference: An Empirical Study. In Proceedings of the 42nd ACM SIGPLAN Int. Conf. on Programming Language Design and Implementation (PLDI 2021). ACM, New York. https://doi.org/10.1145/3453483.3454035 Digital Library Google Scholar [50] Meta Research. 2018. Tensor Comprehensions. https://github.com/ facebookresearch/TensorComprehensions. Google Scholar [51] Paul B. Schneck. 1973. A Survey of Compiler Optimization Techniques. In Proceedings of the ACM Annual Conference (ACM '73). ACM, New York, 106-113. https://doi.org/10.1145/800192.805690 Digital Library Google Scholar [52] Andreas Simburger, Sven Apel, Armin Grosslinger, and Christian Lengauer. 2013. The potential of polyhedral optimization: An empirical study. In 2013 28th IEEE/ACM International Conference on Automated Software Engineering (ASE). 508-518. https://doi.org/ 10.1109/ASE.2013.6693108 Digital Library Google Scholar [53] Jan Sjodin, Sebastian Pop, Harsha Jagasia, Tobias Grosser, and Antoniu Pop. 2009. Design of graphite and the Polyhedral Compilation Package. Google Scholar [54] Huawei Technologies. 2023. MindSpore AI computing Framework. https:// github.com/mindspore-ai/mindspore. Google Scholar [55] Dan Terpstra, Heike Jagode, Haihang You, and Jack Dongarra. 2010. Collecting Performance Data with PAPI-C. In Tools for High Performance Computing 2009, Matthias S. Muller, Michael M. Resch, Alexander Schulz, and Wolfgang E. Nagel (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 157-173. Google Scholar [56] Nicolas Vasilache, Oleksandr Zinenko, Theodoros Theodoridis, Priya Goyal, Zachary DeVito, William S. Moses, Sven Verdoolaege, Andrew Adams, and Albert Cohen. 2018. Tensor Comprehensions: Framework-Agnostic High-Performance Machine Learning Abstractions. arxiv:1802.04730 [cs.PL] Google Scholar [57] Sven Verdoolaege, Juan Carlos Juega, Albert Cohen, Jose Ignacio Gomez, Christian Tenllado, and Francky Catthoor. 2013. Polyhedral Parallel Code Generation for CUDA. (2013), 23 pages. https://doi.org/10.1145/2400682.2400713 Digital Library Google Scholar [58] Sven Verdoolaege and Tobias Grosser. 2012. Polyhedral Extraction Tool. 2nd International Workshop on Polyhedral Compilation Techniques (2012). https://impact-workshop.org/impact2012/workshop_IMPACT/ verdoolaege.pdf Google Scholar [59] Sven Verdoolaege, Serge Guelton, Tobias Grosser, and Albert Cohen. 2014. Schedule Trees. In IMPACT - 4th Workshop on Polyhedral Compilation Techniques, associated with HiPEAC. https:// inria.hal.science/hal-00911894 Google Scholar [60] Sven Verdoolaege, Manjunath Kudlur, Rob Schreiber, and Harinath Kamepalli. 2020. Generating SIMD Instructions for Cerebras CS-1 using Polyhedral Compilation Techniques. Google Scholar [61] Tim Zerrell and Jeremy Bruestle. 2019. Stripe: Tensor Compilation via the Nested Polyhedral Model. arxiv:1903.06498 [cs.DC] Google Scholar [62] Jie Zhao, Bojie Li, Wang Nie, Zhen Geng, Renwei Zhang, Xiong Gao, Bin Cheng, Chen Wu, Yun Cheng, Zheng Li, Peng Di, Kun Zhang, and Xuefeng Jin. 2021. AKG: Automatic Kernel Generation for Neural Processing Units Using Polyhedral Transformations. In Proceedings of the 42nd International Conference on Programming Language Design and Implementation. 16 pages. https://doi.org/10.1145/3453483.3454106 Digital Library Google Scholar [63] Zhide Zhou, Zhilei Ren, Guojun Gao, and He Jiang. 2021. An empirical study of optimization bugs in GCC and LLVM. Journal of Systems and Software 174 (2021), 110884. https://doi.org/10.1016/ j.jss.2020.110884 Crossref Google Scholar Index Terms 1. A Survey of General-purpose Polyhedral Compilers 1. Software and its engineering 1. Software notations and tools 1. Compilers 2. Software organization and properties 1. Extra-functional properties 1. Software performance Recommendations * General purpose languages should be metalanguages PEPM '10: Proceedings of the 2010 ACM SIGPLAN workshop on Partial evaluation and program manipulation In his paper, The Next 700 Programming Languages, the late Landin writes that "most programming languages are partly a way of expressing things in terms of other things and partly a basic set of given things." Landin tries to separate the general ... Read More * An experimental general purpose compiler AFIPS '67 (Spring): Proceedings of the April 18-20, 1967, spring joint computer conference With the advent of numerous programming languages, both special and general purpose, much interest has been generated in developing newer and higher level programming languages. Two notable approaches have been taken in the attempt to provide language ... Read More * Imbedding GPSS in a general purpose programming language WSC '81: Proceedings of the 13th conference on Winter simulation - Volume 1 GPSS has proven to be an excellent simulation language, but was not designed to perform the logical and computational tasks of a programming language. Strategies for improvement can take one of two paths: building adequate analytic constructs into the ... Read More Comments Please enable JavaScript to view thecomments powered by Disqus. Information & Contributors Information Published In cover image ACM Transactions on Architecture and Code Optimization ACM Transactions on Architecture and Code Optimization Just Accepted ISSN:1544-3566 EISSN:1544-3973 Table of Contents Copyright (c) 2024 Copyright held by the owner/author(s). Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). Publisher Association for Computing Machinery New York, NY, United States Publication History Online AM: 22 June 2024 Accepted: 05 June 2024 Revised: 02 May 2024 Received: 13 January 2024 Check for updates Author Tags 1. polyhedral compilation 2. benchmark 3. performance analysis Qualifiers * Research-article Contributors [loader-7e6] Other Metrics View Article Metrics Bibliometrics & Citations Bibliometrics Article Metrics * 0 Total Citations * 68 Total Downloads * Downloads (Last 12 months)68 * Downloads (Last 6 weeks)68 Other Metrics View Author Metrics Citations View Options View options PDF View or Download as a PDF file. PDF eReader View online with eReader. eReader Get Access Login options Check if you have access through your login credentials or your institution to get full access on this article. Sign in Full Access Get this Article Media Figures Other Tables Share Share Share this Publication link Copy Link Copied! Copying failed. Share on social media XLinkedinRedditFacebookemail Affiliations [default-pr] Arun Thangamani ICube, University of Strasbourg, Strasbourg, France CAMUS, Inria Research Centre Nancy Grand Est, Villers-les-Nancy France https://orcid.org/0000-0003-1382-2399 View Profile [contrib-81] Vincent Loechner ICube, University of Strasbourg, Strasbourg France CAMUS, Inria Research Centre Nancy Grand Est, Villers-les-Nancy France https://orcid.org/0000-0003-3481-4881 View Profile [default-pr] Stephane Genaud ICube, University of Strasbourg, Strasbourg France CAMUS, Inria Research Centre Nancy Grand Est, Villers-les-Nancy France https://orcid.org/0000-0003-0065-8083 View Profile Download PDF Go to Go to Show all references Request permissionsExpand All Collapse Expand Table Authors Info & Affiliations Export Citations Select Citation format[BibTeX ] * Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download,a status dialog will open to start the export process. The process may takea few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download + Download citation + Copy citation Footer Categories * Journals * Magazines * Books * Proceedings * SIGs * Conferences * Collections * People About * About ACM Digital Library * ACM Digital Library Board * Subscription Information * Author Guidelines * Using ACM Digital Library * All Holdings within the ACM Digital Library * ACM Computing Classification System * Accessibility Statement Join * Join ACM * Join SIGs * Subscribe to Publications * Institutions and Libraries Connect * Contact us via email * ACM on Facebook * ACM DL on X * ACM on Linkedin * Send Feedback * Submit a Bug Report The ACM Digital Library is published by the Association for Computing Machinery. Copyright (c) 2024 ACM, Inc. * Terms of Usage * Privacy Policy * Code of Ethics ACM Digital Library home ACM Association for Computing Machinery corporate logo Your Search Results Download Request We are preparing your search results for download ... We will inform you here when the file is ready. Download now! Your Search Results Download Request Your file of search results citations is now ready. Download now! Your Search Results Download Request Your search export query has expired. Please try again.