Explicit and implicit parallel functional programming : concepts and implementation

Die vorliegende Arbeit beschreibt Konzepte zur parallelen Programmierung mit funktionalen Sprachen und deren Implementierung, insbesondere parallele Haskell-Dialekte und die Sprache Eden. Wir gehen der Frage nach, welche grundlegenden Koordinationskonstrukte und welcher Grad an expliziter Ausführungskontrolle nötig und nützlich für eine funktionale Implementierung paralleler Koordination sind. In der heutigen Zeit von globaler Vernetzung und Mehrkernprozessoren wird die parallele Programmierung immer wichtiger. Dennoch sind nach wie vor Programmiermodelle verbreitet, die kaum von den Hardwareeigenschaften abstrahieren und sich daher zwangsläufig in technischen Details verlieren. Funktionale Sprachen erlauben aufgrund ihrer Abstraktion und mathematischen Natur, die gegenüber sequenziellen Programmen erheblich höhere Komplexität paralleler Programme zu erfassen, sie ermöglichen ein abstrakteres Nachdenken über parallele Programme. Dabei taucht unvermeidlich die oben formulierte Leitfrage auf, zu welchem Grad explizite Kontrolle der Ausführung nötig und nützlich ist, um effiziente parallele Programme zu schreiben, wenn diese wiederum abstraktere Kontrollkonstrukte implementieren und insbesondere in der sog. skelettbasierten Programmierung, welche gängige Muster der Parallelverarbeitung abstrakt als Funktionen höherer Ordnung beschreibt. Wir beschreiben unsere Implementierung für die Sprache Eden, welche hierarchisch in Schichten organisiert ist. Die unterste, direkt implementierte Schicht stellt nur sehr einfache Primitive für Parallelverarbeitung bereit, komplexere Kontrollkonstrukte werden in der funktionalen Sprache Haskell implementiert. Neben der Implementierung von Eden stellen die implementierten Primitive für sich genommen bereits Kontrollkonstrukte zur Parallelverarbeitung dar. Aus der Implementierung abgeleitet wird die funktionale Sprache EDI vorgeschlagen, die auf niedrigem Abstraktionsniveau Haskell um orthogonale, grundlegend notwendige Konstrukte zur Koordination paralleler Berechnungen erweitert: Auswertungskontrolle, Nebenläufigkeit, Prozesserzeugung, Kommunikation und Information über verfügbare Ressourcen. Die grundlegende Systemunterstützung von EDI und das Implementierungskonzept lassen sich mit nur geringen Modifikationen auf andere Implementierungen (und Berechnungssprachen) übertragen. Aufgrund seiner Flexibilität und der funktionalen Basis bietet unser Ansatz großes Potenzial für modellgestützte Ansätze zur automatischen Verwaltung paralleler Berechnungen und für die Verifikation von Systemeigenschaften. Wir beschreiben das allgemeine Design eines generischen Systems zur hierarchischen Implementierung paralleler Haskell-Erweiterungen, eine Prototyp-Implementierung für adaptive Scheduling-Konzepte und eine Machbarkeitsstudie für virtuellen globalen Speicher. Anwendungsgebiet für die Evaluation der Sprache EDI ist die Implementierung abstrakterer Konstrukte, insbesondere paralleler Skelette, auf die wir uns in einem weiteren Teil der Dissertation konzentrieren. Skelette beschreiben parallelisierbare Algorithmen und parallele Verarbeitungsmuster und verbergen ihre parallele Implementierung. Somit bieten sie ein (gegenüber der Programmierung mit Eden oder EDI) höheres Abstraktionsniveau, entziehen aber dem Programmierer die explizite Parallelitätskontrolle. Für einen Vergleich der Ausdrucksstärke und Pragmatik werden exemplarisch Implementierungen für verschiedene parallele Skelette in der Sprache Eden und ihrer Implementierungssprache EDI beschrieben. Wir untersuchen neben einschlägigen Vertretern dieser algorithmischen Skelette eine andere Art Skelette, welche anstelle der Algorithmik die Interaktion von Prozessen in regulärer Anordnung beschreiben und für die wir den Begriff Topologieskelette geprägt haben. Durch die zusätzlichen nicht-funktionalen Konstrukte in Eden haben Eden und EDI im Ergebnis die gleiche Ausdrucksstärke, wobei aber die abstrakteren Eden-Konstrukte essenzielle Seiteneffekte und Nebenläufigkeit verbergen. Durch die in EDI (im Gegensatz zu Eden) explizite Kommunikation lassen sich Skelett-Implementierungen besser lesen und an besondere Bedürfnisse anpassen. Die explizitere Sprache EDI findet ihr originäres Anwendungsgebiet in der Skelettimplementierung, -anpassung und -optimierung.