Structured Parallelism by Composition - Design and implementation of a framework supporting skeleton compositionality

Autor: Dieterle, Mischa, Loogen, Rita (Prof. Dr.)
Jazyk: němčina
Rok vydání: 2015
Předmět:
Popis: Diese Arbeit widmet sich der effizienten Komponierbarkeit von algorithmischen Skeletten, einer Abstraktion von gängigen parallelen Programmierschemen, die sich in der funktionalen parallelen Programmiersprache Eden in einfacher Weise als Funktionen höherer Ordnung darstellen lassen. Durch algorithmische Skelette lässt sich paralleles Programmieren extrem erleichtern, da sie die kniffligen Details paralleler Abläufe bereits beinhalten und sich durch bloße Bereitstellung problemspezifischer Funktionen auf konkrete Anwendungen spezialisieren lassen. Dabei kommt der effizienten Komponierbarkeit von parallelen Skeletten eine besondere Bedeutung zu, da sich hierdurch komplexe, spezialisierte Skelette aus einfacheren Basisskeletten zusammensetzen lassen. Die so gewonnene Modularität ist gerade für funktionales Programmieren wichtig und sollte insbesondere in einer funktionalen parallelen Sprache nicht fehlen. Komposition wird hier in drei Kategorien unterteilt: -Verschachtelung: Ein Skelett wird aus einem anderen Skelett heraus instanziiert. Kommunikation findet baumartig entlang der Aufrufhierarchie statt. Dies wird in Eden direkt unterstützt. -Verkettung oder Hintereinanderausführung: Das Ergebnis einer Skelettberechnung wird zur Eingabe eines Folgeskeletts. Komposition von Funktionen wird in Haskell mit dem Kompositionsoperator ( . ) ausgedrückt. Aus Performanzgründen sollen die Prozesse beider Skelette Ergebnisse direkt austauschen können, ohne diese über den Aufrufprozess schicken zu müssen. Hierfür wird das Remote-Data-Konzept eingeführt. -Iteration: Ein Skelett wird variabel oft hintereinander ausgeführt. Dies kann durch Rekursion und Hintereinanderausführung definiert werden. Optimiert werden die Anzahl der Skelett-Instanzen, die Kommunikation zwischen den Iterationsschritten und die Kontrolle der Schleifendurchläufe. Dazu dient ein eigens entwickeltes Iterationsframework, in dem Iterationsskelette aus Kontroll- und Rumpfskeletten zusammengefügt werden. In dieser Arbeit haben wir neue Konzepte zur verteilten Skelettkomposition erforscht. Wir wollten weder von einer speziellen Kompilerunterstützung zur Realisierung der Komposition abhängig sein, noch wollten wir einfach einen Satz aus vordefinierten verteilten Datenstrukturen bereitstellen, die nach ihrer Implementierung eine feste API mit einer begrenzten Anzahl an unterstützten Datenstrukturen haben. Dennoch sollte eine performante Implementierung der Skelettkomposition auf Basis unserer Konzepte umgesetzt werden. Die Konzepte sollten sich reibungslos in den Kontext funktionaler Programmierung einbetten lassen, also Merkmale funktionaler Sprachen wie Funktionen als Werte, Rekursion und nicht strikte Datenstrukturen unterstützen. Anders ausgedrückt behandeln wir die Frage: Was sind konzeptionelle Bausteine, die performante Skelettkomposition erlauben, einfach zu benutzen sind und hohe Flexibilität in Bezug auf Konnektivität, Erweiterbarkeit und Transformierbarkeit gewährleisten? Eine Schlüsselrolle bei unserem Kompositionskonzept kommt Remote Data zu. An Stelle der eigentlichen Daten kann ein Remote-Data-Handle verschickt werden, das an seinem Zielort benutzt wird, um die referenzierten Daten anzufordern. Remote Data kann in beliebigen Containertypen ähnlich wie verteilte Datenstrukturen zur effizienten Skelettkomposition benutzt werden. Die freie Zusammensetzung von Remote Data mit beliebigen Containertypen sorgt dabei für einen sehr hohen Grad an Flexibilität. Der Programmierer ist nicht auf vordefinierte verteilte Schnittstellen oder (Um-)Verteilungsfunktionen festgelegt und kann damit auch in eleganter Weise Prozesstopologien erzeugen. Für den Spezialfall der Iteration algorithmischer Skelette versuchen wir den sukzessiven Auf- und Abbau eines Skeletts in jedem Iterationsschritt zu verhindern, der bei der rekursiven Benutzung von Skeletten üblich ist. Dies minimiert den parallelen Overhead für Prozess- und Kanalerzeugung und ermöglicht es Daten lokal auf persistenten Prozessen zu belassen. Dazu stellen wir ein Iterations Framework bereit. Dieses Konzept ist unabhängig von der Benutzung von Remote Data, lässt sich aber durch die Benutzung von Remote Data flexibel erweitern. Beide oben genannte Ansätze zeigen für unsere Fallbeispiele vergleichbare Laufzeiten zu Programmen mit identischem parallelem Aufbau, bei denen das zugrunde liegende Skelett aber nicht aus einfacheren Basisskeletten komponiert, sondern als monolithisches Skelett implementiert wurde. Des weiteren präsentieren wir Erweiterungen der Programmiersprache Eden, mit denen wir Komposition besser unterstützen können: Verallgemeinerung der überladenen Kommunikation, verallgemeinerte Prozessinstanziierung, kompositionelle Prozessplatzierung und Erweiterung von Box-Typen zum Anpassen von Kommunikationsverhalten.
Databáze: OpenAIRE
Externí odkaz: