The DOI matches its Crossref record; 50 of the 50 references it cites were found in a registry or an index.
A practical automatic polyhedral parallelizer and locality optimizer
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
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
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
Semi-Automatic Composition of Loop Transformations for Deep Parallelism and Memory Hierarchies
Girbal, S., Vasilache, N., Bastoul, C., Cohen, A., Parello, D., Sigler, M., & Temam, O. (2006) · International Journal of Parallel Programming · doi:10.1007/s10766-006-0012-3 · Cited by 215
A LIBRARY FOR DOING POLYHEDRAL OPERATIONS
WILDE, D. K. (2000) · Parallel Algorithms and Applications · doi:10.1080/01495730008947354 · Cited by 198
Bondhugula, U., Baskaran, M., Krishnamoorthy, S., Ramanujam, J., Rountev, A., & Sadayappan, P. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78791-4_9 · Cited by 196
Self-citationNew tiling techniques to improve cache temporal locality
Song, Y., & Li, Z. (1999) · Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation · doi:10.1145/301618.301668 · Cited by 194
An affine partitioning algorithm to maximize parallelism and minimize communication
Lim, A. W., Cheong, G. I., & Lam, M. S. (1999) · Proceedings of the 13th international conference on Supercomputing · doi:10.1145/305138.305197 · Cited by 181
A comparison of empirical and model-driven optimization
Yotov, K., Li, X., Ren, G., Cibulskis, M., DeJong, G., Garzaran, M., Padua, D., Pingali, K., Stodghill, P., & Wu, P. (2003) · ACM SIGPLAN Notices · doi:10.1145/780822.781140 · Cited by 165
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
Tiling multidimensional iteration spaces for multicomputers
Ramanujam, J., & Sadayappan, P. (1992) · Journal of Parallel and Distributed Computing · doi:10.1016/0743-7315(92)90027-k · Cited by 161
Self-citationMaximizing parallelism and minimizing synchronization with affine partitions
Lim, A. W., & Lam, M. S. (1998) · Parallel Computing · doi:10.1016/s0167-8191(98)00021-0 · Cited by 147
Iterative optimization in the polyhedral model: part ii, multidimensional time
Pouchet, L.-N., Bastoul, C., Cohen, A., & Cavazos, J. (2008) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/1375581.1375594 · Cited by 147
Blocking and array contraction across arbitrarily nested loops using affine partitioning
Lim, A. W., Liao, S.-W., & Lam, M. S. (2001) · Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming · doi:10.1145/379539.379586 · Cited by 142
Implicit and explicit optimizations for stencil computations
Kamil, S., Datta, K., Williams, S., Oliker, L., Shalf, J., & Yelick, K. (2006) · Proceedings of the 2006 workshop on Memory system performance and correctness · doi:10.1145/1178597.1178605 · Cited by 130
Boulet, P., Darte, A., Risset, T., & Robert, Y. L. (1994) · Integration · doi:10.1016/0167-9260(94)90019-1 · Cited by 130
Iterative Optimization in the Polyhedral Model: Part I, One-Dimensional Time
Pouchet, L.-N., Bastoul, C., Cohen, A., & Vasilache, N. (2007) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1109/cgo.2007.21 · Cited by 122
A Note on Chernikova's algorithm
Verge, H. L. (1992) · OpenGrey (Institut de l'Information Scientifique et Technique) · Cited by 116
Automatic Parallelization of Loop Programs for Distributed Memory Architectures
Griebl, M. (2004) · Cited by 115
Facilitating the search for compositions of program transformations
Cohen, A., Sigler, M., Girbal, S., Temam, O., Parello, D., & Vasilache, N. (2005) · International Conference on Supercomputing · doi:10.1145/1088149.1088169 · Cited by 104
Code generation for multiple mappings
Kelly, W., Pugh, W., & Rosser, E. (2002) · Symposium on the Frontiers of Massively Parallel Computation (Frontiers) · doi:10.1109/fmpc.1995.380437 · Cited by 97
Parameterized tiled loops for free
Renganarayanan, L., Kim, D., Rajopadhye, S. V., & Strout, M. M. (2007) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/1250734.1250780 · Cited by 94
A comparison of empirical and model-driven optimization
Yotov, K., Li, X., Ren, G., Cibulskis, M., DEJONG, G. F., Garzarán, M. J., Padua, D., Pingali, K. K., Stodghill, P. V., & Wu, P. (2003) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/781131.781140 · Cited by 87
A singular loop transformation framework based on non-singular matrices
Li, W., & Pingali, K. K. (1994) · International Journal of Parallel Programming · doi:10.1007/bf02577874 · Cited by 86
Polyhedral Code Generation in the Real World
Vasilache, N., Bastoul, C., & Cohen, A. (2006) · Lecture notes in computer science · doi:10.1007/11688839_16 · Cited by 83
Loop parallelization algorithms: From parallelism extraction to code generation
Boulet, P., Darte, A., Silber, G.-A., & Vivien, F. (1998) · Parallel Computing · doi:10.1016/s0167-8191(98)00020-9 · Cited by 83
Multi-level tiling: M for the price of one
Kim, D., Renganarayanan, L., Rostron, D., Rajopadhye, S. V., & Strout, M. M. (2007) · ACM/IEEE Conference on Supercomputing (SC) · doi:10.1145/1362622.1362691 · Cited by 80
Communication-Minimal Tiling of Uniform Dependence Loops
Xue, J. (1997) · Journal of Parallel and Distributed Computing · doi:10.1006/jpdc.1997.1310 · Cited by 72
Combining Retiming and Scheduling Techniques for Loop Parallelization and Loop Tiling
Darte, A., Silber, G.-A., & Vivien, F. (1997) · Parallel Processing Letters · doi:10.1142/s0129626497000383 · Cited by 59
Selecting tile shape for minimal execution time
Högstedt, K., Carter, L., & Ferrante, J. (1999) · ACM Symposium on Parallel Algorithms and Architectures (SPAA) · doi:10.1145/305619.305641 · Cited by 56
Optimal Fine and Medium Grain Parallelism Detection in Polyhedral Reduced Dependence Graphs
Darte, A., & Vivien, F. (1997) · International Journal of Parallel Programming · doi:10.1023/a:1025168022993 · Cited by 50
Vasilache, N., Bastoul, C., Cohen, A., & Girbal, S. (2006) · International Conference on Supercomputing · doi:10.1145/1183401.1183448 · Cited by 48
Code generation in the polytope model
Griebl, M., Lengauer, C., & Wetzel, S. (1998) · doi:10.5555/522344.825673 · Cited by 44
On time optimal supernode shape
Hodzic, E., & Shang, W. (2002) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2002.1158261 · Cited by 36
Synthesizing Transformations for Locality Enhancement of Imperfectly-Nested Loop Nests
Ahmed, N., Mateev, N., & Pingali, K. K. (2001) · International Journal of Parallel Programming · doi:10.1023/a:1012293814832 · Cited by 34
Andonov, R., Balev, S., Rajopadhye, S. V., & Yanev, N. (2003) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2003.1233716 · Cited by 32
Transforming Complex Loop Nests for Locality
Yi, Q., Kennedy, K., & Adve, V. (2004) · The Journal of Supercomputing · doi:10.1023/b:supe.0000011386.69245.f5 · Cited by 23
Cited by
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
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.