A practical automatic polyhedral parallelizer and locality optimizer
The DOI matches its Crossref record; 50 of the 50 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
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
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
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
Automated empirical optimizations of software and the ATLAS project
Clint Whaley, R., Petitet, A., & Dongarra, J. J. (2001) · Parallel Computing · doi:10.1016/s0167-8191(00)00087-9 · Cited by 1,317
The Omega test: a fast and practical integer programming algorithm for dependence analysis
Pugh, W. (1991) · Proceedings of the 1991 ACM/IEEE conference on Supercomputing - Supercomputing '91 · doi:10.1145/125826.125848 · Cited by 750
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
Cited by
Tensor Comprehensions: Framework-Agnostic High-Performance Machine Learning Abstractions
Vasilache, N., Zinenko, O., Theodoridis, T., Goyal, P., DeVito, Z., Moses, W. S., Verdoolaege, S., Adams, A., & Cohen, A. (2018) · arXiv · doi:10.48550/arxiv.1802.04730 · Cited by 548
MLIR: Scaling Compiler Infrastructure for Domain Specific Computation
Lattner, C., Amini, M., Bondhugula, U., Cohen, A., Davis, A., Pienaar, J., Riddle, R., Shpeisman, T., Vasilache, N., & Zinenko, O. (2021) · 2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO) · doi:10.1109/cgo51591.2021.9370308 · Cited by 541
Self-citationPolyhedral parallel code generation for CUDA
Verdoolaege, S., Carlos Juega, J., Cohen, A., Ignacio Gómez, J., Tenllado, C., & Catthoor, F. (2013) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/2400682.2400713 · Cited by 382
POLLY — PERFORMING POLYHEDRAL OPTIMIZATIONS ON A LOW-LEVEL INTERMEDIATE REPRESENTATION
GROSSER, T., GROESSLINGER, A., & LENGAUER, C. (2012) · Parallel Processing Letters · doi:10.1142/s0129626412500107 · Cited by 355
Memory-centric accelerator design for Convolutional Neural Networks
Peemen, M., Setio, A. A. A., Mesman, B., & Corporaal, H. (2013) · 2013 IEEE 31st International Conference on Computer Design (ICCD) · doi:10.1109/iccd.2013.6657019 · Cited by 332
Christen, M., Schenk, O., & Burkhart, H. (2011) · 2011 IEEE International Parallel & Distributed Processing Symposium · doi:10.1109/ipdps.2011.70 · Cited by 311
Understanding Reuse, Performance, and Hardware Cost of DNN Dataflow: A Data-Centric Approach
Kwon, H., Chatarasi, P., Pellauer, M., Parashar, A., Sarkar, V., & Krishna, T. (2019) · Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture · doi:10.1145/3352460.3358252 · Cited by 301
Machine Learning for Microcontroller-Class Hardware: A Review
Saha, S. S., Sandha, S. S., & Srivastava, M. (2022) · IEEE Sensors Journal · doi:10.1109/jsen.2022.3210773 · Cited by 253
The Polyhedral Model Is More Widely Applicable Than You Think
Benabderrahmane, M.-W., Pouchet, L.-N., Cohen, A., & Bastoul, C. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-11970-5_16 · Cited by 232
“– Pluto(5) is an automatic parallelization tool based on the polyhedral model [5].”
BackgroundMethodInfluentialAn auto-tuning framework for parallel multicore stencil computations
Kamil, S., Chan, C., Oliker, L., Shalf, J., & Williams, S. (2010) · 2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS) · doi:10.1109/ipdps.2010.5470421 · Cited by 209
Louboutin, M., Lange, M., Luporini, F., Kukreja, N., Witte, P. A., Herrmann, F. J., Velesko, P., & Gorman, G. J. (2019) · Geoscientific Model Development · doi:10.5194/gmd-12-1165-2019 · Cited by 207
“Devito aims to combine performance benefits of dedicated stencil frameworks (Bondhugula et al., 2008; Tang et al., 2011; Henretty et al., 2013; Yount, 2015) with the expressiveness of symbolic PDE-solving DSLs (Logg et al., 2012; Rathgeber et al., 2015) through automated code generation and…”
BackgroundPolyMage: Automatic Optimization for Image Processing Pipelines
Mullapudi, R. T., Vasista, V., & Bondhugula, U. (2015) · Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/2694344.2694364 · Cited by 160
“Stencil optimization efforts have extensively focused on improving locality and parallelism for time-iterated stencil computations, resulting in parallelogram [8, 43, 44], diamond [5], split [22], and hybrid hexagonal [21] tiling techniques.”
BackgroundMethodSelf-citation
Metadata
- Authors
- Bondhugula, U., Hartono, A., Ramanujam, J., & Sadayappan, P.
- Venue
- Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation
- Publisher
- ACM
- Published
- 2008-06-07
- Pages
- 101-113
- ISSN
- 1531-7102 (ISSN-L)
- OpenAlex
- W2034761517
- Cited by
- 880
- References
- 50
- FWCI
- 18.30
- Type
- conference paper
- Language
- en
- Open access
- closed
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.