Prof. Dr. Herbert Kuchen
Parallel Programmierung mit Algorithmischen Skeletten
Die parallel Programmierung von Rechnern mit einem gemeinsamen Speicher erfolgt heute vorwiegend auf der
Grundlage von Nachrichtenaustausch und dafür geschaffenen Bibliotheken wie MPI. Hiermit lassen sich zwar
effiziente und plattformunabhängige Programmsysteme erstellen, allerdings ist das Programmierniveau noch
vergleichsweise niedrig und die Programmierung entsprechend aufwändig und fehleranfällig.
Demzufolge gibt es viele Ansätze, die parallele Programmierung zu vereinfachen und das Programmierniveau
anzuheben.
Im Rahmen dieses Projekts werden hier insbesondere
sogenannte algorithmische Skelette betrachtet. Dabei handelt es sich um typische parallele Programmiermuster, die
den Benutzern als polymorphe Funktionen höherer Ordnung zur Verfügung gestellt werden. Sie sind
für alle in Frage kommenden Plattformen effizient parallel implementiert, so dass sich das Problem, eine
parallele Applikation zu erstellen, darauf beschränkt, die vorgegebenen Skelette in geeigneter Weise und
Reihenfolge aufzurufen.
Das Konzept der algorithmischen Skelette stammt
ursprünglich aus der funktionalen Programmierung, aber auch imperative Gastsprachen wie z. B. Skil
wurden bereits erprobt. Der große Durchbruch der Skelette ist dennoch bisher ausgeblieben. Zwei wesentliche
Gründe hierfür sind die fehlende Standardisierung der Skelette und die Notwendigkeit, für die
Verwendung der Skelette eine neue Programmiersprache zu lernen. Zu letzterem sind nur wenige Anwender bereit;
sie bevorzugen stattdessen die Programmiersprachen, die sie kennen und in vielen parallelen Anwendungen erprobt
haben, wie z. B. C. und C++. Im Rahmen des laufenden Projekts wurden die Skelette daher in Form einer für
Sprachen wie C++ und C verwendbaren Bibliothek verfügbar gemacht. Weiterhin wurde der bereitgestellte
Satz an Skeletten nach einer vorherigen intensiven Diskussion in der einschlägigen Community festgelegt, so
dass der vorliegende Ansatz als Vorschlag für eine Standardisierung zu verstehen ist.
Die genannte Bibliothek bietet neben datenparallelen
auch taskparallele Skelette und ermöglicht, diese auf der Grundlage einer 2-Ebenen-Architektur zu
verknüpfen. Genauer gesagt, kann eine taskparallele Berechnung Prozesse enthalten, die intern datenparallel
arbeiten. Anhand von ausgewählten Benchmarks wurde nachgewiesen, dass das so erreichbare, höhere
Programmierniveau nicht auf Kosten der Effizienz geht, sondern dass sich eine Performance erzielen lässt, die
mit der von handgeschiebenem C++-Code mit MPI-Aufrufen vergleichbar ist. Unter den betrachteten Benchmarks
waren Beispielprobleme wie das Gauß'sche Eliminationsverfahren, Samplesort, Matrixmultiplikation, FFT,
Raytracing und Kantendetektion in Bildern. In
der Zukunft wird der Satz an Skeletten ergänzt und die Zusammenarbeit der task- und datenparallelen
Skelette verbessert werden. Weiterhin sollen Werkzeuge für das Programmieren mit algorithmischen Skeletten
entwickelt werden. Hierzu zählt u. a. ein Optimierer für Folgen von Skeletten.
Beteiligte Wissenschaftler:
Veröffentlichungen:
| 
