Motivation

Die Multiplikation dünn besetzter Matrizen mit Vektoren (Sparse-Matrix-Vector-Multiplication) muss in vielen wissenschaftlichen Simulationsanwendungen durchgeführt werden. Die Algorithmen zur Berechnung derartiger Produkte sind stets durch die Speicherbandbreite limitiert (memory-bound) und sind daher in ihrer Skalierbarkeit bei paralleler Ausführung beschränkt.

Dementsprechend existiert eine Reihe von Datenformaten zum Abspeichern derartiger Matrizen, die sich je nach verwendeter Architektur (Multi-Core-System, Grafikkarte) unterscheiden können.

Ebenso gibt es in der Literatur diverse Strategien zur Optimierung, sowohl für dünn besetzte Matrizen von denen bestimmte Eigenschaften bekannt sind, als auch für solche über die a priori keine Aussage möglich ist.

Beschreibung der Arbeit

Im Rahmen dieser Arbeit soll anhand bestehender Lösungen ein entsprechendes Datenformat, sowie ein optimierter Algorithmus für die Multiplikation von Matrizen mit einer bestimmten, für jede Problemgröße identischen Struktur und einem dichten Vektor konzipiert werden. Hierzu ist eine ausgiebige Literaturrecherche nötig, deren Ergebnisse zu dokumentieren sind. Anschließend sollen die Konzepte für Mehrkern-Prozessor-Systeme und Grafikkarten umgesetzt und ihre Leistungsfähigkeit, ihre parallele Skalierbarkeit, sowie der Speicherverbrauch mit bestehenden Lösungen verglichen werden.

Die Arbeit kann als Bachelor- oder Master-Thesis bearbeitet werden, wobei im Rahmen einer Masterarbeit auch die Implementierung einer heterogenen Lösung vorgesehen wird, bei der sowohl CPU als auch GPU gleichzeitig am Berechnungsvorgang beteiligt sind. Auch sollen mögliche Preprocessing Schritte genauer betrachtet werden.

Die Ergebnisse der Arbeit sollen abschließend zusammen mit dem Betreuer in einen bestehenden Forschungscode zur Simulation von Kohlenstoffnanoröhren integriert werden.

Empfohlene Vorkenntnisse

• Gute Programmierkenntnisse in C/C++,

• Kenntnisse in der GPU Programmierung (OpenCL, CUDA) ,

• Grundkenntnisse im Parallelen Rechnen (OpenMP, Beschleuniger)

• Gute Englisch-Lesekenntnisse (zum Verständnis der Literatur)