Explicit and implicit parallel functional programming [Elektronische Ressource] : concepts and implementation / vorgelegt von Jost Berthold

Sujets

• Informatik

Informations

• Publié par: philipps-universitat_marburg
• Publié le: 01 janvier 2008
• Nombre de lectures: 15
• Langue: Deutsch
• Poids de l'ouvrage: 2 Mo

Extrait

Explicit and Implicit
Parallel Functional Programming:
Concepts and Implementation
Dissertation
zur
Erlangung des Doktorgrades
der Naturwissenschaften
(Dr. rer.nat.)
dem
Fachbereich Mathematik und Informatik
¨der Philipps-Universitat Marburg
vorgelegt von
Jost Berthold
aus Kassel
Marburg/Lahn, 2008Vom Fachbereich Mathematik und Informatik
der Philipps-Universit¨at Marburg als Dissertation
am 6.6.2008 angenommen.
Erstgutachter: Prof. Dr. Rita Loogen
Zweitgutachter: Prof. Dr. Greg Michaelson
Tag der mu¨ndlichen Pru¨fung am 16.6.2008Zusammenfassung (deutsch)
Die vorliegende Arbeit beschreibt Konzepte zur parallelen Programmierung mit
funktionalenSprachenundderenImplementierung,insbesondereparalleleHaskell-
DialekteunddieSpracheEden. WirgehenderFragenach, welche grundlegenden
Koordinationskonstrukte und welcher Grad an expliziter Ausfu¨hrungskontrolle
n¨otig und nu¨tzlich fu¨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 ab-
strahieren und sich daher zwangsl¨aufig in technischen Details verlieren. Funk-
tionaleSprachenerlaubenaufgrundihrerAbstraktionundmathematischenNatur,
diegegenu¨bersequenziellen Programmenerheblichh¨ohereKomplexit¨atparalleler
Programme zu erfassen, sie erm¨oglichen ein abstrakteres Nachdenken u¨ber paral-
lele Programme. Dabei taucht unvermeidlich die oben formulierte Leitfrage auf,
zu welchem Grad explizite Kontrolle der Ausfu¨hrung n¨otig und nu¨tzlich ist, um
effiziente parallele Programme zu schreiben, wenn diese wiederum abstraktere
Kontrollkonstrukte implementieren und insbesondere in der sog. skelettbasierten
Programmierung, welche g¨angige Muster der Parallelverarbeitung abstrakt als
Funktionen h¨oherer Ordnung beschreibt.
Wir beschreiben unsere Implementierung fu¨r die Sprache Eden, welche hier-
archisch in Schichten organisiert ist. Die unterste, direkt implementierte Schicht
stelltnursehreinfachePrimitivefu¨rParallelverarbeitungbereit,komplexereKon-
trollkonstrukte werden in der funktionalen Sprache Haskell implementiert.
Neben der Implementierung von Eden stellen die implementierten Primi-
tive fu¨r sich genommen bereits Kontrollkonstrukte zur Parallelverarbeitung dar.
Aus der Implementierung abgeleitet wird die funktionale Sprache EdI (‘ED’en-
’I’mplementierungssprache) vorgeschlagen, die auf niedrigem Abstraktionsniveau
Haskell um orthogonale, grundlegend notwendige Konstrukte zur Koordination
paralleler Berechnungen erweitert: Auswertungskontrolle, Nebenl¨aufigkeit, Pro-
zesserzeugung, Kommunikation und Information u¨ber verfu¨gbare Ressourcen.
Die grundlegende Systemunterstu¨tzung von EdI und das Implementierungs-
konzept lassen sich mit nur geringen Modifikationen auf andere Implementierun-
gen (und Berechnungssprachen) u¨bertragen. Aufgrund seiner Flexibilit¨at und
der funktionalen Basis bietet unser Ansatz großes Potenzial fu¨r modellgestu¨tzte
Ans¨atze zur automatischen Verwaltung paralleler Berechnungen und fu¨r die Ve-
rifikation von Systemeigenschaften. Wir beschreiben das allgemeine Design eines
generischen Systems zur hierarchischen Implementierung paralleler Haskell-Er-
weiterungen, eine Prototyp-Implementierung fu¨r adaptive Scheduling-Konzepte
und eine Machbarkeitsstudie fu¨r virtuellen globalen Speicher.
Anwendungsgebiet fu¨r die Evaluation der Sprache EdI ist die Implemen-
tierung abstrakterer Konstrukte, insbesondere paralleler Skelette, auf die wir uns
iiiineinemweiteren TeilderDissertationkonzentrieren. Skelettebeschreiben paral-
lelisierbare Algorithmen und parallele Verarbeitungsmuster abstrakt als Funktio-
nenh¨ohererOrdnungundverbergenihreparalleleImplementierung. Somitbieten
sie ein (gegenu¨ber der Programmierung mit Eden oder EdI) h¨oheres Abstrak-
tionsniveau,entziehenaberdemProgrammiererdieexpliziteParallelit¨atskontrolle.
Fu¨r einen Vergleich der Ausdrucksst¨arke und Pragmatik werden exemplarisch
Implementierungen fu¨r verschiedene parallele Skelette in der Sprache Eden und
ihrer Implementierungssprache EdI beschrieben. Wir untersuchen neben ein-
schl¨agigen Vertretern dieser “algorithmischen Skelette” eine andere Art Skelette,
welcheanstellederAlgorithmikdieInteraktionvonProzesseninregul¨arerAnord-
nung beschreiben und fu¨r die wir den Begriff Topologieskelette gepr¨agt haben.
Durch die zus¨atzlichen nicht-funktionalen Konstrukte in Eden haben Eden
und EdI im Ergebnis die gleiche Ausdrucksst¨arke, wobei aber die abstrakteren
Eden-Konstrukte essenzielle Seiteneffekte und Nebenl¨aufigkeit verbergen. Durch
die inEdI (im Gegensatz zu Eden) explizite Kommunikation lassen sich Skelett-
Implementierungen besser lesen und an besondere Bedu¨rfnisse anpassen. Die
explizitere SpracheEdI findet ihr origin¨ares Anwendungsgebiet in der Skelettim-
plementierung, -anpassung und -optimierung. Demgegenu¨ber ist ein klarer Plus-
¨punktvonEdendieautomatische(durcheineTypklasseundgeeigneteUberladung
definierte) Stream- und Tupelkommunikation. Letztere kann inEdI unver¨andert
u¨bernommen werden, sollte hier aber, gem¨aß der EdI-Philosophie, explizit und
gezielt vom Programmierer eingesetzt werden.
¨Ergebnisse im Uberblick:
• die Definition der Sprache EdI, Haskell mit expliziten Prozesskontroll-
und Kommunikationskonstrukten. EdI erweitert Haskell um orthogonale,
grundlegend notwendige Konstrukte zur Koordination paralleler Berech-
nungen: Auswertungskontrolle, Nebenl¨aufigkeit, Prozesserzeugung, Kom-
munikationundInformationu¨berverfu¨gbareRessourcen. Einsatzgebiet der
Sprache ist die Implementierung komplexerer Koordinationskonstrukte.
• eine strukturierte Implementierung von Eden, deren Konzepte in einem
allgemeineren Kontext tragf¨ahig sind.
• das Design und eine Prototypimplementierung fu¨r ein generisches System
zurImplementierungabstraktererKontrollkonstrukte,insbesonderefu¨reine
automatisierte dynamische Steuerung paralleler Berechnungen.
• neu entwickelte bzw. alternative Skelett-Implementierungen fu¨r algorith-
mische und Topologie-Skelette, fu¨r einen Vergleich von EdI und Eden.
• der exemplarische Nachweis, dass funktionale Sprachen ein ad¨aquates Ab-
straktionsniveaubieten,umStrukturenderParallelverarbeitungzuerfassen.
ivAbstract
This thesis investigates the relation between the two conflicting goals of explicit-
ness 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 proposalof a Haskell extension for explicit low-level coordination, andto a
concept of structuring implementations for parallel functional languages in layers
of increasing abstraction.
The first main part concentrates on implementation techniques and require-
ments. 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 man-
agement of parallel functional computations, major parts of which are encoded
in Haskell.
In a second main part, we concentrate on implementations of parallel skele-
tons, 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
interactionandcommunicationpatternsinregularlystructuredprocessnetworks.
In a broader context, the implementation concepts and skeleton implemen-
tations which we present underline that functional languages provide a suitable
abstraction level to reason about parallel programming and to circumvent its
complexity.
vThank You!
First of all, I would like to thank my supervisor, Prof. Dr. Rita Loogen for her
support andinspirations over the lastyears, which gaveme thechance todevelop
the ideas I am going to present.
I appreciate the opportunity to use the Beowulf clusters of the Heriot-Watt
University for my series of tests. Personal acknowledgements go to people who
I enjoyed working with and who provided important impulses for my research:
Hans-Wolfgang Loidl (formerly Heriot-Watt, now LMU Munich), Phil Trinder
and Greg Michaelson (Heriot-Watt), Kevin Hammond (St.Andrews), Abyd Al
Zain (Heriot-Watt), and my new colleague Mischa Dieterle. I also would like to
thank many nice people who are working in related areas and which I have met
at conferences and workshops. It has been a pleasure to meet you, and