Dokument 1

Prüfsumme (MD5)

Kurzfassung in Englisch:
This thesis investigates the relation between the two conflicting goals of explicitness and abstraction, for the implementation of parallel functional languages and skeletons. Necessary and useful coordination features for implementing parallel coordination in a functional implementation language will be identified, leading to the proposal of a Haskell extension for explicit low-level coordination, and to a concept of structuring implementations for parallel functional languages in layers of increasing abstraction. The first main part concentrates on implementation techniques and requirements. We are describing the layered implementation of the parallel functional language Eden, pointing out advantages of its layer structure and deriving the coordination features of the proposed explicit low-level language, named EdI. Subsequently, the presented implementation concept is generalised to the design and a prototype implementation of a generic parallel runtime system for management of parallel functional computations, major parts of which are encoded in Haskell. In a second main part, we concentrate on implementations of parallel skeletons, thereby investigating expressiveness and pragmatics of the proposed low-level language EdI in comparison to the language Eden. Exemplarily, a range of implementations is presented for data parallel skeletons implementing map, map-reduce, and the Google-MapReduce programming model. Furthermore, we present and discuss a new skeleton category: topology skeletons, which describe interaction and communication patterns in regularly structured process networks. In a broader context, the implementation concepts and skeleton implementations which we present underline that functional languages provide a suitable abstraction level to reason about parallel programming and to circumvent its complexity.

Kurzfassung in Deutsch:
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.

Das Dokument ist im Internet frei zugänglich - Hinweise zu den Nutzungsrechten