TU Darmstadt / ULB / TUprints

Irregularity mitigation and portability abstractions for accelerated sparse matrix factorization

Thürck, Daniel (2021)
Irregularity mitigation and portability abstractions for accelerated sparse matrix factorization.
Technische Universität
doi: 10.26083/tuprints-00017951
Ph.D. Thesis, Primary publication, Publisher's Version

[img]
Preview
Text
20210420_dthuerck_dissertation_pdfa.pdf
Copyright Information: CC BY-NC-SA 4.0 International - Creative Commons, Attribution NonCommercial, ShareAlike.

Download (9MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Irregularity mitigation and portability abstractions for accelerated sparse matrix factorization
Language: English
Referees: Kersting, Prof. Dr. Kristian ; Bollhöfer, Prof. Dr. Matthias ; Goesele, Prof. Dr. Michael
Date: 2021
Place of Publication: Darmstadt
Collation: B, XIII, 175 Seiten
Date of oral examination: 25 March 2021
DOI: 10.26083/tuprints-00017951
Abstract:

In this thesis, we investigate new ways to mitigate the inherent irregularity in sparse matrix factorizations and decompose the resulting computation into simple kernels which are portable across a diverse set of compute accelerator architectures through our novel compiler borG. Be it weather prediction, climate models, personalized medicine, genetic analysis and autonomous driving: some of today's central challenges require processing of vast amounts of data, feeding large-scale simulations or AI models. As the scale of these problems outpaces the processing power and available storage capacity, it becomes crucial to exploit their inherent sparsity. Such sparse topologies, i.e., graph topologies where most of the nodes are not directly connected, are often the source for sparse linear systems of equations whose solution poses a major computational challenge.

At the same time, we are witnessing a shift in terms of hardware in the high-performance computing field: as hardware designers try to avoid the quadratically increasing energy consumption for higher clock frequencies, compute setups increase parallelism and specialization instead. Notably, most of the accelerators in use today are optimized for massive parallelism on regular structures and dense data structures.

Processing sparse workloads efficiently on novel, heterogeneous architectures presents a challenge that demands systemic solutions. In this thesis, we investigate strategies and systems focusing on an important building block for computational sciences: sparse numerical (matrix) factorizations. Factorizations exhibit irregularity in two aspects. First, the sparse data structures complicate workload distribution on accelerators geared towards regular grids. Second, numerically mandated pivoting introduces irregularity into the control flow. This leads to expensive synchronization points and requires expensive re-building of data structures.

We propose two building blocks that help mitigate these problems for accelerators. First, a generalization of sparse factorizations to block-sparse matrices, leading to the use of batched, heavily templated compute kernels. Such kernels are relatively simple and can be tuned for the accelerator architecture in question. Second, we propose a data structure for block-sparse matrices that enables global pivoting through parallel index modifications. Additionally, we demonstrate how pivoting can be introduced into register-focused GPU kernels, leading to a two-level, threshold a-posteriori pivoting scheme. Both concepts are validated on implementations of sparse LDLt factorizations for GPUs.

Once we extend the block-sparse approach to other architectures, we risk maintaining divergent, device-specific code bases for batched kernels. Therefore, we present the source-to-source compiler borG. Based on a novel intermediate representation unifying two distinct parallel architectures programming models, borG compiles OpenCL code that uses a generalization of the warp register cache idiom, to AVX512-based CPUs, NVIDIA GPUs and NEC's SX-Aurora vector processor. The generated kernels may be specialized for a specific problem size, e.g., processing a batch of m*n matrices, and compare favorably to hand-coded kernels in the systems' native development stack.

Building on work so far, we extend the concept of block-sparse decomposition and generalize it into a meta-algorithm. Motivated by the rise of domain-specific, fixed function accelerators, we simplify the device-side code for factorizations even further. The resulting concept, METAPACK, can be implemented not just on more traditional compute accelerators, but also on "non-Neumann" types of hardware. The latter includes systolic arrays and FPGAs. Relying only on host-side pipelining and batched kernel submission, we lay out a blueprint of a versatile factorization generator. As a full-stack system, METAPACK will allow rapid creation of customized, parameterized, sparse factorization code across many systems that support batched or pipelined parallelism. Several experiments confirm the validity of the concept and encourage a full-fledged implementation.

For the sake of simplicity, METAPACK regularizes sparse matrices by subdivision into a regular grid. In order to reduce the memory waste and exploit compute resources more efficiently, accelerators would need native support for work items of different sizes. By expanding on concepts from borG, we propose such support. We combine an incremental change of current accelerators' architectures with a novel compiler pass to simplify such irregular scheduling on the hardware side. A prototypical software simulation shows this architectures' potential to simplify support for irregular compute loads in the future.

In summary, our work can help to improve and simplify the handling of sparse matrix factorizations and their efficiency on acclerators. Through a block-centric decomposition of the factorization process and a simplification of the primitive numerical kernels, we enable the use of novel and future accelerator architectures for the sparse problems of computational science.

Alternative Abstract:
Alternative AbstractLanguage

In dieser Arbeit untersuchen wir neue Ansätze zur Minderung der unerwünschten Effekte bedingt durch irregulär strukturierte Berechnungen bei der Faktorisierung von dünnbesetzten Matrizen. Dazu zerlegen wir die Abfolge der Berechnungen in primitive Funktionen, die sich mittels unseres Compilers borG auf mehrere Arten von Rechenbeschleunigern übersetzen lassen. Sowohl bei der Wettervorhersage, als auch bei Klimamodellen, personalisierter Medizin, genetischer Analyse oder etwa beim autonomen Fahren werden heutzutage große Mengen an Daten verarbeitet, insbesondere durch hochauflösende Simulation oder Algorithmen des maschinellen Lernens. Aufgrund des weiterhin zunehmenden Umfanges dieser Probleme gerät die aktuelle Generation der Hardware sowohl hinsichtlich der Rechenpower als auch der Speicherkapazität an ihre Grenzen. Daher ist es entscheidend, dünnbesetzte Strukturen der Probleme auszunutzen. Diese Strukturen, die sich im Falle eines Graphen etwa dadurch auszeichnen, dass viele Knoten nicht direkt verbunden sind, führen oft zu dünnbesetzten lineare Gleichungssystemen, deren Lösung sehr rechenintensiv ist.

Gleichzeitig findet ein Prinzipienwandel in der Hardwareentwicklung im Bereich des Hochleistungsrechnens statt: Um den quadratisch zunehmenden Energiebedarf von höheren Taktfrequenzen zu umgehen, setzen Entwickler vermehrt auf Parallelisierung und Spezialisierung. So sind die heute meistverwendeten Rechenbeschleuniger für massive-parallele Berechnungen auf dichten und regulären Datenstrukturen ausgelegt.

Die effiziente Lösung dünnbesetzer Problemstrukturen auf solchen Beschleunigerarchitekturen stellt eine Herausforderung dar, der nur systemische Lösungen gerecht werden können. In dieser Arbeit untersuchen wir daher Strategien und Systeme, die sich mit einem wichtigen Fall dünnbesetzter Problemstrukturen beschäftigen: die der dünnbesetzten linearen Gleichungssysteme. Diese weist in zweierlei Hinsicht irreguläre Strukturen auf: Einmal führt die irreguläre Verteilung der Einträge in der Matrix zu Schwierigkeiten bei der gleichmäßigen Verteilung der Berechnungen auf die Hardware. Zusätzlich benötigen numerisch anspruchsvolle Matrizen eine Pivotisierung, die zu irregulärem Kontrollfluss im Programm führt. Dadurch ergibt sich unerwünschter Synchronisationsaufwand und es wird ein aufwändiger Neuaufbau vorhandener Datenstrukturen notwendig.

Daher schlagen wir zwei Bausteine vor, die die adversen Effekte dieser beiden Eigenschaften minimieren sollen. Zunächst generalisieren wir die Faktorisierung auf die Ebene von dichten Blöcken in der dünnbesetzten Matrix, was die Abbildung der notwendigen Berechnungen auf "batched" Funktionsaufrufe, die einem Template folgen, ermöglicht. Diese Funktionen sind relativ einfach und können mit wenig Aufwand an eine Beschleunigerarchitektur angepasst werden. Weiterhin beschreiben wir eine Datenstruktur, die globale Pivotisierung auf Block-Matrizen ausschließlich durch Index-Manipulationen ermöglicht. Als weitere Möglichkeit zur Pivotisierung zeigen wir registerfokussierte Implementierungen von linearer Algebra auf Grafikkarten auf. Die Kombination beider Arten der Pivotisierung ergibt schließlich eine a-posteriori-Pivotingstrategie, welche wir im Rahmen einer LDLt-Faktorisierung auf Grafikkarten validieren.

Wenn wir diese Methoden ebenfalls auf anderen Beschleunigerarchitekturen verwenden wollen, kann es zu divergenten, architekturspezifischen Quellcodesammlungen kommen. Als Lösung prasentieren wir hier den Quellcode-zu-Quellcode Compiler borG. Dieser basiert auf einer neuartigen abstrakten Darstellung zweier verschiedener Konzepte des parallen Rechnens und übersetzt registerfokussierten Quellcode für Prozessoren mit AVX512, NVIDIA Grafikkarten und NECs SX-Aurora Vektorprozessor. Die generierten Programme können auf eine gewissen Problemgröße, etwa für m*n Matrizen, spezialisiert sein und sind von der Laufzeit her vergleichbar mit Programmen, die händisch in der jeweiligen nativen Entwicklerumgebung erstellt wurden.

Darauf aufbauend, erweitern wir das Konzept der Faktorisierung von Blockmatrizen hin zu einem Meta-Algorithmus der Faktorisierung. Inspiriert durch das Aufkommen von spezialisierten Hardwarebeschleunigern, vereinfachen wir den beschleunigerseitigen Code noch weiter. Diese Ansätze ergeben das Konzept "METAPACK", welches nicht nur für die verbreiteten Beschleunigerarchitekturen umgesetzt werden kann, sondern auch neue "non-Neumann" Typen von Architekturen unterstützt, darunter Systolische Arrays und FPGAs (rekonfigurierbare Hardware). Wir beschreiben die Blaupause einer Implementierung, die sich nur auf Pipeleine-Parallelisierung auf Host- und "batched"-Parallelisierung auf der Beschleunigerseite stützt. In seiner vollen Ausbaustufe wird METAPACK es Benutzern erlauben, schnell angepasste Pakete zur Faktorisierung dünnbesetzter Matrizen auf ihrer jeweiligen Beschleunigerhardware zu instanziieren. Mittels mehrerer Experimente belegen wir das enorme Potenizal dieses Konzeptes und leisten dadurch einer künftigen Umsetzung Vorschub.

Zur Reduktion der Komplexität verwendet METAPACK eine einheitliche Blockgröße zur Matrixzerlegeung. Um jedoch Speicherverwendung und Unterforderung der Berechnungseinheiten des Beschleunigers zu vermeiden, bräuchten ebenjene Beschleuniger native Unterstützung für "Batches" aus Problemen unterschiedlicher Größen. Basierend auf unseren Ideen zu borG, schlagen wir inkrementelle Änderungen an der Hardwarearchitektur vor und ergänzen Compiler um eine neue Phase, die zusammen die Verteilung dieser irregulären Probleme signifikant vereinfacht. Mittels einer Simulation in Software zeigen wir schlussendlich das Potenzial dieser Architektur für die Berechnungsprobleme der Zukunft auf.

Zusammenfassend lässt sich sagen, dass unsere Arbeit entscheidende Ansätze zur vereinfachten Entwicklung von effizienten Implementierungen von Lösern für dünnbesetzte Gleichungssyteme liefert. Durch unsere Blockmatrix-basierte Abstraktion des Faktorisierungsprozesses und der relativ simplen numerischen Funktionen ermöglichen wir die Nutzung aktueller und zukünftiger Beschleunigerarchitekturen für die Berechnungen der rechnergestützten Wissenschaft.

German
Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-179517
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Artificial Intelligence and Machine Learning
Date Deposited: 03 May 2021 12:24
Last Modified: 03 May 2021 12:25
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/17951
PPN: 478796935
Export:
Actions (login required)
View Item View Item