EUVIMEDEUVIMED entdecken
Crossref

Cache-Oblivious Algorithms

Matteo Frigo, Charles E. Leiserson, Harald Prokop, Sridhar Ramachandran

ACM Transactions on Algorithms · 2012-01 · 8 (1) · 1-22

DOI: 10.1145/2071379.2071383 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Algorithms, 2012-01. Verfasst von Matteo Frigo und 3 weiteren Autor:innen. Die Arbeit wurde bisher 102-mal zitiert (Crossref) und nennt 41 Literaturangaben. Gefördert von: National Science Foundation, Division of Computing and Communication Foundations, Division of Computer and Network Systems.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 : no variables dependent on hardware parameters, such as cache size and cache-line length, need to be tuned to achieve optimality. Nevertheless, these algorithms use an optimal amount of work and move data optimally among multiple levels of cache. For a cache with size M and cache-line length B where M = Ω ( B 2 ), the number of cache misses for an m × n matrix transpose is Θ (1 + mn / B ). The number of cache misses for either an n -point FFT or the sorting of n numbers is Θ (1 + ( n / B )(1 + log M n )). We also give a Θ ( mnp )-work algorithm to multiply an m × n matrix by an n × p matrix that incurs Θ (1 + ( mn + np + mp )/ B + mnp / B √ M ) cache faults. We introduce an “ideal-cache” model to analyze our algorithms. We prove that an optimal cache-oblivious algorithm designed for two levels of memory is also optimal for multiple levels and that the assumption of optimal replacement in the ideal-cache model can be simulated efficiently by LRU replacement. We offer empirical evidence that cache-oblivious algorithms perform well in practice.

Förderung

  • National Science Foundation
  • Division of Computing and Communication Foundations
  • Division of Computer and Network Systems
  • Defense Advanced Research Projects Agency

Zitieren

APA

Frigo, M., Leiserson, C. E., Prokop, H., & Ramachandran, S. (2012). Cache-Oblivious Algorithms. ACM Transactions on Algorithms, 8(1), 1-22. https://doi.org/10.1145/2071379.2071383

Vancouver

Frigo M, Leiserson CE, Prokop H, Ramachandran S. Cache-Oblivious Algorithms. ACM Transactions on Algorithms. 2012;8(1):1-22. doi:10.1145/2071379.2071383

BibTeX
@article{Frigo2012,
  author = {Frigo, Matteo and Leiserson, Charles E. and Prokop, Harald and Ramachandran, Sridhar},
  title = {Cache-Oblivious Algorithms},
  journal = {ACM Transactions on Algorithms},
  year = {2012},
  volume = {8},
  number = {1},
  pages = {1--22},
  doi = {10.1145/2071379.2071383}
}
Kostenlos starten →