Evaluating and improving upon the use of high-performance libraries in linear and multi-linear algebra

Psarras, Christos; Bientinesi, Paolo (Thesis advisor); van de Geijn, Robert (Thesis advisor); Morrison, Abigail Joanna Rhodes (Thesis advisor)

Aachen : RWTH Aachen University (2023)
Doktorarbeit

Dissertation, RWTH Aachen University, 2023

Kurzfassung

Diese Dissertation zielt darauf ab, den Prozess der Übersetzung von Formeln, die Matrizen und Tensoren enthalten, in leistungsfähigen Code zu verbessern und damit einen Beitrag zu den Bereichen der linearen bzw. multilinearen Algebra zu leisten. Die beiden Bereiche werden getrennt untersucht. Einerseits gibt es im Bereich der linearen Algebra seit langem standardisierte Bausteinbibliotheken (BLAS/LAPACK), die eine Reihe hoch optimierter Funktionen, sogenannte Kernel, anbieten. Das Vorhandensein dieser Bibliotheken hat dazu geführt, dass die Auswertung Formeln, die Matrizen enthalten, gleichbedeutend ist mit der Übersetzung dieser Formeln in Kernel. Für die Endnutzer wird es immer unwahrscheinlicher, dass sie sich für den zeitaufwändigen Prozess der direkten Verwendung dieser Kernel entscheiden; stattdessen werden Sprachen und Bibliotheken, die eine höhere Abstraktionsebene zur Verfügung stellen, immer beliebter. Diese Sprachen und Bibliotheken enthalten Mechanismen, die das Eingabeprogramm intern auf low-level Kernel abbilden. Allerdings ist eine solche Abbildung in Bezug auf die Rechenleistung in der Regel suboptimal. In dieser Dissertation definieren wir das Problem der Abbildung eines linearen Algebra-Ausdrucks auf eine Menge verfügbarer Bausteine als "Linear Algebra Mapping Problem" (LAMP); wir untersuchen, wie effektiv eine Reihe von Testproblemen von weitverbreiteten höheren Programmiersprachen und Bibliotheken gelöst wird. Im Einzelnen betrachten wir Matlab, Octave, Julia, R, Armadillo (C++), Eigen (C++) und NumPy (Python); der Benchmark testet sowohl Compiler-Optimierungen, als auch lineare Algebra-spezifische Optimierungen, wie die optimale Klammerung von Matrixprodukten. Abschließend geben wir Sprachentwicklern und Endbenutzern Ratschläge für die Priorisierung verschiedener Optimierungen bei der Lösung eines LAMP. Andererseits hat das Fehlen standardisierter Bausteinbibliotheken im Bereich der multilinearen Algebra zu einem erheblichen Mehraufwand bei der Softwareentwicklung geführt. Wir diskutieren den Nutzen solcher Bibliotheken für eine Reihe von Anwendungen und konzentrieren uns gleichzeitig auf Fälle, in denen ein bibliotheksbasierter Ansatz nicht ausreichen würde. Konkret untersuchen wir zwei solcher Fälle in einem der bekanntesten Gebiete der multilinearen Algebra, der Chemometrie: die CP-Tensorzerlegung (engl. canonical polyadic decomposition) und das Jackknife-Resampling, eine statistische Methode zur Bestimmung der Unsicherheiten von CP-Zerlegungen. Im ersten Fall, der CP-Zerlegung, verwendet eine weit verbreitete Methode zu ihrer Berechnung den Algorithmus der Alternating Least Squares (ALS). Wenn die Anzahl der Komponenten klein ist, weist ALS, unabhängig von der Implementierung, eine niedrige arithmetische Intensität auf, was seine Leistung stark einschränkt und die effektive Auslagerung auf GPUs verhindert. In der Praxis berechnen Anwender oftmals mehrere Zerlegungen desselben Tensors mit einer kleinen Anzahl von Komponenten (typischerweise weniger als 20). Wir machen uns diese Beobachtung zunutze und zeigen, wie sich mehrere Zerlegungen desselben Tensors auf algorithmischer Ebene miteinander verschmelzen lassen, um die arithmetische Intensität zu erhöhen. Dadurch können sowohl CPUs als auch GPUs effizienter genutzt werden, was zu einer weiteren Beschleunigung führt; gleichzeitig ist die Technik mit vielen Erweiterungen kompatibel, die typischerweise in ALS verwendet werden, wie z. B. Liniensuchverfahren (engl. line search) und Nicht-Negativitätsbeschränkungen (engl. non-negativity constraints). Als Teil dieser Arbeit präsentieren wir den Algorithmus und die Bibliothek Concurrent ALS (CALS), welche eine Matlab-Schnittstelle, sowie einen Mechanismus zur effektiven parallelen Ausführung von Zerlegungen mit unterschiedlicher Laufzeit bereitstellt. Experimentelle Ergebnisse mit synthetischen und realen Datensätzen zeigen, dass die erhöhte arithmetische Intensität zu einer kürzeren Laufzeit führt. In dem zweiten Fall, dem Jackknife-Resampling, wurde festgestellt, dass die abgetasteten Tensoren nahezu identisch sind. Wir konnten zeigen, dass es möglich ist, die CALS-Technik auf ein Jackknife-Resampling-Szenario zu erweitern. Diese Erweiterung ermöglicht den Zugang zu den rechnerischen Effizienzvorteilen von CALS zum Preis eines moderaten Anstiegs (typischerweise ein paar Prozent) in der Anzahl der Gleitkommaoperationen. Numerische Experimente mit synthetischen und realen Datensätzen zeigen, dass der vorgeschlagene Workflow um ein Vielfaches schneller sein kann als die konventionelle Methode, bei der die Jackknife-Teilmodelle einzeln verarbeitet werden.

Einrichtungen

• Fachgruppe Informatik [120000]
• Lehr- und Forschungsgebiet Neural Computation (FZ Jülich) [124920]