Structured Generic Programming in Eden

Die Ausnutzung von Parallelität ist schon immer eine für den Benutzer unsichtbare, aber große Quelle zur Verbesserung der Prozessorleistung gewesen. Da aber die Menge an implizit nutzbarer Parallelität auf Befehlsebene begrenzt ist und gleichzeitig immer größere Rechenleistungen benötigt werden, erleben wir gegenwärtig eine Renaissance expliziter paralleler Techniken sowohl auf Hardware- als auch auf Softwareebene. Aufgrund ihrer Komplexität sind parallele Systeme mit traditionellen Programmiersprachen schwer zu handhaben. Deshalb werden zunehmend abstraktere Programmiersprachen betrachtet. Eden ist eine solche Sprache, die Programmkonstrukte zur gleichzeitigen Auswertung von Ausdrücken in die funktionale Programmiersprache Haskell integriert. Eden ist ein Kompromiss zwischen vollständiger und fehlender Parallelitätskontrolle durch den Programmierer: Es wird genügend Kontrolle zur Erreichung guter Beschleunigungen bereitgestellt, gleichzeitig wird aber auch ein abstrakter Programmierstil durch die Übernahme weniger wichtiger Vorgänge durch das Laufzeitsystem gewahrt. In dieser Arbeit stellen wir Eden drei Sprachkonzepte zur Seite, um eine noch weitergehende Abstraktion zu erreichen: 1) Unter Meta-Programmierung versteht man die Definition von Programmen, die andere Programme erzeugen oder verändern. Diese Technik wird benutzt, um in Haskell programmierte statische Präprozessorphasen zur Verbesserung von Eden-Programmen zu konstruieren. Dadurch wird die Portabilität des Eden-Compilers verbessert, da diese Phasen nun nicht mehr in den zugrundeliegenden Haskell-Compiler integriert werden müssen. 2) Generische Programmierung erweitert parametrische zur strukturellen Polymorphie und ermöglicht daher die Definition von Funktionen, die mit beliebigen Argumentdatenstrukturen arbeiten. Wir beschreiben einen reduzierten strukturorientierten Ansatz zur generischen Programmierung, der für den Einsatz in Eden konzipiert wurde. Mit diesem Ansatz definieren wir allgemeine parallele Verarbeitungsschemata. 3) Möglichkeiten zur Auswertungskontrolle müssen vorhanden sein, wenn in einer funktionalen Sprache Bedarfssteuerung auf Parallelität trifft. Deren Ziele sind gegensätzlich: Auf der einen Seite werden Auswertungen zeitlich nach hinten geschoben, während auf der anderen Seite frühe Auswertung die Gleichzeitigkeit und damit die Parallelität fördert. Wir zeigen Wege auf, um die Auswertung zu Gunsten der Parallelität zu steuern. In funktionalen Sprachen wird der Auswertungsverlauf durch Datenabhängigkeiten sowie durch Kontrollkonstrukte bestimmt. Analog kann man bei parallelen funktionalen Programmen zwischen datenorientierten und kontrollorientierten unterscheiden. Entsprechend zeigen wir zunächst generische Methoden zur Partitionierung von Datenstrukturen sowie generische Versionen der parallelen map-Funktion. Dann stellen wir kontrollparallele Methoden vor, mit denen die in Eden oft vorkommenden Datenströme behandelt werden können; zusätzlich zeigen wir parallele Schemata zur effizienten Verarbeitung irregulärer Strukturen und langer Kommunikationswege. Letztendlich vereinigen wir die gezeigten Techniken in einer Programmentwicklungsmethodik für Eden.
Parallelism has always been a main, yet hidden, 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 difficult to control with conventional programming languages. Therefore, more abstract high-level approaches move into focus. Eden is a representative 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 abstraction level even more: 1) Meta-programming, which means that programs manipulate other programs, will be used to define static preprocessing steps coded in Haskell for enhancing Eden programs. This supports portability of the Eden compiler, as some transformations can be pulled out of the foreign Haskell implementation. 2) Generic programming raises parametric to structural polymorphism and allows 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 defined. 3) Demand control is a basic requirement if a lazy functional language is faced with parallelism. The contradictory aims of postponing evaluations and simultaneity 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 classified 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 omnipresent 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.