Article

Cache oblivious stencil computations

Authors:

Matteo Frigo,

Volker StrumpenAuthors Info & Claims

ICS '05: Proceedings of the 19th annual international conference on Supercomputing

Pages 361 - 366

https://doi.org/10.1145/1088149.1088197

Published: 20 June 2005 Publication History

Get Access

Abstract

We present a cache oblivious algorithm for stencil computations, which arise for example in finite-difference methods. Our algorithm applies to arbitrary stencils in n-dimensional spaces. On an "ideal cache" of size Z, our algorithm saves a factor of Θ(Z^1/n) cache misses compared to a naive algorithm, and it exploits temporal locality optimally throughout the entire memory hierarchy.

References

[1]

Gianfranco Bilardi and Franco P. Preparata. Upper bounds to processor-time tradeoffs under bounded-speed message propagation. In SPAA '95: Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, pages 185--194. ACM Press, 1995.

Digital Library

Google Scholar

[2]

Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. Cache-oblivious algorithms. In Proc. 40th Ann. Symp. Foundations of Computer Science (FOCS '99), New York, USA, October 1999.

Digital Library

Google Scholar

[3]

Jia-Wei Hong and H. T. Kung. I/O complexity: the red-blue pebbling game. In Proc. Thirteenth Ann. ACM Symp. Theory of Computing, pages 326--333, Milwaukee, 1981.

Digital Library

Google Scholar

[4]

Harald Prokop. Cache-oblivious algorithms. Master's thesis, Massachusetts Inst, of Technology, June 1999.

Google Scholar

[5]

G. D. Smith. Numerical Solution of Partial Differential Equations: Finite Difference Methods. Oxford University Press, 3rd edition, 1985.

Google Scholar

Cited By

View all

Liu PRoot AXu ALi YKjolstad FBik A(2024)Compiler Support for Sparse Tensor ConvolutionsProceedings of the ACM on Programming Languages10.1145/36897218:OOPSLA2(275-303)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689721
Lakshminarasimhan MHall MWilliams SAntepara O(2024)BrickDL: Graph-Level Optimizations for DNNs with Fine-Grained Data Blocking on GPUsProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673046(576-586)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673046
Ahmad ZBrowne RChowdhury RDas RHuang YZhu YLee IChabbi MSteuwer M(2024)Fast American Option Pricing using Nonlinear StencilsProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638506(316-332)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638506
Show More Cited By

Recommendations

Cache-Oblivious Algorithms

This article presents asymptotically optimal algorithms for rectangular matrix transpose, fast Fourier transform (FFT), and sorting on computers with multiple levels of caching. Unlike previous optimal algorithms, these algorithms are cache oblivious: ...
The memory behavior of cache oblivious stencil computations

We present and evaluate a cache oblivious algorithm for stencil computations, which arise for example in finite-difference methods. Our algorithm applies to arbitrary stencils in n -dimensional spaces. On an "ideal cache" of size Z , our algorithm ...
Cache-oblivious algorithms
CIAC'03: Proceedings of the 5th Italian conference on Algorithms and complexity

Computers with multiple levels of caching have traditionally required techniques such as data blocking in order for algorithms to exploit the cache hierarchy effectively. These "cache-aware" algorithms must be properly tuned to achieve good performance ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICS '05: Proceedings of the 19th annual international conference on Supercomputing

June 2005

414 pages

ISBN:1595931678

DOI:10.1145/1088149

General Chair:
Arvind
MIT
,
Program Chair:
Larry Rudolph
MIT

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICS05

Sponsor:

SIGARCH

ICS05: International Conference on Supercomputing 2005

June 20 - 22, 2005

Massachusetts, Cambridge

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

139
Total Citations
View Citations
1,201
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu PRoot AXu ALi YKjolstad FBik A(2024)Compiler Support for Sparse Tensor ConvolutionsProceedings of the ACM on Programming Languages10.1145/36897218:OOPSLA2(275-303)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689721
Lakshminarasimhan MHall MWilliams SAntepara O(2024)BrickDL: Graph-Level Optimizations for DNNs with Fine-Grained Data Blocking on GPUsProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673046(576-586)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673046
Ahmad ZBrowne RChowdhury RDas RHuang YZhu YLee IChabbi MSteuwer M(2024)Fast American Option Pricing using Nonlinear StencilsProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638506(316-332)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638506
Ahmad ZChowdhury RDas RGanapathi PGregory AZhu Y(2023)A Fast Algorithm for Aperiodic Linear Stencil Computation using Fast Fourier TransformsACM Transactions on Parallel Computing10.1145/360633810:4(1-34)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3606338
Liu SZhang ZWu W(2023)DHTS: A Dynamic Hybrid Tiling Strategy for Optimizing Stencil Computation on GPUsIEEE Transactions on Computers10.1109/TC.2023.327106072:10(2795-2807)Online publication date: Oct-2023
https://doi.org/10.1109/TC.2023.3271060
Liu SWan XZhang ZZhao BWu W(2023)TurboStencil: You only compute once for stencil computationFuture Generation Computer Systems10.1016/j.future.2023.04.019146(260-272)Online publication date: Sep-2023
https://doi.org/10.1016/j.future.2023.04.019
Sun BLi MYang HXu JLuan ZQian D(2023)Adapting combined tiling to stencil optimizations on sunway processorCCF Transactions on High Performance Computing10.1007/s42514-023-00147-x5:3(322-333)Online publication date: 17-May-2023
https://doi.org/10.1007/s42514-023-00147-x
Jacquelin MAraya-Polo MMeng JWolf FShende SCulhane CAlam SJagode H(2022)Scalable distributed high-order stencil computationsProceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis10.5555/3571885.3571924(1-13)Online publication date: 13-Nov-2022
https://dl.acm.org/doi/10.5555/3571885.3571924
Qu LAbdelkhalak RLtaief HSaid IKeyes D(2022)Exploiting temporal data reuse and asynchrony in the reverse time migrationThe International Journal of High Performance Computing Applications10.1177/1094342022112852937:2(132-150)Online publication date: 3-Oct-2022
https://doi.org/10.1177/10943420221128529
Ahmad ZChowdhury RDas RGanapathi PGregory AZhu YAgrawal KLee I(2022)Brief AnnouncementProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538558(291-293)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538558
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Cache-Oblivious Algorithms

The memory behavior of cache oblivious stencil computations

Cache-oblivious algorithms