Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Entwicklung und Implementierung von Partitionierungsstrategien für dünn besetzte Matrizen auf hybriden Systemen mit verteiltem Speicher

 
: Schubert, Lauretta
: Berrendorf, Rudolf; Becker, Peter

:
Volltext urn:nbn:de:0011-n-1987496 (20 MByte PDF)
MD5 Fingerprint: 9ceefd30189607bed4b11a8cbab26da2


Sankt Augustin, 2012, 127 pp.
Sankt Augustin, Hochschule Bonn-Rhein-Sieg, Master Thesis, 2012
German
Master Thesis, Electronic Publication
Fraunhofer SCAI ()
Partitionierung; Lastbalancierung; SpMV; GPU; LAMA; GPGPU; Graph-Partitionierung; Roofline-Modell; hybride Cluster

Abstract
Die Matrix-Vektor-Multiplikation für dünn besetzte Matrizen (SpMV) stellt für weitreichende wissenschaftliche Anwendungen eine der Kernoperationen des High-Performance-Computing-Bereichs dar. Für die verteilte Berechnung mit immer beliebter werdenden hybriden Rechenclustern kommt dabei die Frage nach einer geeigneten Partitionierungsstrategie für die Verteilung von Daten und Berechnung auf. Diese Arbeit beschäftigt sich damit welchen Einfluss die Struktur der Matrix und die unterschiedlichen Prozessortypen auf die Leistung der SpMV haben und schlägt ein Modell vor, um für diese eine lastbalancierte Verteilung zu erreichen. Wesentliche Bestandteile sind dabei die Laufzeitvorhersage für aktuelle CPUs und GPUs basierend auf einem abgewandelten Roofline-Modell sowie die bewährte Methode der Graph-Partitionierung. Es wird gezeigt, dass für die Laufzeit unter idealen Voraussetzungen eine gute Vorhersage gemacht werden kann und mit der Graph-Partitionierung die Kommunikation für die verteilte Berechnung mit asynchroner Kommunikation hinreichend minimiert wird. Weiterhin wird erläutert, warum für hybride Rechencluster die Abbildung der Rechenlast auf die Anzahl der Matrix-Einträge i.d.R. nicht ausreichend ist um ein balanciertes Gesamtsystem zu erhalten. Diese Problemstellung betreffend werden erste Verbesserungsvorschläge für die Modellierung gegeben.

: http://publica.fraunhofer.de/documents/N-198749.html