Prof. Dr. habil. Sergei Gorlatch
Skelettbasierter Entwurf paralleler und verteilter Software
In den 60er Jahren geriet die Softwareentwicklung aufgrund der Verwendung der GoTo-Primitive in Programmiersprachen in eine "Softwarekrise", die den gegenwärtigen Schwierigkeiten der Parallelprogrammierung sehr ähnlich war. Die Krise wurde im Wesentlichen durch strukturierte Programmierung überwunden, indem das GoTo vollständig durch alternative höhere Programmkonstrukte - Komposition, Schleife und bedingte Programmausführung ersetzt wurde.
Analog hierzu ersetzen wir im Bereich paralleler und verteilter Programmierung die in diesem Bereiche traditionell verwendeten low-level Primitive send/receive zur Kommunikation bzw. lock/unlock zur Synchronisation durch höhere alternative Programmkonstrukte [1]. Ziel ist, dass die Verwendung expliziter Kommunikation und Synchronisation in einer strukturierten, disziplinierten Form erfolgt, beispielsweise unter ausschließlicher Benutzung von sog. Skeletten. Skelette sind wiederkehrende Muster, die als kollektive Operation effizient auf
verschiedenen parallelen Rechnerarchitekturen implementiert werden können [4].
Die Verwendung von Skeletten bewirkt auf natürliche Weise eine Rollenverteilung zwischen dem Anwender, der Skelette verwendet, und dem Systemprogrammierer, der sie zur Verfügung stellt. Diese Rollenverteilung hat zwei entscheidende Vorteile: 1) Probleme bei der Parallelisierung bleiben dem Anwender verborgen, da sie in den Skeletten gelöst werden, und 2) Implementierungen von Skeletten werden von den Systemprogrammierern auf die Gegebenheiten konkreter Rechnerarchitekturen abgestimmt und sind daher sehr effizient.
Im Rahmen des DFG-Projekts COFFEE wurden weit verbreitete Skelette in Form eines einheitlichen Kataloges beschrieben. Es wurden zwei neue Skelette formal eingeführt und implementiert: der verteilbare Homomorphismus und der Double-Scan [2]. Es wurde gezeigt, dass beide neuen Skelette auf unterschiedlichen parallelen Architekturen effizient implementierbar sind. Dabei wurden mehrere anwendungsbezogene Fallstudien untersucht, beispielsweise die Lösung von Gleichungssystemen oder die schnelle Fourier Transformation, die mit Hilfe der neuen Skelette einfach beschreibbar sind. Weiterhin wurden die Kosten (Produkt aus Prozessoren und Laufzeit) der Skelett-Implementierungen untersucht und die Kostenoptimalität (keine extra Kosten für Parallelität) für den
Double-Scan bewiesen [5].
Drittmittelgeber:
Beteiligte Wissenschaftler:
Veröffentlichungen:
|