Praktische Informatik in der Wirtschaft (Prof. Dr. Herbert Kuchen)
Parallele Programmierung mit Algorithmischen Skeletten
Die parallel Programmierung von Rechnern mit gemeinsamem 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 geigneter 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 parallellen 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
handgeschriebenenem 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 werden 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:
|