EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Cache-oblivious Hilbert Curve-based Blocking Scheme for Matrix Transposition

João Nuno Ferreira Alves, Luís Manuel Silveira Russo, Alexandre Francisco

ACM Transactions on Mathematical Software · 31.12.2022 · 48 (4) · 1-28

DOI: 10.1145/3555353 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Mathematical Software, online erschienen am 19.12.2022. Verfasst von João Nuno Ferreira Alves und 2 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 24 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Fundação para a Ciência e Tecnologia, Austrian Science Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

This article presents a fast SIMD Hilbert space-filling curve generator, which supports a new cache-oblivious blocking-scheme technique applied to the out-of-place transposition of general matrices. Matrix operations found in high performance computing libraries are usually parameterized based on host microprocessor specifications to minimize data movement within the different levels of memory hierarchy. The performance of cache-oblivious algorithms does not rely on such parameterizations. This type of algorithm provides an elegant and portable solution to address the lack of standardization in modern-day processors. Our solution consists in an iterative blocking scheme that takes advantage of the locality-preserving properties of Hilbert space-filling curves to minimize data movement in any memory hierarchy. This scheme traverses the input matrix, in O(nm) time and space, improving the behavior of matrix algorithms that inherently present poor memory locality. The application of this technique to the problem of out-of-place matrix transposition achieved competitive results when compared to state-of-the-art approaches. The performance of our solution surpassed Intel MKL version after employing standard software prefetching techniques.

Förderung

  • Fundação para a Ciência e Tecnologia
  • Austrian Science Fund

Zitieren

APA

Alves, J. N. F., Russo, L. M. S., & Francisco, A. (2022). Cache-oblivious Hilbert Curve-based Blocking Scheme for Matrix Transposition. ACM Transactions on Mathematical Software, 48(4), 1-28. https://doi.org/10.1145/3555353

Vancouver

Alves JNF, Russo LMS, Francisco A. Cache-oblivious Hilbert Curve-based Blocking Scheme for Matrix Transposition. ACM Transactions on Mathematical Software. 2022;48(4):1-28. doi:10.1145/3555353

BibTeX
@article{Alves2022,
  author = {Alves, João Nuno Ferreira and Russo, Luís Manuel Silveira and Francisco, Alexandre},
  title = {Cache-oblivious Hilbert Curve-based Blocking Scheme for Matrix Transposition},
  journal = {ACM Transactions on Mathematical Software},
  year = {2022},
  volume = {48},
  number = {4},
  pages = {1--28},
  doi = {10.1145/3555353}
}
Kostenlos starten →