Code generation in the polyhedral model is easier than you think
Open accessThe DOI matches its Crossref record; 28 of the 30 references it cites were found in a registry or an index.
Abstract
Many advances in automatic parallelization and optimization have been achieved through the polyhedral model. It has been extensively shown that this computational model provides convenient abstractions to reason about and apply program transformations. Nevertheless, the complexity of code generation has long been a deterrent for using polyhedral representation in optimizing compilers. First, code generators have a hard time coping with generated code size and control overhead that may spoil theoretical benefits achieved by the transformations. Second, this step is usually time consuming, hampering the integration of the polyhedral framework in production compilers or feedback-directed, iterative optimization schemes. Moreover, current code generation algorithms only cover a restrictive set of possible transformation functions. This paper discusses a general transformation framework able to deal with nonunimodular, noninvertible, nonintegral or even nonuniform functions. It presents several improvements to a state-of-the-art code generation algorithm. Two directions are explored: generated code size and code generator efficiency. Experimental evidence proves the ability of the improved method to handle real-life problems.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Theory of Linear and Integer Programming
Letchford, A. N., & Schrijver, A. (2000) · The Journal of the Operational Research Society · doi:10.2307/253980 · Cited by 5,515
Automatic discovery of linear restraints among variables of a program
Cousot, P., & Halbwachs, N. (1978) · Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '78 · doi:10.1145/512760.512770 · Cited by 1,614
Dataflow analysis of array and scalar references
Feautrier, P. (1991) · International Journal of Parallel Programming · doi:10.1007/bf01407931 · Cited by 567
Some efficient solutions to the affine scheduling problem. I. One-dimensional time
Feautrier, P. (1992) · International Journal of Parallel Programming · doi:10.1007/bf01407835 · Cited by 555
The Structure of Computers and Computations
Kuck, D. L. (1978) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 492
Parametric integer programming
Feautrier, P. (1988) · RAIRO - Operations Research · doi:10.1051/ro/1988220302431 · Cited by 378
Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time
Feautrier, P. (1992) · International Journal of Parallel Programming · doi:10.1007/bf01379404 · Cited by 368
Scanning polyhedra with DO loops
Ancourt, C., & Irigoin, F. (1991) · Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming · doi:10.1145/109625.109631 · Cited by 315
A LIBRARY FOR DOING POLYHEDRAL OPERATIONS
WILDE, D. K. (2000) · Parallel Algorithms and Applications · doi:10.1080/01495730008947354 · Cited by 198
Generation of Efficient Nested Loops from Polyhedra
Quilleré, F., Rajopadhye, S., & Wilde, D. (2000) · International Journal of Parallel Programming · doi:10.1023/a:1007554627716 · Cited by 161
Research works printed but not linked: 2
- le fur, 1994, Parcours de polye?dres parame?tre?s avec l'e?limination de Fourier-Motzkin, Technical Report, 2358
- slama, 2000, Vers l'extension du mode?le polye?drique aux transformations irre?gulie?res, CARI'5 International Conference on African Research in Computer Science
Cited by
Items 401–457 of 457
HARDWARE-AWARE TILING OPTIMIZATION FOR MULTI-CORE SYSTEMS
Adamski, D., & Jabłoński, G. (2017) · Computer Science · doi:10.7494/csci.2017.18.2.145
Data layout oriented compilation techniques in vectorization for multi-/many-cores
Xu, S. (2017) · Trinity's Access to Research Output (TARA) (Trinity College Dublin)
Compilation Method of Reconfigurable Cryptographic Processors
Liu, L., Wang, B., & Wei, S. (2018) · Springer eBooks · doi:10.1007/978-981-10-8899-5_4
Analysis and Optimization of Scientific Applications through Set and Relation Abstractions
Tohid, & Mohammed (2017)
Optimising finite-difference methods for PDEs through parameterised time-tiling in DevitoPreprint
Sim, N. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.08299
Texturizing PPCG: Supporting Texture Memory in a Polyhedral Compiler
Patwardhan, A. A., & Upadrasta, R. (2016) · Research Archive of Indian Institute of Technology Hyderabad (Indian Institute of Technology Hyderabad)
Easing parallel programming on heterogeneous systems
Moreton‐Fernandez, A. (2018) · UVaDOC UVaDOC University of Valladolid Documentary Repository (University of Valladolid) · doi:10.35376/10324/31397
Nie, Z., Li, Z., Wang, L., Guo, S., & Dou, Q. (2018) · Communications in computer and information science · doi:10.1007/978-981-13-2423-9_2
Automatic parallelization of "inherently" sequential nested loop programs
Zou, Y., Rajopadhye, S. V., Strout, M., Bohm, A. P. W., & Breidt, F. J. (2007) · Digital Collections of Colorado (Colorado State University) · doi:10.25675/3.022075
Memory Access Classification for Vertical Task Parallelism
Gustedt, J., & Mogé, M. (2019) · Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP) · doi:10.1109/empdp.2019.8671575
Program Generation for Linear Algebra Using Multiple Layers of DSLsPreprint
Spampinato, D. G., Fabregat‐Traver, D., Püschel, M., & Bientinesi, P. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.08613
Leben, J. (2019) · UVic’s Research and Learning Repository (University of Victoria)
Beyond shared memory loop parallelism in the polyhedral model
Yuki, T., Rajopadhye, S. V., Böhm, W., Strout, M. M., & Chong, E. (2007) · Digital Collections of Colorado (Colorado State University) · doi:10.25675/3.023296
Automatic generation of adaptive codes
Schmitt, M. (2019) · theses.fr (ABES) · doi:10.70675/a6e96f95z16c1z4560zbda2zf1737e80a211
Polyhedral Source-to-Source Compile)
Adamski, D. (2016) · Elektronika : konstrukcje, technologie, zastosowania · doi:10.15199/13.2016.12.1
Sushko, S., & Chemeris, A. (2020) · Problems of Informatization and Management · doi:10.18372/2073-4751.64.15151
ASIF: An Internal Representation Suitable for Program Transformation and Parallel Conversion
Kalyur, S., & Nagaraja, G. S. (2021) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-030-79276-3_12
Characterizing Loop Acceleration in Heterogeneous Computing
Biookaghazadeh, S., Ren, F., & Zhao, M. (2021) · IEEE ... International Conference on Cloud Computing · doi:10.1109/cloud53861.2021.00059
Cardoso, J. M. P., Coutinho, J. G. F., & Diniz, P. C. (2013) · Springer eBooks · doi:10.1007/978-1-4614-4894-5_7
Winterstein, F. (2017) · Springer theses · doi:10.1007/978-3-319-53222-6_3
Data coherence analysis and optimization
Sousa, R. C. F. (2017) · doi:10.47749/t/unicamp.2017.984216
Analysis and Optimization of Scientific Applications through Set and Relation Abstractions
Tohid, M. (2017) · Louisiana State University · doi:10.31390/gradschool_dissertations.4404
Loop Controller Area Estimation for Automatic Design Space Exploration
Degryse, T., Devos, H., & Stroobandt, D. (2007) · Ghent University Academic Bibliography (Ghent University)
Programming models to support data science workflows
Ramon-Cortes, C. (2020) · UPCommons institutional repository (Universitat Politècnica de Catalunya) · doi:10.5821/dissertation-2117-330142
A runtime for code offloading on modern heterogeneous platforms
Gonçalves, R. A. (2016) · Digital Library of Theses and Dissertations (Universidade de São Paulo) · doi:10.11606/t.45.2016.tde-20230727-113552
ParameTrick: Coefficient Generalization for Faster Polyhedral Scheduling
Consolaro, G., Razanajato, H., Lossing, N., Barthou, D., Zhang, Z., Ancourt, C., & Bastoul, C. (2024) · HAL
Self-citationProfile guided hybrid compilation
Sampaio, D. N. (2016) · theses.fr (ABES) · doi:10.70675/79e78d88z4cb3z41d6zb1cbz353858e3e7b9
Vanderbruggen, T. (2010)
Performance Portable Tracking of Evolving Surfaces
Yu, W. B. (2011)
Monitahoinen optimointi ohjelmointikielen kääntäjässä
Hirvonen, T. (2024) · Jyväskylä University Digital Archive (University of Jyväskylä)
Trifunović, K. (2011) · theses.fr (ABES) · doi:10.70675/ae2e80ddz5505z493dz8f00zbded07e27060
System-on-chip design flow for Software Defined Radio
田广业 (2011) · theses.fr (ABES) · doi:10.70675/590119b9zfce2z4c5bzb649z835ff3f2bcfe
Utilisation du modèle polyédrique pour la synthèse d'architectures pipelinées
Morvan, A. (2013) · theses.fr (ABES) · doi:10.70675/cd7808c5z07b6z4708zaf4dz79618f152604
Automatic parallelization of affine loops using dependence and cache analysis in a binary rewriter
Kotha, A. (2013) · University Libraries (University of Maryland)
Interactive Program Restructuring
Zinenko, O. (2016) · theses.fr (ABES) · doi:10.70675/6c07b473z153bz4497za14dz578d294b138d · Cited by 2
Adaptation automatique et semi-automatique des optimisations de programmes
Bagnères, L. (2016) · theses.fr (ABES) · doi:10.70675/4c050d35z5565z4ca8z9993z71d9be91d224
Runtime optimization of binary through vectorization transformations
Hallou, N. (2017) · theses.fr (ABES) · doi:10.70675/95d71994z104dz4d0dz9835zf4a7adab2954
Tracking haute fréquence pour architectures SIMD : optimisation de la reconstruction LHCb
Lemaitre, F. (2019) · theses.fr (ABES) · doi:10.70675/68b8abf8z57bbz41bdz8336z62acd143ee4f · Cited by 1
Gouin, F. (2019) · theses.fr (ABES) · doi:10.70675/28ed0eb6z64d0z41e7za4ffz7638663da061
Génération de code polyédrique efficace : vers plus de parallélisme et moins de contrôle
Razanajato, H. (2020) · theses.fr (ABES) · doi:10.70675/ceece872z48a1z47e3zba4ez2753b8df5fe5
Compiling Trees : Combining Data Layouts and the Polyhedral Model
Iannetta, P. (2022) · theses.fr (ABES) · doi:10.70675/43bc0670zd709z4cffza0e2z2455449e95d0
Tollenaere, N. (2022) · theses.fr (ABES) · doi:10.70675/f94898efz24f8z4784zbc06z2b1f62951a91
Translation validation of tensor compilers
Clément, B. (2022) · theses.fr (ABES) · doi:10.70675/0467c7a2ze4a9z4754z9e5eze9e51447e92d
Automatic Source-to-Source Optimizations using Machine Learning
Berezov, M. (2022) · theses.fr (ABES) · doi:10.70675/ba1152c7zadfaz4d0fzb08fz0f218d038f2a
Optimized code generation of parallel and polyhedral loop nests using MLIR
Thangamani, A. (2024) · theses.fr (ABES) · doi:10.70675/b30b02b1zc799z4a1cz8285z44133b3a4e3b
Automatic generation of performance model for heterogeneous architectures
Derumigny, N. (2023) · theses.fr (ABES) · doi:10.70675/3da18693z2629z44c3z8134z3408115e531d
Configurable Polyhedral Scheduling for All-Scenario Deep Learning Compilers
Consolaro, G. (2024) · theses.fr (ABES) · doi:10.70675/d6848fa8z8279z4addzbe70zd3aeb8bf1959
EvoTADASHI: Genetic Programming for High-Performance Code Optimization
Batista, J. E., Vatai, E., Валентинович, Д. А., & Wahib, M. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-23604-3_3
Parametric Mappings for Distributed-Memory Tensor Computations
Wu, B., & Kong, M. (2026) · International Conference on Supercomputing · doi:10.1145/3797905.3800508
Bielecki, W., Pałkowski, M., & Klimek, T. (2010) · Metody Informatyki Stosowanej
Bielecki, W., Kraska, K., & Poliwoda, M. (2012) · PRZEGLĄD ELEKTROTECHNICZNY
Metadata
- Authors
- Bastoul, C.
- Affiliations
- Université de Versailles Saint-Quentin-en-Yvelines (FR)
- Corresponding author
- Bastoul, C.
- ORCID
- Bastoul, C.
- Venue
- Proceedings. 13th International Conference on Parallel Architecture and Compilation Techniques, 2004. PACT 2004.
- Publisher
- IEEE
- Published
- 2004-11-08
- Pages
- 7-16
- ISSN
- 1089-795X (ISSN-L)
- OpenAlex
- W2076485607
- Cited by
- 447
- References
- 30
- Citations by year
- 2026: 2 · 2025: 4 · 2024: 4 · 2023: 5 · 2022: 6 · 2021: 20 · 2020: 12 · 2019: 19 · 2018: 18 · 2017: 34 · 2016: 39 · 2015: 43 · 2014: 37 · 2013: 33 · 2012: 39
- FWCI
- 5.84
- Type
- conference paper
- Language
- en
- Open access
- green
- hal.science
- Licence
- other-oa
- Locations
- International Conference on Parallel Architectures and Compilation Techniques (PACT) (publishedVersion)
- HAL (submittedVersion, other-oa)
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Hardware and Architecture › Embedded Systems Design Techniques
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Keywords
- polyhedral models, code generation, program transformation, automatic parallelization, program size, optimizing compilers, feedback-directed optimization
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.