Implicit and explicit optimizations for stencil computations
Open accessThe DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Abstract
Stencil-based kernels constitute the core of many scientific applications on block-structured grids. Unfortunately, these codes achieve a low fraction of peak performance, due primarily to the disparity between processor and main memory speeds. We examine several optimizations on both the conventional cache-based memory systems of the Itanium 2, Opteron, and Power5, as well as the heterogeneous multicore design of the Cell processor. The optimizations target cache reuse across stencil sweeps, including both an implicit cache oblivious approach and a cache-aware algorithm blocked to match the cache structure. Finally, we consider stencil computations on a machine with an explicitly-managed memory hierarchy, the Cell processor. Overall, results show that a cache-aware approach is significantly faster than a cache oblivious approach and that the explicitly managed memory on Cell is more efficient: Relative to the Power5, it has almost 2x more memory bandwidth and is 3.7x faster.
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
Adaptive mesh refinement for hyperbolic partial differential equations
Berger, M. J., & Oliger, J. (1984) · Journal of Computational Physics · doi:10.1016/0021-9991(84)90073-1 · Cited by 2,106
Adaptive Mesh Refinement for Hyperbolic Partial Differential Equations
Berger, M. J., & Oliger, J. (1983) · doi:10.21236/ada130162 · Cited by 1,523 · cited 1×
“Stencil computations perform global sweeps through data structures that are typically much larger than the capacity of available data caches.”
BackgroundThe potential of the cell processor for scientific computing
Williams, S., Shalf, J., Oliker, L., Kamil, S., Husbands, P., & Yelick, K. (2006) · Proceedings of the 3rd conference on Computing frontiers · doi:10.1145/1128022.1128027 · Cited by 309 · cited 2×
“A 4 step time skewed version similar to the blocking algorithm developed by Sellappa and Chatterjee [9] was demonstrated in [11].”
MethodSelf-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 · cited 1×
“More recently, Frigo et al [4] showed the potential of cache oblivious optimizations for improving stencil kernel performance.”
BackgroundFrigo, M., Leiserson, C. E., Prokop, H., & Ramachandran, S. (2012) · ACM Transactions on Algorithms · doi:10.1145/2071379.2071383 · Cited by 192
Improving locality and parallelism in nested loops
Wolf, M. E. (1992) · Cited by 157
Impact of modern memory subsystems on cache optimizations for stencil computations
Kamil, S. A., Husbands, P., Oliker, L., Shalf, J. M., & Yelick, K. (2005) · Workshop on Memory System Performance and Correctness · doi:10.1145/1111583.1111589 · Cited by 124 · cited 2×
“Initial work by Wolf [12] showed loop skewing generally did not improve performance, but subsequent studies by McCalpin [6] et al and others [10, 13] have shown a mod-ified form of loop skewing called time skewing can improve performance for many stencil kernels.”
BackgroundSelf-citationUsing time skewing to eliminate idle time due to memory bandwidth and network limitations
Wonnacott, D. (2002) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2000.845979 · Cited by 118 · cited 1×
“More recently, Frigo et al [4] showed the potential of cache oblivious optimizations for improving stencil kernel performance.”
BackgroundEvaluation of Cache-based Superscalar and Cacheless Vector Architectures for Scientific Computations
Oliker, L., Canning, A., Carter, J. T., Shalf, J. M., Skinner, D. E., Ethier, S., Biswas, R., Djomehri, J., & Wijngaart, R. F. V. D. (2003) · ACM/IEEE Conference on Supercomputing (SC) · doi:10.1145/1048935.1050213 · Cited by 51
Self-citationCache-Efficient Multigrid Algorithms
Sellappa, S., & Chatterjee, S. (2004) · The International Journal of High Performance Computing Applications · doi:10.1177/1094342004041295 · Cited by 49
Research works printed but not linked: 1
- 10.5555/846234.849346 · doi:10.5555/846234.849346
Cited by
A practical automatic polyhedral parallelizer and locality optimizer
Bondhugula, U., Hartono, A., Ramanujam, J., & Sadayappan, P. (2008) · Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1375581.1375595 · Cited by 880
3D finite difference computation on GPUs using CUDA
Micikevicius, P. (2009) · Proceedings of 2nd Workshop on General Purpose Processing on Graphics Processing Units · doi:10.1145/1513895.1513905 · Cited by 520
“These are similar to stencil approaches described for Cell processors in [1][4].”
MethodStencil computation optimization and auto-tuning on state-of-the-art multicore architectures
Datta, K., Murphy, M., Volkov, V. M., Williams, S., Carter, J. T., Oliker, L., Patterson, D. A., Shalf, J. M., & Yelick, K. (2008) · IEEE International Conference on High Performance Computing, Data, and Analytics · doi:10.5555/1413370.1413375 · Cited by 462
Self-citationTang, Y., Chowdhury, R. A., Kuszmaul, B. C., Luk, C.-K., & Leiserson, C. E. (2011) · Proceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures · doi:10.1145/1989493.1989508 · Cited by 337
“The Berkeley autotuner [8,26,41] focuses on optimizing the performance of stencil kernels by automatically selecting tuning parameters.”
BackgroundMethodProgram synthesis by sketching
Bodík, R., & Solar-Lezama, A. (2008) · UC Berkeley · Cited by 388
Metadata
- Authors
- Kamil, S., Datta, K., Williams, S., Oliker, L., Shalf, J., & Yelick, K.
- Affiliations
- Lawrence Berkeley National Laboratory (US)
- University of California, Berkeley (US)
- Venue
- Proceedings of the 2006 workshop on Memory system performance and correctness
- Publisher
- ACM
- Published
- 2006-10-22
- Pages
- 51-60
- OpenAlex
- W2129471558
- Cited by
- 130
- References
- 11
- Citations by year
- 2026: 1 · 2025: 1 · 2024: 1 · 2023: 1 · 2021: 4 · 2020: 5 · 2019: 4 · 2018: 4 · 2017: 12 · 2016: 7 · 2015: 10 · 2014: 6 · 2013: 6 · 2012: 11
- FWCI
- 7.49
- Type
- conference paper
- Language
- en
- Open access
- green
- escholarship.org
- Locations
- eScholarship (California Digital Library) (submittedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computer Graphics and Visualization Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Matrix Theory and Algorithms
- Keywords
- stencil computations, cache-aware algorithms, cache-oblivious algorithms, memory hierarchy, Cell processor, multi-core processors, block-structured grids, memory bandwidth, cache reuse, Itanium 2
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Implicit and explicit optimizations for stencil computations. https://app.cochat.ai/papers/10.1145/1178597.1178605
- The paper
- Kamil, S., Datta, K., Williams, S., Oliker, L., Shalf, J., & Yelick, K. (2006). Implicit and explicit optimizations for stencil computations. Proceedings of the 2006 workshop on Memory system performance and correctness. https://doi.org/10.1145/1178597.1178605
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.