Structured generic programming in Eden [Elektronische Ressource] / vorgelegt von Steffen Priebe

Sujets

• Informatik

Informations

• Publié par: philipps-universitat_marburg
• Publié le: 01 janvier 2007
• Nombre de lectures: 22
• Langue: Deutsch

Extrait

Structured Generic Programming
in Eden
Dissertation
zur
Erlangung des Doktorgrades
der Naturwissenschaften
(Dr. rer. nat.)
dem
Fachbereich Mathematik und Informatik
der Philipps-Universitat¤ Marburg
vorgelegt von
Steffen Priebe
aus Marburg/Lahn
Marburg/Lahn 2007Vom Fachbereich Mathematik und Informatik
¤der Philipps-Universitat Marburg als Dissertation am 3. Februar 2007 angenommen.
Erstgutachterin: Prof. Dr. Rita Loogen
Zweitgutachter: Hochschuldozent Dr. Ralf Hinze, Universitat¤ Bonn
Tag der mundlic¤ hen Prufung¤ am 9. Februar 2007Zusammenfassung
Die Ausnutzung von Parallelitat¤ ist schon immer eine fur¤ den Benutzer unsichtba-
re, aber gro e Quelle zur Verbesserung der Prozessorleistung gewesen. Da aber die
Menge an implizit nutzbarer Parallelitat¤ auf Befehlsebene begrenzt ist und gleich-
¤ ¤ ¤zeitig immer gro ere Rechenleistungen benotigt werden, erleben wir gegenwartig
eine Renaissance expliziter paralleler Techniken sowohl auf Hardware- als auch
auf Softwareebene. Aufgrund ihrer Komplexitat¤ sind parallele Systeme mit tra-
ditionellen Programmiersprachen schwer zu handhaben. Deshalb werden zuneh-
mend abstrakterehen betrachtet. Eden ist eine solche Spra-
che, die Programmkonstrukte zur gleichzeitigen Auswertung von Ausdruc¤ ken in
die funktionalehe Haskell integriert. Eden ist ein Kompromiss
zwischen vollstandiger¤ und fehlender Parallelitatskontrolle¤ durch den Program-
mierer: Es wird genugend¤ Kontrolle zur Erreichung guter Beschleunigungen be-
reitgestellt, gleichzeitig wird aber auch ein abstrakter Programmierstil durch die
¤Ubernahme weniger wichtiger Vorgange¤ durch das Laufzeitsystem gewahrt.
In dieser Arbeit stellen wir Eden drei Sprachkonzepte zur Seite, um eine noch
weitergehende Abstraktion zu erreichen:
Unter Meta-Programmierung versteht man die De nition von Programmen,
die andere Programme erzeugen oder verandern.¤ Diese Technik wird benutzt,
¤um in Haskell programmierte statische Praprozessorphasen zur Verbesse-
rung von Eden-Programmen zu konstruieren. Dadurch wird die Portabilitat¤
des Eden-Compilers verbessert, da diese Phasen nun nicht mehr in den zu-
grundeliegenden Haskell-Compiler integriert werden mussen.¤
Generische Programmierung erweitert parametrische zur strukturellen Poly-
morphie und ermoglic¤ ht daher die De nition von Funktionen, die mit belie-
bigen Argumentdatenstrukturen funktionieren. Wir beschreiben einen redu-
zierten struktur-orientierten Ansatz zur generischen Programmierung, der
fur¤ den Einsatz in Eden konzipiert wurde. Mit diesem Ansatz de nieren wir
allgemeine parallele Verarbeitungsschemata.
Moglic¤ hkeiten zur Auswertungskontrolle mussen¤ vorhanden sein, wenn in
einer funktionalen Sprache Bedarfssteuerung auf Parallelitat¤ trifft. Deren
Ziele sind gegensatzlic¤ h: Auf der einen Seite werden Auswertungen zeitlich
¤ ¤nach hinten geschoben, wahrend auf der anderen Seite fruhe Auswertung die
Gleichzeitigkeit und damit die Parallelitat¤ fordert.¤ Wir zeigen Wege auf, um
die Auswertung zu Gunsten der Pat¤ zu steuern.
In funktionalen Sprachen wird der Auswertungsverlauf durch Datenabhangigkeiten¤
sowie durch Kontrollkonstrukte bestimmt. Analog kann man bei parallelen funk-
tionalen Programmen zwischen daten-orientierten und kontroll-orientierten unter-
¤scheiden. Entsprechend zeigen wir zunachst generische Methoden zur Partitionie-
rung von Datenstrukturen sowie generische Versionen der parallelen map-Funktion.
Dann stellen wir kontroll-parallele Methoden vor, mit denen die in Eden oft vor-
kommenden Datenstrome¤ behandelt werden konnen;¤ zusatzlic¤ h zeigen wir par-
allele Schemata zur ef zienten Verarbeitung irregularer¤ Strukturen und langer
Kommunikationswege. Letztendlich vereinigen wir die gezeigten Techniken in ei-
ner Programmentwicklungsmethodik fur¤ Eden.Abstract
Parallelism has always been a hidden main source of processor power. As a result
of the limited amount of implicitly exploitable small-scale parallelism (for example
on the instruction-level) and ever-growing needs for more computational power,
parallel techniques break their way from a minor matter to a major feature in
both hardware and software. Due to their complexity, such parallel systems are
getting increasingly dif cult to control with conventional programming languages.
Therefore, more abstract high-level approaches move into focus. Eden is a repre-
sentative of these approaches which integrates constructs for remote evaluation
into the standard functional language Haskell. It strikes a balance between full
and no parallelism control and delivers good speedups while providing a high-level
style of programming.
In this thesis we equip Eden with three language features to raise the abstrac-
tion level even more:
Meta-programming, which means that programs manipulate other programs,
will be used to de ne static preprocessing steps coded in Haskell for enhanc-
ing Eden programs. This supports portability of the Eden compiler, as some
transformations can be pulled out of the foreign Haskell implementation.
Generic programming raises parametric to structural polymorphism and al-
lows to write functions which are valid for all data structures. We will present
a reduced, structure-oriented approach to generic programming tailored for
Eden’s needs. Using this approach, very general parallel schemes are de ned.
Demand control is a basic requirement if a lazy functional language is faced
with parallelism. The contradictory aims of postponing evaluations and si-
multaneity of evaluations enforces demand control in favour of parallelism.
We present a set of means to do that.
In functional programs, evaluation progress is determined by a mix of control
structures and data dependencies. Accordingly, parallel functional programs can
roughly be classi ed into data-oriented and control-oriented ones. Firstly, we will
present generic methods for partitioning data structures as well as generic versions
of the parallel map function. Secondly, we will show methods to manage the om-
nipresent streams as well as parallel schemes for dealing with irregular task sizes
and long communication distances. To conclude, we will summarise all methods
shown in a program developing guide for Eden.Acknowledgements
My thanks are threefold:
Firstly, I want to most heartily thank my supervisor Rita Loogen. Not
only for introducing me into the exciting topics of functional languages
and parallel computers, but also for giving me the possibility to write
this thesis about the topics I am most interested in and for providing
a very stimulating working atmosphere. Thanks also go to the many
present and past members of the Eden group in Marburg and Madrid
for many valuable discussions. I am grateful to Ralf Hinze for agreeing
to serve on the examination board despite being loaded with teaching
duties and research activities. I am also thankful for the suggestions of
other conference participants and especially for the neutral assessments
and helpful comments of many anonymous referees.
Secondly, I am most thankful to the Evangelisches Studienwerk Vil-
ligst e.V. (which is the scholarship organisation of the german protes-
tant church) for granting me a scholarship when I needed it the most.
Not only their generous nancial support is acknowledged, but at least
as much the inspiring, interdisciplinary meetings at Villigst and in the
local group of scholarship holders at Marburg.
Thirdly, the warmest thanks go to my family for their constant and lov-
ing support in all situations. Above all, my loving thanks go to my wife
Friederike and our daughter Luisa for bearing with me through all ups
and downs of my work.Contents
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Why Parallel Computing Is on the Rise Again . . . . . . . . . 1
1.1.2 Why More Abstract Programming Languages Are Needed . . 2
1.1.3 Why Functional May Be the Solution 3
1.1.4 Why More Advanced Techniques Are Needed . 6
1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Structure of this Dissertation . . . . . . . . . . . . . . . . . . . . . . . 8
2 Fundamentals 9
2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Parallel Computers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Approaches to Parallel Programming . . . . . . . . . . . . . . . . . . . 13
2.4hes to P Functional Programming . . . . . . . . . . . . 15
2.5 The Parallel Functional Language Eden . . . . . . . . . . . . . . . . . 16
2.5.1 Process Creation and Placement . . . . . . . . . . . . . . . . . 17
2.5.2 Communication and Storage . . . . . . . . . . . . . . . . . . . . 18
2.5.3 Evaluation Behaviour and Laziness . . . . . . . . . . . . . . . 20
3 Meta-Programming for Eden 21
3.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 with Template Haskell . . . . . . . . . . . . . . . 23
3.3 Preprocessing Eden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.1 The Preprocessor . . . . . . . . . . . . . . . . . . . . . . . . . .