guest ::
Evaluating and improving upon the use of high-performance libraries in linear and multi-linear algebra
2023
Dissertation, RWTH Aachen University, 2023
Veröffentlicht auf dem Publikationsserver der RWTH Aachen University
Genehmigende Fakultät
Fak01
Hauptberichter/Gutachter
; ;
Tag der mündlichen Prüfung/Habilitation
2023-01-23
Online
DOI: 10.18154/RWTH-2023-01466
URL: https://publications.rwth-aachen.de/record/945184/files/945184.pdf
Einrichtungen
Projekte
Inhaltliche Beschreibung (Schlagwörter)
HPC (frei) ; dense linear algebra (frei) ; high-performance libraries (frei) ; linear algebra mapping problem (frei) ; multi-linear algebra (frei)
Thematische Einordnung (Klassifikation)
DDC: 004
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.This dissertation aims to improve the process of translating (mapping) expressions containing matrices and tensors to high-performance code and thus contributes to the linear and multi-linear algebra domains, respectively. The two domains are examined separately. On the one hand, in the linear algebra domain, standardized building-block libraries (BLAS/LAPACK) have long existed, offering a set of highly optimized functions called kernels. The existence of those libraries has made the task of evaluating mathematical expressions containing matrices equivalent to mapping those expressions to a sequence of kernel invocations. However, end-users are progressively less likely to go through the time-consuming process of directly using said kernels; instead, languages and libraries, which offer a higher level of abstraction, are becoming increasingly popular. These languages and libraries offer mechanisms that internally map an input program to lower level kernels. Unfortunately, our experience suggests that, in terms of performance, this mapping is typically suboptimal. In this dissertation, we formally define the problem of mapping a linear algebra expression to a set of available building blocks as the "Linear Algebra Mapping Problem" (LAMP). Then, we investigate how effectively a benchmark of test problems is solved by popular high-level programming languages and libraries. Specifically, we consider Matlab, Octave, Julia, R, Armadillo (C++), Eigen (C++), and NumPy (Python); the benchmark tests both compiler optimizations, as well as linear algebra specific optimizations, such as the optimal parenthesization of matrix products. Finally, we provide guidelines to language developers and end-users for how to prioritize different optimizations when solving a LAMP. On the other hand, in the multi-linear algebra domain, the absence of standardized, building-block libraries has led to significant replication of effort when it comes to software development. While we point out the benefit that such libraries would provide to a number of scientific fields, at the same time we identify and focus on cases where such a library-based approach would not suffice. Specifically, we investigate two such cases in one of the most prominent fields in multi-linear algebra, chemometrics: the Canonical Polyadic (CP) tensor decomposition and jackknife resampling, a statistical method used to determine uncertainties of CP decompositions.For the first case, the CP decomposition, a broadly used method for computing it relies on the Alternating Least Squares (ALS) algorithm. When the number of components is small, regardless of its implementation, ALS exhibits low arithmetic intensity, which severely hinders its performance and makes GPU offloading ineffective. We observe that, in practice, experts often have to compute multiple decompositions of the same tensor, each with a small number of components (typically fewer than 20). Leveraging this observation, we illustrate how multiple decompositions of the same tensor can be fused together at the algorithmic level to increase the arithmetic intensity. Therefore, both CPUs and GPUs can be utilized more efficiently for further speedups; at the same time the technique is compatible with many enhancements typically used in ALS, such as line search, and non-negativity constraints. We introduce the Concurrent ALS (CALS) algorithm and library, which offers an interface to Matlab, and a mechanism to effectively deal with the issue that decompositions complete at different times. Experimental results on artificial and real datasets demonstrate that the increased arithmetic intensity results in a shorter time to completion.For the second case, we examine jackknife resampling. Upon observation that the jackknife resampled tensors, though different, are nearly identical, we show that it is possible to extend the CALS technique to a jackknife resampling scenario. This extension gives access to the computational efficiency advantage of CALS for the price of a modest increase (typically a few percent) in the number of floating point operations. Numerical experiments on both synthetic and real-world datasets demonstrate that the proposed workflow can be several times faster than a straightforward workflow where the jackknife submodels are processed individually.
OpenAccess: 
PDF
(additional files)
Dokumenttyp
Dissertation / PhD Thesis
Format
online
Sprache
English
Externe Identnummern
HBZ: HT021725508
Interne Identnummern
RWTH-2023-01466
Datensatz-ID: 945184
Beteiligte Länder
Germany
