Performance modeling and prediction for dense linear algebra

Peise, Elmar Hans; Gunnels, John; Bientinesi, Paolo; Müller, Matthias Stefan

doi:HT019650566

Performance modeling and prediction for dense linear algebra = Performance-Modellierung und -Vorhersage für Dichtbesetzte Lineare Algebra

Peise, Elmar Hans^RWTH*

2017 & 2018

Verantwortlichkeitsangabevorgelegt von Elmar Peise, Master of Science

ImpressumAachen 2017

Umfang1 Online-Ressource (xii, 257 Seiten) : Illustrationen

Dissertation, RWTH Aachen University, 2017

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2018

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Bientinesi, Paolo (Thesis advisor) ; Müller, Matthias Stefan (Thesis advisor)^RWTH* ; Gunnels, John (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2017-11-30

Online
DOI: 10.18154/RWTH-2018-223017
URL: http://publications.rwth-aachen.de/record/721186/files/721186.pdf

Einrichtungen

Projekte

GSC 111: Aachen Institute for Advanced Study in Computational Engineering Science (AICES) (24613455) (24613455)

Inhaltliche Beschreibung (Schlagwörter)
dense linear algebra (frei) ; performance modeling (frei) ; performance prediction (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Diese Dissertation stellt messungsbasierte Techniken zur Performancemodellierung und -Vorhersage für Algorithmen der dichtbesetzten linearen Algebra vor. Als ein Kernprinzip vermeiden diese Techniken die Ausführung solcher Algorithmen völlig und sagen ihre Performance stattdessen durch Laufzeitschätzungen ihrer Kernoperationen vorher. Für eine Vielzahl an Operationen erlauben diese Vorhersagen schnell die effizienteste Algorithmuskonfigurationen aus verfügbaren Alternativen zu wählen. Wir betrachten zwei Szenarien, die ein breites Spektrum von Berechnungen abdecken: Um die Performance von geblockten Algorithmen vorherzusagen, entwerfen wir algorithmenunabhängige Performancemodelle für Kernoperationen, die pro Plattform einmalig automatisiert generiert werden. Für diverse Matrixoperationen identifizieren auf solchen Modellen basierende Vorhersagen schnell und treffsicher den schnellsten Algorithmus und eine nahezu optimale Blockgröße. Für Performancevorhersagen von BLAS-basierten Tensorkontraktionen schlagen wir Microbenchmarks vor, die Caching-Effekte einkalkulieren und die hochreguläre Struktur der Kontraktionen ausnutzen. In nur einem Bruchteil der Laufzeit einer Kontraktion identifizieren auf solchen Microbenchmarks basierende Vorhersagen die schnellste Kombination aus Tensortraversierung und Kernoperation.

This dissertation introduces measurement-based performance modeling and prediction techniques for dense linear algebra algorithms. As a core principle, these techniques avoid executions of such algorithms entirely, and instead predict their performance through runtime estimates for the underlying compute kernels. For a variety of operations, these predictions allow to quickly select the fastest algorithm configurations from available alternatives. We consider two scenarios that cover a wide range of computations: To predict the performance of blocked algorithms, we design algorithm-independent performance models for kernel operations that are generated automatically once per platform. For various matrix operations, instantaneous predictions based on such models both accurately identify the fastest algorithm, and select a near-optimal block size. For performance predictions of BLAS-based tensor contractions, we propose cache-aware micro-benchmarks that take advantage of the highly regular structure inherent to contraction algorithms. At merely a fraction of a contraction's runtime, predictions based on such micro-benchmarks identify the fastest combination of tensor traversal and compute kernel.

OpenAccess:
PDF
(additional files)