|
Optimierung dynamischer Datenstrukturen bezüglich ihrer Cacheleistung
Wir wollen zur Optimierung des Layouts dynamischer Datenstrukturen beitragen.
Es gilt, das Layout so zu optimieren, daß man auf die Datenstruktur in
modernen Speicherhierarchien effizient zugreifen kann. Damit wird einer der
zentralen Engpässe moderner Rechnersysteme, der Speicherzugriff via
Caches, entlastet.
Seit Einführung kleiner, schneller Pufferspeicher in der
Speicherhierarchie, den sogenannten Caches, wurden viele
Methoden vorgeschlagen, Speicherzugriffe numerischer Anwendungen, die
vornehmlich Reihungen als Datenstrukturen verwenden, zu optimieren.
Vernachlässigt wurde hingegen die Optimierung von Zugriffen auf
dynamische Datenstrukturen wie Listen, Bäume und Graphen.
Von den verschiedenen vorgeschlagenen Optimierungsverfahren wollen wir
uns hier der Verringerung von Hauptspeicherzugriffen auf dynamische
Datenstrukturen durch automatische Ãœbersetzeroptimierungen widmen.
Dazu sollen Analyse- und Transformationstechniken untersucht und
entwickelt werden, die folgende Fragen beantworten: Was sind für den
Zugriff kritische Datenstrukturen? Wie kann man diese besser im
Speicher anordnen? Kann man diese Anordnung durch
Programmtransformation unter Erhalt der ursprünglichen Semantik
herstellen? Dazu soll die Typstruktur eines Programmes
analysiert werden, um die Datenstrukturen zu interpretieren.
Programmglobale Codeanalysen können eine Aussage über die Anzahl der
Zugriffe auf eine Datenstruktur machen. Lokale Analysen der
Zugriffspfade gewährleisten die Korrektheit der Transformationen.
Die durch diese Analysen gewonnene Information soll direkt f"ur
ergänzende Optimierungen zum Verstecken der Latenzzeiten
verbleibenderf Hauptspeicherzugriffe verwendet werden.
Die gefundenen Methoden sollen exemplarisch in einem vorhandenen
Übersetzer für eine objektorientierte Sprache mit einer modernen
Zwischensprache implementiert und erprobt werden.
Projektbeteiligte
Software in diesem Projekt
Publikationen zum Projekt
| |
