Programmorientierte Kostenmodelle für Speicherhierarchien

Das Projekt wurde durch die Deutsche Forschungsgemeinschaft (DFG) gefördert.

Die Entwicklung der Rechnerarchitekturen zeigt einen starken Trend in Richtung komplexer Speicherhierarchien. Dazu zählen schnelle Cachespeicher verschiedener Stufen, aber auch die virtuelle Speicherverwaltung insbesondere bei hierarchisch verteiltem Speicher in parallelen Systemen mit virtuell gemeinsamem Adressraum. Für eine effiziente Abarbeitung eines Programmes auf Rechnern mit Speicherhierarchien spielt die Lokalität der Speicherzugriffe eine grosse Rolle. Ziel des Projektes ist die Identifikation von zur Compilezeit analysierbaren Eigenschaften eines parallelen Programms, die die Lokalität der Speicherzugriffe und damit die Effizienz des Programmes bestimmen. Darauf aufbauend soll ein Kostenmodell entwickelt werden, das die Laufzeitmodellierung (paralleler) Programme auf Rechnern mit Speicherhierarchien gestattet und das als Grundlage für den Vergleich von Programmversionen und zur Steuerung von optimierenten Transformationen dienen soll. Das Kostenmodell basiert auf der Entwicklung von parametrisierten Laufzeitformeln, die relevante Charakteristika von Speicherhierarchien wie Speichergröße, Assoziativität und Rückschreibestrategie erfassen.

Das Verfahren soll den Programmierer in bestimmten Entwicklungsphasen während der Realisierung einer parallelen Programmapplikation begleiten und unterstützen, indem beispielsweise bereits in einer frühen Entwicklungsstufe eine effiziente Implementierung eines Algorithmus durch Laufzeitmodellierungen bestimmt werden kann. Die Grundidee des entwickelten Compilerwerkzeuges ist eine statische Analyse des Programmquelltextes und eine darauf aufbauende Erzeugung von Kostenausdrücken und parametrisierten Laufzeitfunktionen, welche die Ausführungszeit der Programmapplikation modellieren. Die Kostenfunktionen für Message Passing Programme werden in Form von parametrisierten Laufzeitfunktionen angegeben, welche zur Laufzeitvorhersage von parallelen Applikationen geeignet sind und Programmeigenschaften, wie Berechnungsaufwand und Kommunikationsoverhead, erfassen können. Mit dem entwickelten Compilerwerkzeug können verschiedene auf der Programmstruktur basierende Kostenausdrücke und -formeln erzeuget werden, welche insbesondere für eine Verfeinerung des Kostenmodells eingesetzt werden können.

Viele Programmanwendungen im Bereich des wissenschaftlichen Rechnens und der physikalischen Simulation können durch gemischt task- und datenparallele Implementierungen für Zielplattformen mit verteiltem oder gemeinsamen Adressraum profitieren. Da für parallele Implementierungen der Realisierungs-Aufwand relativ hoch ist, ist eine Abschätzung der Programmlaufzeit durch parametrisierte Laufzeitfunktionen sehr nützlich, um mögliche Performance-Vorteile einer bestimmten Programmversion auf einer parallelen Architektur, insbesondere in einer frühen Entwicklungsphase, zu erkennen. Auf diese Weise kann der Overhead von Kommunikationsoperationen portabler Message Passing Bibliotheken, wie MPI oder PVM, durch stetige Laufzeitfunktionen abgeschätzt und wenn möglich minimiert werden. Durch eine Kombination der Laufzeitvorhersage des Berechnungs- und Kommunikationsaufwandes kann der Programmierer oder Anwender seinen parallelen Algorithmus optimieren, ohne dabei zeitaufwendige und teure Laufzeitexperimente auf verschiedenen parallelen Plattformen in Kauf zu nehmen.