TifaMMy

Cache-effiziente Verfahren zur Matrixmultiplikation auf Basis der Peanokurve

Die Multiplikation zweier Matrizen stellt zwar algorithmisch zunächst keine große Herausforderung dar, man stellt aber schnell fest, dass eine triviale Implemetierung durch verschachtelte Schleifen, also etwa

  for(int i=0;i<n;i++)
     for(int j=0;j<n;j++) {
        C(i,j) = 0;
        for(int k=0;k<n;k++)
           C(i,j) += A(i,k) * B(k,j)
     };

eine mehr als enttäuschende Performance aufweist. Dies liegt vor allem an einer schlechten Cache-Ausnutzung.

Mit Hilfe eines Ansatzes, der auf einer Peanokurve basiert, lässt sich nun ein Algorithmus formulieren, der über eine rekursive Blockmultiplikation eine inhärent cache-effiziente Implementierung der Matrixmultiplikation liefert. Die Ansätze lassen sich auf andere Matrixoperationen, wie z.B. die LR-Zerlegung, übertragen.

TifaMMy - TifaMMy isn't the fastest Matrix Multiplication, yet

TifaMMy ist der Auftakt zu einer library für inhärent Cache-effiziente Matrix-Operationen (Multiplikation von Matrizen, LR-Zerlegung, etc.) basierend auf der Peano-Multiplikation. Fernziel ist ein Funktionsumfang gemäß BLAS oder LAPACK.

TifaMMy ist ein Open-Source-Projekt basierend auf den studentischen Arbeiten von (bisher) Christian Mayer und Alexander Heinecke und soll durch weitere studentische Arbeiten stetig weiterentwickelt werden.

Zu vergebende Themen

1. Dünnbesetzte Matrizen: innerhalb TifaMMys wird eine Matrix über eine hierarchische Zerlegung gespeichert (ähnlich zu Oktalbäumen). Das entsprechende Datenformat lässt sich relativ kanonisch für den Fall dünnbesetzter Matrizen erweitern und optimieren. Implementierung, (parallele) Effizienz, etc. entsprechender Operationen auf dünnbesetzten Matrizen sind zu untersuchen.
2. Parallele Implementierung: In TifaMMy ist eine OpenMP-Parallelisierung implementiert für System mit gemeinsamem Speicher. Ein Projektthema könnte aber auch die Implementierung auf Compute Clustern mit verteiltem Speicher sein. Hier kann man z.B. explizite Caches auf jedem Prozessor implementieren, die die Kommunikation reduzieren.