Nachwuchsgruppe „Speicherhierarchie-optimale Matrixmultiplikations-Programme”
Freie Stellen
Kurze Projektbeschreibung
In vielen Daten-intensiven Anwendungen in Bereichen wie der Bioinformatik, Netzwerkanalyse, Optimierung und Simulation, erwarten wir von einem Computer vor allem, dass er schnell ist. Die Laufzeit eines Programms auf einem modernen Computer hängt allerdings von vielen Aspekten ab. Viele Anwendungen in diesem Umfeld können als einfache Operationen auf einer dünn besetzten Matrix formuliert werden. Dabei ist entscheidend, dass moderne Computer nicht nur einen, sondern eine Hierarchie verschiedener Speicher haben. Deren Charakteristik reicht von sehr klein und sehr schnell (Register, Cache) bis sehr groß und relativ langsam (Festplatte). Wenn ein Programm etwa die Zwischenergebnisse auf der Festplatte speichern muss, ergibt sich dessen Laufzeit in erster Linie aus der Anzahl von Zugriffen auf die Festplatte.
Für das Multiplizieren einer voll besetzten Matrix mit einem Vektor sind (im wesentlichen) optimale Algorithmen bekannt. Dabei ist die mathematischen Aussage, wieviele Speicherzugriffe ein korrekter Algorithmus mindestens ausführen muss, wichtig. Sie zeigt nicht nur, dass ein Algorithmus so gut wie optimal ist, sondern auch, dass weitere Verbesserungen die aktuellen Modellannahmen verletzen müssen.
In jüngster Zeit wurde ein Algorithmus für dünn besetzte Matrizen entwickelt, dessen Qualität nur von der Größe der Matrix und der Anzahl der Einträge abhängt. Darüberhinaus wurde bewiesen, dass der Algorithmus für eine zufällig gewählte Matrix (im wesentlichen) optimal ist. Da in fast allen Anwendungen eine gewisse Struktur zu erwarten ist, ist es möglich, dass in der Praxis auftretende Matrizen schneller verarbeitet werden können. Dementsprechend ist es ein zentrales Ziel des Projekts, für eine beliebige Matrix A ein Speicherzugriff-optimales Programm zu finden (zu berechnen), das bei Eingabe eines Vektors x das Produkt Ax erzeugt.
Projektbeschreibung (englisch)