Universitšt Karlsruhe
Projekt ACODA

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

Alumni
Dr. Götz Lindenmaier

Software in diesem Projekt

Jack -- Java Compiler Karlsruhe
Ein √úbersetzer, basierend auf Firm, der Java in Bin√§rcode √ľbersetzt.
libFirm
Eine C Implementierung der Zwischensprache Firm.

Publikationen zum Projekt

2002
Lindenmaier, libFIRM -- A Library for Compiler Optimization Research Implementing FIRM
Login
Links