Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
FLOPs as a discriminant for dense linear algebra algorithms
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-4675-7434
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-4972-7097
2022 (English)In: ICPP '22: proceedings of the 51st international conference on parallel processing, ACM Digital Library, 2022, article id 11Conference paper, Published paper (Refereed)
Abstract [en]

Expressions that involve matrices and vectors, known as linear algebra expressions, are commonly evaluated through a sequence of invocations to highly optimised kernels provided in libraries such as BLAS and LAPACK. A sequence of kernels represents an algorithm, and in general, because of associativity, algebraic identities, and multiple kernels, one expression can be evaluated via many different algorithms. These algorithms are all mathematically equivalent (i.e., in exact arithmetic, they all compute the same result), but often differ noticeably in terms of execution time. When faced with a decision, high-level languages, libraries, and tools such as Julia, Armadillo, and Linnea choose by selecting the algorithm that minimises the FLOP count. In this paper, we test the validity of the FLOP count as a discriminant for dense linear algebra algorithms, analysing "anomalies": problem instances for which the fastest algorithm does not perform the least number of FLOPs. To do so, we focused on relatively simple expressions and analysed when and why anomalies occurred. We found that anomalies exist and tend to cluster into large contiguous regions. For one expression anomalies were rare, whereas for the other they were abundant. We conclude that FLOPs is not a sufficiently dependable discriminant even when building algorithms with highly optimised kernels. Plus, most of the anomalies remained as such even after filtering out the inter-kernel cache effects. We conjecture that combining FLOP counts with kernel performance models will significantly improve our ability to choose optimal algorithms.

Place, publisher, year, edition, pages
ACM Digital Library, 2022. article id 11
Keywords [en]
algorithm selection, linear algebra, scientific computing
National Category
Computer Sciences Computational Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-214445DOI: 10.1145/3545008.3545072ISI: 001062754200011Scopus ID: 2-s2.0-85138311336ISBN: 9781450397339 (electronic)OAI: oai:DiVA.org:umu-214445DiVA, id: diva2:1797663
Conference
ICPP '22: 51st International Conference on Parallel Processing Bordeaux France 29 August 2022- 1 September 2022
Available from: 2023-09-15 Created: 2023-09-15 Last updated: 2025-04-24Bibliographically approved

Open Access in DiVA

fulltext(962 kB)135 downloads
File information
File name FULLTEXT01.pdfFile size 962 kBChecksum SHA-512
ee87b64bca4881ade63a68c1ee0231a19b03b6cde1b3ccbaffb0e801d3e2670ffdfe843bc52423b6d063fea9fad71f37ce2a7c52185aaee87cf621cf7a7392cb
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

López, FranciscoKarlsson, LarsBientinesi, Paolo

Search in DiVA

By author/editor
López, FranciscoKarlsson, LarsBientinesi, Paolo
By organisation
Department of Computing Science
Computer SciencesComputational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 135 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 488 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf