A practical automatic polyhedral parallelizer and locality optimizer
The DOI matches its Crossref record; 41 of the 41 references it cites were found in a registry or an index.
Abstract
We present the design and implementation of an automatic polyhedral source-to-source transformation framework that can optimize regular programs (sequences of possibly imperfectly nested loops) for parallelism and locality simultaneously. Through this work, we show the practicality of analytical model-driven automatic transformation in the polyhedral model -- far beyond what is possible by current production compilers. Unlike previous works, our approach is an end-to-end fully automatic one driven by an integer linear optimization framework that takes an explicit view of finding good ways of tiling for parallelism and locality using affine transformations. The framework has been implemented into a tool to automatically generate OpenMP parallel code from C program sections. Experimental results from the tool show very high speedups for local and parallel execution on multi-cores over state-of-the-art compiler frameworks from the research community as well as the best native production compilers. The system also enables the easy use of powerful empirical/iterative optimization for general arbitrarily nested loop sequences.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
A generalized inverse for matrices
Penrose, R. (1955) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100030401 · Cited by 4,551
Theory of Linear and Integer Programming
Smith, D. K. (1987) · Journal of the Operational Research Society · doi:10.1057/jors.1987.94 · Cited by 2,708
A data locality optimizing algorithm
Wolf, M. E., & Lam, M. S. (1991) · Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation - PLDI '91 · doi:10.1145/113445.113449 · Cited by 1,331
Automatic translation of FORTRAN programs to vector form
Allen, R., & Kennedy, K. (1987) · ACM Transactions on Programming Languages and Systems · doi:10.1145/29873.29875 · Cited by 734
A loop transformation theory and an algorithm to maximize parallelism
Wolf, M. E., & Lam, M. S. (1991) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/71.97902 · Cited by 643
A practical algorithm for exact array dependence analysis
Pugh, W. (1992) · Communications of the ACM · doi:10.1145/135226.135233 · Cited by 568
Dataflow analysis of array and scalar references
Feautrier, P. (1991) · International Journal of Parallel Programming · doi:10.1007/bf01407931 · Cited by 567
Irigoin, F., & Triolet, R. (1988) · Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '88 · doi:10.1145/73560.73588 · Cited by 564
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
Code generation in the polyhedral model is easier than you think
Bastoul, C. (2004) · Proceedings. 13th International Conference on Parallel Architecture and Compilation Techniques, 2004. PACT 2004. · doi:10.1109/pact.2004.1342537 · Cited by 447
Research works printed but not linked: 13
- 10.5555/1025127.1025992 · doi:10.5555/1025127.1025992
- 10.5555/1765931.1765962 · doi:10.5555/1765931.1765962
- 10.5555/1788374.1788386 · doi:10.5555/1788374.1788386
- 10.5555/556139 · doi:10.5555/556139
- 10.1007/BF01407835 · DOI · Paper page
- Goumas G., 2002, Code Generation Methods for Tiling Transformations. J. of Information Science and Engineering, 18, 667
- Kelly W., 1995, Intl. Symp. on the frontiers of massively parallel computation, 332
- Norris B., 2007, Annotations for performance and productivity
- Pop S., 2006, Proc. of the 4th GCC Developper?s summit
- Schreiber R., 1990, Automatic blocking of nested loops. Technical report
- Whaley R., 2000, Parallel Computing
- Wilde D. K., 1993, IRISA
- 10.5555/353939 · doi:10.5555/353939
Cited by
Items 201–249 of 249
Nested Loop Parallelization Using Polyhedral Optimization in High-Level Synthesis
Suda, A., Takase, H., Takagi, K., & Takagi, N. (2014) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.e97.a.2498
Recovering memory access patterns of executable programs
Ketterlin, A., & Clauss, P. (2012) · Science of Computer Programming · doi:10.1016/j.scico.2012.08.002
Battery-aware mapping optimization of loop nests for CGRAs
Yu, P., Yin, S., Liu, L., & Wei, S. (2015) · Asia and South Pacific Design Automation Conference (ASP-DAC) · doi:10.1109/aspdac.2015.7059103
Parallel Data Reuse Theories for OpenMP and OpenTM Applications
Wu, J., Yang, X., Liu, G., & Tang, Y. (2011) · Journal of Software · doi:10.3724/sp.j.1001.2010.03696
Free Scheduling of Tiles Based on the Transitive Closure of Dependence Graphs
Bielecki, W., Pałkowski, M., & Klimek, T. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-32152-3_13
Extending Explicit Management of SMMHS to OpenMP for Heterogeneous Architectures
Liu, X., Zhao, R., Yao, Y., & Huang, P.-F. (2013) · Lecture notes in electrical engineering · doi:10.1007/978-1-4614-4981-2_242
A Survey of Loop Parallelization: Models, Approaches, and Recent Developments
Hong, Y., Deng, H., & Zou, C. (2016) · International Journal of Grid and Distributed Computing · doi:10.14257/ijgdc.2016.9.11.12
Synchronization-Free Automatic Parallelization for Arbitrarily Nested Affine Loops
Klimek, T., Pałkowski, M., & Bielecki, W. (2016) · International Symposium on Computer Architecture and High Performance Computing Workshops (SBAC-PADW) · doi:10.1109/sbac-padw.2016.16
Tamarit, S., Vigueras, G., Carro, M., & Mariño, J. (2017) · Springer eBooks · doi:10.1007/978-3-319-56702-0_7
Parallel Cache Efficient Algorithm and Implementation of Needleman-Wunsch Global Sequence Alignment
Pałkowski, M., Siedlecki, K., & Bielecki, W. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-91262-2_19
Compilation Method of Reconfigurable Cryptographic Processors
Liu, L., Wang, B., & Wei, S. (2018) · Springer eBooks · doi:10.1007/978-981-10-8899-5_4
A High Arithmetic Intensity Krylov Subspace Method Based on Stencil Compiler Programs
Donfack, S., Sanan, P., Schenk, O., Reps, B., & Vanroose, W. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-97136-0_1
Transitive Closure Based Schedule of Loop Nest Statement Instances
Bielecki, W., & Pałkowski, M. (2018) · Advances in intelligent systems and computing · doi:10.1007/978-3-030-03314-9_11
Energy Consumption Analysis of the Nussinov RNA Folding Implementations
Pałkowski, M. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-20915-5_22
IR-Level Dynamic Data Dependence Using Abstract Interpretation Towards Speculative Parallelization
Omar, R., El-Mahdy, A., & Rohou, E. (2020) · IEEE Access · doi:10.1109/access.2020.2997715
CLAM: Compiler Leasing of Accelerator Memory
Chen, D., Ding, C., & Patru, D. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-72789-5_7 · Cited by 1
Tanase, A.-P., Hannig, F., & Teich, J. (2018) · Springer eBooks · doi:10.1007/978-3-319-73909-0_3
DeLICM: scalar dependence removal at zero memory cost
Kruse, M., & Grosser, T. (2018) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1145/3179541.3168815
Winterstein, F. (2017) · Springer theses · doi:10.1007/978-3-319-53222-6_3
Khan, S., Chatterjee, B., & Pande, S. (2022) · International Conference on Supercomputing · doi:10.1145/3524059.3532393
(2022) · Elsevier eBooks · doi:10.1016/b978-0-12-815412-0.00023-1
Kolganov, A. S., & Гусев, Г. Д. (2022) · Vyčislitelʹnye metody i programmirovanie · doi:10.26089/nummet.v23r418
Optimizing Cache Accesses with Tensor Memory Format Search for Transformers in TVM
He, X., Gao, X., Zhao, J., Gao, C., & Ye, K. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-23498-9_4
CustomHalide – A new plugin of clang for loop optimization
Jun, W., Suo, Q., Yan, D., & Yue, C. (2023) · International Conference on Computing and Artificial Intelligence (ICCAI) · doi:10.1145/3594315.3594372
Wang, X.-Y., Shen, J.-Y., & Liao, S.-W. (2023) · Research Square · doi:10.21203/rs.3.rs-3274775/v1 · Cited by 1
Taking RNA-RNA Interaction to Machine Peak
Mondal, C., & Rajopadhye, S. V. (2024) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2024.3380443
Leveraging the High Bandwidth of Last-Level Cache for HPC Seismic Imaging Applications
Plotnitskii, P., Beaurepaire, L., Qu, L., Akbudak, K., Ltaief, H., & Keyes, D. E. (2024) · Platform for Advanced Scientific Computing Conference (PASC) · doi:10.1145/3659914.3659936
A Priori Loop Nest Normalization: Automatic Loop Scheduling in Complex Applications
Trümper, L., Schaad, P., Ates, B., Calotoiu, A., Copik, M., & Hoefler, T. (2025) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1145/3696443.3708951
Optimizing Compute Core Assignment for Dynamic Batch Inference in AI Inference Accelerator
Liou, Z.-W., & Hong, D. (2025) · ACM Symposium on Applied Computing · doi:10.1145/3672608.3707809
NPDP programming for RISC multi-core processors
Pałkowski, M., & Grużewski, M. (2025) · Annals of Computer Science and Information Systems · doi:10.15439/2025f8280
Grużewski, M., & Pałkowski, M. (2025) · Procedia Computer Science · doi:10.1016/j.procs.2025.09.462
A Data-driven Analysis of Code Optimizations
Hakimi, Y., & Baghdadi, R. (2025) · IEEE/ACS International Conference on Computer Systems and Applications (AICCSA) · doi:10.1109/aiccsa66935.2025.11315210
CHEHAB: Automatic Compiler Code Optimization for Fully Homomorphic Encryption
Seddiki, A., Mohammed, A., Hebbal, Z., Chabounia, A., Chielle, E., Benatchba, K., Challal, Y., Menacer, D. E., Maniatakos, M., & Baghdadi, R. (2026) · ACM SIGPLAN International Conference on Compiler Construction (CC) · doi:10.1145/3771775.3786269
CHEHAB RL: Learning to Optimize Fully Homomorphic Encryption Computations
Sefsaf, B., Dandani, A., Seddiki, A., Mohammed, A., Chielle, E., Maniatakos, M., & Baghdadi, R. (2026) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3779212.3790138
Efficient code generation for hardware accelerators by refining partially specified implementation
Beaugnon, U. (2019) · theses.fr (ABES) · doi:10.70675/d5616431z1928z4641z8afcz4ae3cc485807
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
Tiling-Aware Vectorization Framework for Perfect Loop Nests in MLIR
Hong, C., Liu, Z., Zhong, H., & Zhang, H. (2026) · Lecture notes in computer science · doi:10.1007/978-981-95-8399-7_30
Automatic Source-to-Source Optimizations using Machine Learning
Berezov, M. (2022) · theses.fr (ABES) · doi:10.70675/ba1152c7zadfaz4d0fzb08fz0f218d038f2a
Dynamic Operator Fusion and Vectorized Code Generation for Custom Tensor Languages in MLIR
Fu, A., & Liang, D. (2026) · International Conference on Electronics Technology and Artificial Intelligence (ETAI) · doi:10.1109/etai68332.2026.11485267
PLCG: Parametric Loop Code Generator for Loop Transformation Optimization Benchmarking
Zhi, Y., Wu, Q., Han, X., & Cai, M. (2026) · IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS) · doi:10.1109/ispass69572.2026.00057
RAPO: Retrieval-Augmented Phase Ordering
Yang, J., Lee, J.-H., Hong, Y., & Sung, H. (2026) · ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES) · doi:10.1145/3814943.3816172
Pałkowski, M., Iserte, S., Olas, T., Grużewski, M., & Wyrzykowski, R. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-29915-4_48
AutoOMP: A Lightweight Source-to-Source Automatic Performance Optimization Tool for Fortran Programs
Jiang, H. (2026) · International Conference on Intelligent Communications and Computing (ICICC) · doi:10.1109/icicc71012.2026.11637652
Kolganov, A. S., & Nikitin, O. Y. (2026) · Vyčislitelʹnye metody i programmirovanie · doi:10.26089/nummet.v27r331
Polyhedral Optimizations of RNA–RNA Interaction Predictions—Case Study on Domain-Specific Language
Varadarajan, S. (2026) · Methods in molecular biology · doi:10.1007/978-1-0716-5567-2_13
Metadata
- Authors
- Bondhugula, U., Hartono, A., Ramanujam, J., & Sadayappan, P.
- Affiliations
- The Ohio State University (US)
- Louisiana State University (US)
- Venue
- ACM SIGPLAN Notices
- Published
- 2008-05-30
- Volume
- 43
- Issue
- 6
- Pages
- 101-113
- ISSN
- 0362-1340 (ISSN-L)
- 1558-1160
- OpenAlex
- W3151489216
- Cited by
- 248
- References
- 41
- Citations by year
- 2026: 13 · 2025: 11 · 2024: 7 · 2023: 15 · 2022: 16 · 2021: 25 · 2020: 19 · 2019: 19 · 2018: 28 · 2017: 24 · 2016: 18 · 2015: 13 · 2014: 9 · 2013: 8 · 2012: 9
- FWCI
- 9.67
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- ACM SIGPLAN Notices (publishedVersion)
- Civil War Book Review (submittedVersion)
- 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 › Computer Graphics and Computer-Aided Design › Computer Graphics and Visualization Techniques
- Keywords
- polyhedral models, automatic parallelization, locality optimization, source-to-source translation, loop tiling, integer linear programming, affine transformation, nested loops, compiler 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.