h1

000918229 001__ 918229
000918229 005__ 20230329123016.0
000918229 0247_ $$2HBZ$$aHT021737434
000918229 0247_ $$2Laufende Nummer$$a42058
000918229 0247_ $$2datacite_doi$$a10.18154/RWTH-2023-01193
000918229 037__ $$aRWTH-2023-01193
000918229 041__ $$aEnglish
000918229 082__ $$a004
000918229 1001_ $$0P:(DE-82)IDM02071$$aBarthels, Henrik$$b0$$urwth
000918229 245__ $$aLinnea: a compiler for mapping linear algebra problems onto high-performance kernel libraries$$cvorgelegt von Henrik Barthels, Master of Science$$honline
000918229 260__ $$aAachen$$bRWTH Aachen University$$c2022
000918229 260__ $$c2023
000918229 300__ $$a1 Online-Ressource : Illustrationen
000918229 3367_ $$02$$2EndNote$$aThesis
000918229 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
000918229 3367_ $$2BibTeX$$aPHDTHESIS
000918229 3367_ $$2DRIVER$$adoctoralThesis
000918229 3367_ $$2DataCite$$aOutput Types/Dissertation
000918229 3367_ $$2ORCID$$aDISSERTATION
000918229 502__ $$aDissertation, RWTH Aachen University, 2022$$bDissertation$$cRWTH Aachen University$$d2022$$gFak01$$o2022-03-23
000918229 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University 2023
000918229 5203_ $$aDie Übersetzung von Berechnungen der linearen Algebra in effizienten Code, der aus Funktionen (sogenannte Kernel) besteht, wie sie von Bibliotheken wie BLAS und LAPACK bereitgestellt werden, ist ein häufig auftretendes Problem in verschiedenen Bereichen der Natur- und Ingenieurwissenschaften. Da die manuelle Übersetzung ein mühsamer, fehleranfälliger und zeitaufwendiger Prozess ist, der viel Fachwissen erfordert, wurden mehrere höhere Programmiersprachen und Bibliotheken entwickelt, die dieses Problem automatisch lösen. Beispiele hierfür sind Matlab, Julia, Eigen und Armadillo. Diese Sprachen und Bibliotheken ermöglichen es dem Benutzer, Berechnungen der linearen Algebra in Code zu beschreiben, der der mathematischen Beschreibung des Problems sehr ähnlich ist; dieser Code wird dann intern in Sequenzen von Kernel-Aufrufen übersetzt. Diese Sprachen und Bibliotheken führen zwar zu einer höheren Produktivität des Anwenders, es hat sich jedoch gezeigt, dass die automatische Übersetzung häufig in suboptimalem Code resultiert. In dieser Arbeit stellen wir Linnea vor, einen domänenspezifischen Compiler, der die mathematische Beschreibung von Problemen der linearen Algebra automatisch in effiziente Sequenzen von Kernel-Aufrufen übersetzt. Ziel von Linnea ist es, die Benutzerfreundlichkeit von höheren Programmiersprachen mit der Geschwindigkeit von Code zu kombinieren, der von einem Experten in einer niedrigeren Programmiersprache geschrieben wurde. Im Gegensatz zu anderen Sprachen und Bibliotheken macht Linnea ausgiebig Gebrauch von Wissen über lineare Algebra: Algebraische Identitäten wie Assoziativität, Kommutativität und Distributivität werden verwendet, um das Problem umzuschreiben. Darüber hinaus ist Linnea in der Lage, Eigenschaften von Matrizen abzuleiten und redundante Teilausdrücke zu erkennen. Um die große Anzahl von möglichen Lösungen zu durchsuchen verwendet Linnea einen modifizierten Best-First-Suchalgorithmus, der schnell eine erste Lösung und mit etwas mehr Zeit zunehmend bessere Lösungen findet. Diese Arbeit schließt mit einer umfangreichen experimentellen Evaluation von Linnea anhand von 25 Anwendungs- und 100 synthetischen Problemen, sowohl mit sequentieller als auch paralleler Ausführung. Die Ergebnisse zeigen, dass der generierte Code fast immer schneller ist als Matlab, Julia, Eigen und Armadillo, zum Teil um einen Faktor von mehr als 10. Für alle Testprobleme findet Linnea eine erste Lösung in weniger als einer Sekunde; eine nahezu optimale Lösung zu finden dauert selten länger als ein paar Minuten.$$lger
000918229 520__ $$aThe translation of linear algebra computations to efficient code consisting of kernels as provided by libraries such as BLAS and LAPACK is a frequently encountered problem in different areas of science and engineering. Since the manual translation is a tedious, error-prone and time consuming process that requires a lot of expertise, several high-level languages and libraries have been developed that solve this problem automatically. Example include Matlab, Julia, Eigen, and Armadillo. These languages and libraries allow users to describe linear algebra computations in code which closely resembles the mathematical description of the problem; this high-level code is then internally translated to sequences of kernel calls. Unfortunately, while those languages and libraries increase the productivity of the user, it has been shown that this automatic translation frequently results in suboptimal code. In this thesis, we present Linnea, a domain-specific compiler that automatically translates the high-level description of linear algebra problems to efficient sequences of kernel calls. Linnea aims to combine the ease-of-use of high-level languages with the performance of low-level code written by an expert. Unlike other languages and libraries, Linnea extensively makes use of knowledge about linear algebra: Algebraic identities such as associativity, commutativity, and distributivity are used to rewrite the input problem. In addition, Linnea is able to infer matrix properties and detect common subexpressions. To explore the large space of candidate solutions, Linnea uses a custom best-first search algorithm that quickly finds a first solution, and increasingly better solutions when given more time. This thesis concludes with an extensive experimental evaluation of Linnea on 25 application and 100 synthetic test problems, both with sequential and parallel execution. The results show that Linnea almost always outperforms Matlab, Julia, Eigen and Armadillo, with speedups up to and exceeding 10x. For all test problems, Linnea finds a first solution in less than one second; finding a close to optimal solution rarely takes longer than a few minutes.$$leng
000918229 588__ $$aDataset connected to Lobid/HBZ
000918229 591__ $$aGermany
000918229 653_7 $$acompiler
000918229 653_7 $$ahigh-performance computing
000918229 653_7 $$alinear algebra
000918229 653_7 $$aprogram generation
000918229 7001_ $$0P:(DE-82)IDM00518$$aBientinesi, Paolo$$b1$$eThesis advisor
000918229 7001_ $$0P:(DE-82)IDM00960$$aNaumann, Uwe$$b2$$eThesis advisor$$urwth
000918229 7001_ $$aPüschel, Markus$$b3$$eThesis advisor
000918229 8564_ $$uhttps://publications.rwth-aachen.de/record/918229/files/918229.pdf$$yOpenAccess
000918229 8564_ $$uhttps://publications.rwth-aachen.de/record/918229/files/918229_source.zip$$yRestricted
000918229 909CO $$ooai:publications.rwth-aachen.de:918229$$pdnbdelivery$$pdriver$$pVDB$$popen_access$$popenaire
000918229 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000918229 9141_ $$y2022
000918229 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM02071$$aRWTH Aachen$$b0$$kRWTH
000918229 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00960$$aRWTH Aachen$$b2$$kRWTH
000918229 9201_ $$0I:(DE-82)123120_20140620$$k123120$$lLehr- und Forschungsgebiet Informatik 12 (Software und Werkzeuge für Computational Engineering)$$x0
000918229 9201_ $$0I:(DE-82)120000_20140620$$k120000$$lFachgruppe Informatik$$x1
000918229 961__ $$c2023-03-22T08:31:55.444707$$x2023-02-03T17:37:06.891635$$z2023-03-22T08:31:55.444707
000918229 9801_ $$aFullTexts
000918229 980__ $$aI:(DE-82)120000_20140620
000918229 980__ $$aI:(DE-82)123120_20140620
000918229 980__ $$aUNRESTRICTED
000918229 980__ $$aVDB
000918229 980__ $$aphd