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.