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.