Linnea: a compiler for mapping linear algebra problems onto high-performance kernel libraries

Barthels, Henrik; Püschel, Markus; Bientinesi, Paolo; Naumann, Uwe

doi:10.18154/RWTH-2023-01193

Linnea: a compiler for mapping linear algebra problems onto high-performance kernel libraries

Barthels, Henrik^RWTH*

2022 & 2023

Verantwortlichkeitsangabevorgelegt von Henrik Barthels, Master of Science

ImpressumAachen : RWTH Aachen University 2022

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2022

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2023

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Bientinesi, Paolo (Thesis advisor) ; Naumann, Uwe (Thesis advisor)^RWTH* ; Püschel, Markus (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2022-03-23

Online
DOI: 10.18154/RWTH-2023-01193
URL: https://publications.rwth-aachen.de/record/918229/files/918229.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
compiler (frei) ; high-performance computing (frei) ; linear algebra (frei) ; program generation (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Die Ü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.

The 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.

OpenAccess:
PDF
(zusätzliche Dateien)