CoChat

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

Crossref · 10.1145/1379022.1375595

Cites

41 of 41 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Citations

Cites

Research works printed but not linked: 13

  1. 10.5555/1025127.1025992 · doi:10.5555/1025127.1025992
  2. 10.5555/1765931.1765962 · doi:10.5555/1765931.1765962
  3. 10.5555/1788374.1788386 · doi:10.5555/1788374.1788386
  4. 10.5555/556139 · doi:10.5555/556139
  5. 10.1007/BF01407835 · DOI · Paper page
  6. Goumas G., 2002, Code Generation Methods for Tiling Transformations. J. of Information Science and Engineering, 18, 667
  7. Kelly W., 1995, Intl. Symp. on the frontiers of massively parallel computation, 332
  8. Norris B., 2007, Annotations for performance and productivity
  9. Pop S., 2006, Proc. of the 4th GCC Developper?s summit
  10. Schreiber R., 1990, Automatic blocking of nested loops. Technical report
  11. Whaley R., 2000, Parallel Computing
  12. Wilde D. K., 1993, IRISA
  13. 10.5555/353939 · doi:10.5555/353939

Cited by

See all 249

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.