SFB 376 - B3

Werkzeuge zur Entwicklung und Implementierung paralleler Algorithmen

Die Arbeiten in diesem Projektbereich waren von dem Anspruch geprägt, Methoden und Werkzeuge zu entwickeln, mit denen die effiziente Nutzung paralleler Systeme systematisiert und automatisiert wid. Unsere Arbeiten waren das Teilprojekt B3 des Sonderforschungsbereichs 376 "Massive Parallelität - Algorithmen, Entwurfsmethoden, Anwendungen".

Wir haben dazu das Ziel verfolgt, Expertenwissen zur parallelen Programmierung durch Werkzeuge so verfügbar zu machen, dass Anwender, die solches Wissen nicht haben, trotzdem Parallelrechner effizient nutzen können. Schritte der Algorithmenauswahl, Programmentwicklung und -implementierung für parallele Lösungen wurden automatisiert. Solche Automatisierung durch Werkzeuge kann man natürlich nur in Gebieten erreichen, wo das Expertenwissen hinreichend systematisierbar ist. Wir haben uns deshalb auf der Seite der Anwendungen auf spezielle Aufgabenfelder und auf der Seite der Parallelisierungstechniken auf bestimmte Algorithmenklassen sowie Übersetzungsverfahren zur Parallelisierung konzentriert.

Mit unseren Vorarbeiten hatten wir die grundlegenden Mechanismen des Werkzeugsystems geschaffen und erste algorithmische Anwendungsfelder dort eingebracht sowie Parallelisierungsverfahren zur Übersetzung von Schleifenprogrammen fortentwickelt.

Das Werkzeugsystem war so konzipiert, dass Expertenwissen ganz unterschiedlicher Ausprägung wiederverwendet werden kann: von speziellen Software-Herstellungsprozessen und Software-Architekturen über die Auswahl und Parametrisierung von Programmschemata bis hin zur technischen Ansteuerung verschiedener Parallelrechnerplattformen. Wir hatten zunächst für die algorithmischen Themen "Paralleles Branch-&-Bound" und "Paralleles Sortieren" jeweils ein solches Werkzeugsystem konstruiert. Aus den Erfahrungen damit entwickelten wir eine Struktur solcher Werkzeugsysteme und eine Vorgehensweise für ihre Konstruktion, die auch für andere Themen anwendbar war. Außerdem ergänzten wir sie um eine generische graphische Benutzeroberfläche und um die Ansteuerung weiterer Parallelrechnerplattformen.

Den zweiten Arbeitsschwerpunkt unseres Teilprojektes bildete das Thema Analyse und Transformation paralleler Programme. Hier konzentrierten wir uns auf die Parallelisierung regulärer Ablauf- und Datenstrukturen (Schleifen, Arrays), da hier die größten Effekte erzielbar waren. Unsere Verfahren zur systolischen Parallelisierung von Schleifen wurden um ein Modell erweitert, mit dem mehrere Schleifenschachteln eines Programms zusammenhängend parallelisiert werden. Zur Transformation von Schleifen mit dem Ziel, ihre Parallelisierbarkeit zu verbessern, bauten wir eine Experimentierumgebung auf, um Transformationsstrategien zu untersuchen und zu automatisieren.

Eine Entwicklungsumgebung für parallelisierende Übersetzer, die zunächst für VLIW-Zielprozessoren konzipiert war, verallgemeinerten wir hinsichtlich der Zielprozessoren und der Einsatzmöglichkeiten ihrer Analyseverfahren. Damit waren die Komponenten dieser Umgebung auch für die Analyse- und Transformationsaufgaben unseres Vorhabens einsetzbar.

Leitung

Uwe Kastens

Mitarbeiter

Christoph Eilinghoff
Friedrich Wichmann
Peter Pfahler
Adrian Slowik
Dinh Khoi Le

Arbeitsschwerpunkte

Zusammenarbeit mit anderen Teilprojekten

Die Kooperation mit anderen Vorhaben des SFB konzentrierte sich in der ersten Antragsphase auf die Entwicklung von Werkzeugsystemen zur Konfigurierung paralleler Programme für ausgewählte Anwendungsbereiche. Die Werkzeugsysteme für die algorithmischen Anwendungsbereiche Branch-&-Bound und Sortierverfahren entstanden in Kooperation mit Teilprojekt A1 und Teilprojekt A2 .

Für die Entwicklung des Werkzeugsystems im Anwendungsgebiet Produktionsplanungs- und Steuerungssysteme war das Teilprojekt C2 unser zentraler Kooperationspartner. Das hier erarbeitete gemeinsame Verständis zur Beschaffenheit solcher Systeme diente als Grundlage für die Integration von zunächst sequentiellen Bausteinen in die Anwendungsbibliothek. Arbeiten an der Parallelisierung der PPS-Algorithmen wurden darauf aufgebaut.

Für unsere Verfahren zur automatischen Parallelisierung regulärer Algorithmen haben wir in Teilprojekt A3 einen Kooperationspartner gefunden, der Anwendungsprogramme mit regulärer Struktur verwendete. Hier erprobten wir gegenwärtig unsere Verfahren an praxisnahen Programmen, deren Komplexität über die von Fallbeispielen hinausgeht. Die in diesem Zusammenhang erzielten Ergebnisse flossen in die Weiterentwicklung der eingesetzten Verfahren ein.

Die Analyse paralleler Programme erweiterte unseren Forschungsbereich um eine neue Richtung. Sie wurde Informationen über Programme beschaffen, die Verfahren aus Teilprojekten A2 und Teilprojekt B4 zu effizienteren Lösungen verholfen haben. Teilprojekt A2 nutzte Analyseergebnisse bei der Plazierung von Daten und Prozessen. Die Zusammenarbeit mit Teilprojekt B4 begann mit der automatischen Instrumentierung von Programmen für Shared-Memory und Message-Passing Systeme. Mit ihren Ergebnissen wurden Modellannahmen validiert und Engpässe aufgedeckt.

Kontakt

Falls Sie Probleme, Fragen, Anregungen oder Anmerkungen hinsichtlich der Arbeit unseres Teilprojekts des Sonderforschungsbereichs haben, können Sie uns über e-mail: ag-kastens (at) uni-paderborn (dot) de
erreichen.