Theorie trifft Technologie: Cache-effiziente Algorithmen

ausführen als Zugriffe auf den Hauptspeicher machen. Dadurch kann das
traditionelle von Neumann Maschinenmodell zur stumpfen Waffe bei der
Beurteilung effizienter Algorithmen werden. Insbesondere muss bei der
Algorithmenentwicklung berücksichtigt werden, dass Daten, die in
Zwischenspeichern (Caches) vorliegen, deutlich schneller verfügbar
sind. Der Vortrag gibt einen Überblick über Techniken zur effizienten
Nutzung von Caches. Das reicht von einfachen Maßnahmen des Layouts von
Datenstrukturen über algorithmische Techniken zur Beherrschung
unvorhersagbarer Zugriffsmuster bis zu theoretischen Überlegungen, die
erst eine zufriedenstellende Analyse Cache-effizienter Algorithmen
erlauben. Die Techniken werden an konkreten Beispielen erläutert:
Matrixmultiplikation, ein Optimierungsproblem beim Airline Crew
Scheduling, Zufallspermutationen und Prioritätslisten.