Optimierung des Matrix-Vektor-Produkts für schwach besetzte Matrizen [Fortsetzung]

Am Institut für Computational Science werden gegenwärtig Löser für sehr grosse Eigenwertprobleme entwickelt, die beim Entwurf von Teilchenbeschleunigern auftreten. Die reell-symmetrischen Eigenwertprobleme der Form A x = λ Mx entstehen (unter anderem) bei der Diskretisierung der zeit-harmonischen Maxwell-Gleichungen mit finiten Elementen. Da es sich um 3-dimensionale Probleme handelt, können die Matrizen A und M sehr gross werden (Ordnung > 1 Million). Allerdings sind wegen des Finite Elemente-Ansatzes die Matrizen sehr schwach besetzt. Typischerweise sind weniger als 40 Elemente pro Zeile nicht null. Beim Lösen des Eigenwertproblems mit einem Krylow-Raumverfahren oder mit dem Jacobi-Davidson-Algorithmus ist die Matrix-Vektor-Operation die zeitaufwendigste Operation. Eine effiziente Implementation ist deshalb essentiell.

Ausgehend von Ideen von Roman Geus und Stefan Röllin [2] hat Donat Perler [1] in einer kürzlich beendeten Semesterarbeit die Implementation des Matrix-Vektor-Produkt in der Programm-Paket Trilinos [3] untersucht. Er hat gezeigt, dass die Implementation der schwach-besetzten Matrix-Vektor-Produkts in Trilinos signifikant verbessert werden kann. Er erreichte Speedups von über 5 auf Pentium 4 und Opteron basierten Rechnern. Die Techniken die bei dieser Arbeit untersucht wurden waren

Register Blocking Matrix Reordering Software Pipelining

Loop Unrolling Prefetching Streaming

In der Abeit hat sich das Speicherinterface als limitierender Faktor herausgestellt. Deshalb ist die Verkleinerung der Datenmenge, die Minimierung der Zugriffe auf den Hauptspeicher und das Caching von zentraler Bedeutung. Das parallele Ausführen der Matrix-Vektor-Multiplikation wurde in der Arbeit nicht untersucht. 

In diesem Projekt soll die Semesterarbeit von Donat Perler weitergeführt werden und das parallele Matrix-Vektor-Produkt untersucht werden. In der parallelen Umgebung macht die Kommunikation einen grossen Teil der Laufzeit aus. Diese muss für das Matrix-Vektor-Produkt untersucht und eventuell optimiert werden. 

Vorgegeben ist ein in C++ geschriebenes Program, das mit den Strukturen von Trilinos [3] arbeitet. 

1. D. Perler. Optimierung des Matrix-Vektor-Produkts für schwach besetzte Matrizen, Semesterarbeit, Institut für Computational Science, ETH Zürich. Dezember 2004.
2. R. Geus and S. Röllin. Towards a fast parallel sparse matrix-vector multiplication, Parallel Computing 27 (2001), pp. 883-896.
3. The Trilinos Project Home Page

Prof. Peter Arbenz

Institut für Wissenschaftliches Rechnen
ETH Zentrum HRS G27

Tel.: 632 7432

Email: arbenz@inf.ethz.ch