Analyse und Transformation paralleler Programme

Im Arbeitsgebiet "Analyse und Transformation paralleler Programme" haben wir Verfahren zur automatischen Programmparallelisierung untersucht. Solche Verfahren analysieren die regulären Programmanteile eines sequentiellen Programms und transformieren sie so in parallele Programmstücke, dass sie auf einer gegebenen parallelen Ziel-Hardware möglichst effizient ausgeführt werden können. Dazu haben wir unterschiedliche Ziel-Hardware (systolische Arrays, SIMD-Parallelrechner, SCI-gekoppelte Workstations) und verschiedene Optimierungskriterien wie z.B. Ausführungsgeschwindigkeint, Cache-Performance und Kommunikationsminimierung durch Datenlokalität betrachtet. Nähere Informationen finden sich auf diesen Seiten.

Als zweiten Schwerpunkt in diesem Teilgebiet untersuchen wir die automatische Parallelisierung und Verteilung irregulärer Anwendungen. Das übergeordnete Ziel ist es, mehrsträngig formulierte Java-Programme auf mehrere parallel arbeitende virtuelle Maschinen automatisch zu verteilen. Um effiziente Abbildung derartiger Java-Programme auf verteilte virtuelle Java-Maschinen zu erreichen, benötigt man globales Wissen über Aufrufhäufigkeiten und Beziehung zwischen einzelnen Aktivitäten und Instanzen von Klassen des Programms. Das bedeutet, dass statische und dynamische Analyseverfahren an dieser Stelle einzusetzen sind.

Durch statische Analyseinformation können z.B. Vorhersagen über Zugriffsverhalten der parallelen Ausführungsstränge auf Programmobjekte gemacht und somit wesentliche Kriterien für eine lokalitätssteigernde Objektverteilung geliefert werden. Im Gegensatz dazu sammelt die dynamische Analyse Laufzeitinformation. Sie verfolgt den Vorgang der Objekterzeugung, klassifiziert Objektzugriffe als lokal oder entfernt und ermittelt die Zugriffshäufigkeit auf Objekte. Solche Daten bilden wesentliche Grundlage für die Entscheidung über dynamische Umverteilung von Aktivitäten und Objekten. Die Kombination von statischen Analysen mit der dynamischen Analyse erweitert unsere Horizonte in der Programmanalysewelt. Hierbei interessant ist vor allem die sog. Just-In-Time-Lokalitätsoptimierung, d.h. eine Rückkopplung bei der dynamischen Analyse zur statischen Analyse. Man kann dadurch während des Programmlaufs beispielsweise auf das Einhalten von statischen Aussagen prüfen, die statisch vorbereiteten Fragen dynamisch beantworten.

Wir untersuchen momentan diese neuartigen Ansätze und wollen ein System entwickeln, das das automatische Verteilen von parallelen Java-Anwendungen auf einer verteilte Laufzeitumgebung mit effizienter Kommunikationstechnicken ermöglicht.