Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
FLOPs as a discriminant for dense linear algebra algorithms
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-4675-7434
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-4972-7097
2022 (Engelska)Ingår i: ICPP '22: proceedings of the 51st international conference on parallel processing, ACM Digital Library, 2022, artikel-id 11Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
ACM Digital Library, 2022. artikel-id 11
Nyckelord [en]
algorithm selection, linear algebra, scientific computing
Nationell ämneskategori
Datavetenskap (datalogi) Beräkningsmatematik
Identifikatorer
URN: urn:nbn:se:umu:diva-214445DOI: 10.1145/3545008.3545072Scopus ID: 2-s2.0-85138311336ISBN: 9781450397339 (digital)OAI: oai:DiVA.org:umu-214445DiVA, id: diva2:1797663
Konferens
ICPP '22: 51st International Conference on Parallel Processing Bordeaux France 29 August 2022- 1 September 2022
Tillgänglig från: 2023-09-15 Skapad: 2023-09-15 Senast uppdaterad: 2023-11-10Bibliografiskt granskad

Open Access i DiVA

fulltext(962 kB)78 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 962 kBChecksumma SHA-512
ee87b64bca4881ade63a68c1ee0231a19b03b6cde1b3ccbaffb0e801d3e2670ffdfe843bc52423b6d063fea9fad71f37ce2a7c52185aaee87cf621cf7a7392cb
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

López, FranciscoKarlsson, LarsBientinesi, Paolo

Sök vidare i DiVA

Av författaren/redaktören
López, FranciscoKarlsson, LarsBientinesi, Paolo
Av organisationen
Institutionen för datavetenskap
Datavetenskap (datalogi)Beräkningsmatematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 78 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 311 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf