Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Speicherhierarchie-optimale Matrixmultiplikations-Programme

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2007 bis 2015
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 35224341
 
Erstellungsjahr 2015

Zusammenfassung der Projektergebnisse

Viele Berechnungsaufgaben, wie die Multiplikation mit einer dünn-besetzten Matrix, zeichnen sich dadurch aus, dass pro Eingabeelement relativ wenige algebraische Operationen ausgeführt werden. Dementsprechend bezieht sich Effizienz hier vor allem auf die Kommunikation der Daten zu den Rechenkernen. Diese kann Teil des Programms sein, etwa wenn explizit Nachrichten von Rechenknoten zu Rechenknoten eines Hochleistungsrechners geschickt werden, oder sie kann implizit geschehen, etwa wenn eine Cache-Zeile in den Cache geladen wird. In jedem Fall kommt es darauf an, die Berechnung so zu gestalten, dass zum einen mit Daten im lokale Speicher oder Cache möglichst viel sinnvoll gerechnet wird, und dass außerdem wenige Nachrichten geschickt bzw. Cache-Zeilen geladen werden müssen. Hier hat sich das Projekt auf zwei fundamentale Aufgabenstellungen konzentriert: SpMxV ("Sparse Matrix x Vector"): die Multiplikation einer dünn besetzten Matrix mit einem Vektor. Dies steht für eine Klasse von Aufgabenstellungen, die selbst dann schwierig sind, wenn die Struktur im vorhinein bekannt ist. List-Ranking ist eine der einfachsten Aufgabenstellungen auf einem Graphen. Hier ergibt sich der genaue Kommunikationsbedarf erst aus der Analyse der Eingabeinstanz, wodurch die Kommunikationsaufgabe im ganzen schwieriger wird. Außerdem haben wir im Kontext der so genannten dünnen Gitter, einer numerischen Diskretisierungsmethode, einen Teil dieser theoretischen Einsichten in einem konkreten Kontext genutzt. Ein wichtiger Aspekt dieser Forschung war das Konsolidieren, also Bekanntes geschickt zusammenzufügen, Parameterbereiche zu erweitern und so die Grenzen der bekannten Techniken auszuloten. Dies ist im Kontext von SpMxV, List-Ranking und Baumweite Algorithmen hervorragend gelungen. (Fast alle Ergebnisse sind für das parallele I/O-Modell PEM formuliert.) Auch ein Teil der unteren Schranken sind von dieser Gestalt, anspruchsvolle Arbeit sorgfaltig und präzise ausgeführt. Zum anderen ist uns an vielen Stellen gelungen, neuartige Lösungen zu formulieren: Etwa das Multiplizieren einer dichten und einer dünn besetzten Matrix, die Verbindung von SpMxV zu map-reduce, und die Algorithmen und Kommunikationsschema für dünne Gitter. Auch die im Rahmen der dünnen Gitter implementierten Programme sind neue und in ihrem Kontext die schnellsten im Moment bekannten. Außerdem konnten wir mehrere neue Fragestellungen als fundamental identifizieren: Wie sehen für SpMxV im I/O Modell schwierige Matrizen aus? Was ist die "richtige" untere Schranke und Modellbildung für List-Ranking?

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2026 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung