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

Barthels, Henrik; Bientinesi, Paolo (Thesis advisor); Naumann, Uwe (Thesis advisor); Püschel, Markus (Thesis advisor)

Aachen : RWTH Aachen University (2022, 2023)
Doktorarbeit

Dissertation, RWTH Aachen University, 2022

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.

Einrichtungen

• Fachgruppe Informatik [120000]
• Lehr- und Forschungsgebiet Informatik 12 (Software und Werkzeuge für Computational Engineering) [123120]