Performance modeling and prediction for linear algebra algorithms

Iakymchuk, Roman; Bientinesi, Paolo

doi:4271

Performance modeling and prediction for linear algebra algorithms = Performance-Modellierung und -Vorhersage von Algorithmen der Linearen Algebra

Iakymchuk, Roman (Author)

2012

Verantwortlichkeitsangabevorgelegt von Roman Iakymchuk

ImpressumAachen : Publikationsserver der RWTH Aachen University 2012

UmfangXVI, 117 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2012

Zsfassung in engl. und dt. Sprache

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Bientinesi, Paolo (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2012-08-30

Online
URN: urn:nbn:de:hbz:82-opus-42716
URL: https://publications.rwth-aachen.de/record/82828/files/4271.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Leistungsbewertung (Genormte SW) ; Hochleistungsrechnen (Genormte SW) ; Mathematische Modellierung (Genormte SW) ; Lineare Algebra (Genormte SW) ; Informatik (frei) ; Algorithmen der linearen Algebra (frei) ; Performance-Modellierung (frei) ; Performance-Vorhersage (frei) ; linear algebra algorithms (frei) ; performance prediction (frei) ; performance model (frei) ; memory-stalls (frei) ; cache misses (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
ccs: B.3.2 * G.4 * B.3.3

Kurzfassung
Die vorliegende Dissertation umfasst zwei Forschungsprojekte: Zum einen die Performance-Modellierung und -Vorhersage von Algorithmen der Linearen Algebra und zum anderen das Hochleistungsrechnen in Clouds. Das erste Projekt konzentriert sich auf Berechnungen mit dicht-besetzten Matrizen, die häufig den Kern wissenschaftlicher Simulationen bilden. Zur Durchführung dieser mathematischen Operationen bieten Lineare-Algebra-Bibliotheken eine Vielzahl verschiedener Algorithmen an. Die Wahl des entsprechenden Algorithmus wird maßgeblich durch die Performance bedingt, welche wiederum durch eine Vielzahl von Parametern beeinflusst wird. Unter diesen Einflussgrößen befinden sich die charakteristischen Eigenschaften der Computerplattform, die Implementierungsdetails des Algorithmus sowie die Größe und das Speicherformat der Operanden. Aufgrund dieser Komplexität stellt die Vorhersage der Performance eine anspruchsvolle Herausforderung dar – die Entwickler sind meist zu einer aufwendigen Trial-and-Error-Herangehensweise gezwungen. In unserer Arbeit zeigen wir eine alternative Methode auf und stellen dazu zwei Techniken zur Modellierung der Performance vor. Die Erste basiert auf stichprobenartigen Messungen ausgewählter Kernoperationen, während die Zweite vollständig auf das Ausführen des Algorithmus oder Teilen davon verzichtet. Beide Techniken verwenden einen Bottom-up-Ansatz: Zuerst wird die Performance der BLAS Kernoperationen modelliert. Diese Modelle werden dann genutzt, um die Performance von übergeordneten Algorithmen (z.B. der LU-Faktorisierung einer Matrix) zu modellieren, die auf den Kernoperationen hierarchisch aufbauen. Wir zeigen, dass beide Techniken exzellente Performance-Vorhersagen liefern. Das zweite Forschungsprojekt der Dissertation befasst sich mit dem Hochleistungsrechnen in einer kommerziellen Cloud-Computing-Umgebung. Wir untersuchen empirisch die Effizienz dieser Umgebung für rechenintensive wissenschaftliche Anwendungen und den Einfluss der dabei auftretenden geteilten Ressourcennutzung mit anderen Nutzern. Obwohl gelegentlich eine hohe Rechenleistung erzielt wird, führt die gemeinsame Nutzung der Prozessoren sowie der Cache-Speicher im Allgemeinen zu einer verminderten durchschnittlichen Rechenleistung mit hoher Varianz in der Performance. Mit Hilfe der Matrix-Matrix-Multiplikation und des LINPACK Benchmarks zeigen wir, dass durch die Unterauslastung der Ressourcen eine deutlich bessere durchschnittliche Rechenleistung erzielt werden kann. Zum Beispiel werden für eine Reihe von Cluster-Konfigurationen Operationen wesentlich schneller berechnet, wenn die vorhandenen Ressourcen nicht vollständig genutzt werden. Da die üblichen Performance-Metriken wissenschaftlicher Anwendungen hohe Fluktuationen zeigen, schlagen wir abschließend alternative Messgrößen vor, z.B. die zu erwartende Performance, die Kosten pro GFlop oder die Kosten für die Lösung eines Problems.

This dissertation incorporates two research projects: performance modeling and prediction for dense linear algebra algorithms, and high-performance computing on clouds. The first project is focused on dense matrix computations, which are often used as computational kernels for numerous scientific applications. To solve a particular mathematical operation, linear algebra libraries provide a variety of algorithms. The algorithm of choice depends, obviously, on its performance. Performance of such algorithms is affected by a set of parameters, which characterize the features of the computing platform, the algorithm implementation, the size of the operands, and the data storage format. Because of this complexity, predicting algorithmic performance is a challenging task, to the point that developers are often forced to rely on extensive trial-and-error technique. We approach this problem from a different perspective. Instead of performing exhaustive tests, we introduce two techniques for modeling performance: one is based on measurements and requires a limited number of sampling tests, while the other needs neither the execution of the algorithms nor parts of them. Both techniques employ a bottom-up approach: we first model the performance of the BLAS kernels. Then, using these results we create models for higher-level algorithms, e.g. the LU factorization, that are built on top of the BLAS kernels. As a result, by using the hierarchical and modular structure of linear algebra libraries, we develop two techniques for hierarchical performance modeling; both techniques yielding accurate predictions. The second project is concerned with high-performance computing on commercial cloud environments. We empirically study the computational efficiency of compute-intensive scientific applications in such an environment, where resources are shared under high contention. Although high performance is occasionally obtained, contention for the CPU and cache space degrades the expected performance and introduces significant variance. Using the matrix-matrix multiplication kernel of BLAS and the LINPACK benchmark, we show that the underutilization of resources substantially improves the expected performance. For instance, for a number of cluster configurations, the solution is reached considerably faster when the available resources are underutilized. Finally, since the performance measurements of scientific applications show high fluctuation, we propose alternatives, such as expected performance, expected execution time, and cost per GFlop, to the standard definitions of efficiency.

Fulltext:
PDF