title: Strukturierte Parallelität durch Komposition - Design und Implementierung eines Frameworks zur Unterstützung von Skelettkomponierbarkeit
title: Structured Parallelism by Composition - Design and implementation of a framework supporting skeleton compositionality
title: Structured Parallelism by Composition - Design and implementation of a framework supporting skeleton compositionality
Creators: name: Dieterle, Mischa
Publisher: name: Philipps-Universität Marburg
Year: 2016
Subjects: HASKELL ,distributed memory
Skelettkomposition
functional programming
Lists, stacks, and queues (REVISED)
DATA STRUCTURES
Graphs and networks (REVISED)
Arrays
Records (NEW)
Distributed data structures (NEW)
Trees
Tables**
Funktionale Programmierung , Parallelverarbeitung
Concurrent programming structures
Coroutines
Classes and objects (NEW)
Language Constructs and Features (E.2)
Modules, packages
Frameworks (NEW)
Recursion
Polymorphism (NEW)
Data types and structures
Constraints (NEW)
Dynamic storage management
Procedures, functions, and subroutines
Input/output
Inheritance (NEW)
Abstract data types
Control structures
Patterns (NEW)
Applicative (Functional) Programming
Parallel programming
Distributed programming
Concurrent Programming
composition
iteration
Verteilter Speicher , Modularität
Algorithmische Skelette
Komposition
Iteration
modularity
parallel programming
Data processing, Computer science
Informatik
algorithmic skeletons
HASKELL

description: This thesis is dedicated to the
      efficient compositionality of algorithmic skeletons, which
      are abstractions of common parallel programming patterns.
      Skeletons can be implemented in the functional parallel
      language Eden as mere parallel higher order functions. The
      use of algorithmic skeletons facilitates parallel programming
      massively. This is because they already implement the tedious
      details of parallel programming and can be specialised for
      concrete applications by providing problem specific functions
      and parameters. Efficient skeleton compositionality is of
      particular importance because complex, specialised skeletons
      can be compound of simpler base skeletons. The resulting
      modularity is especially important for the context of
      functional programming and should not be missing in a
      functional language. We subdivide composition into three
      categories: -Nesting: A skeleton is instantiated from another
      skeleton instance. Communication is tree shaped, along the
      call hierarchy. This is directly supported by Eden.
      -Composition in sequence: The result of a skeleton is the
      input for a succeeding skeleton. Function composition is
      expressed in Eden by the ( . ) operator. For performance
      reasons the processes of both skeletons should be able to
      exchange results directly instead of using the indirection
      via the caller process. We therefore introduce the remote
      data concept. -Iteration: A skeleton is called in sequence a
      variable number of times. This can be defined using recursion
      and composition in sequence. We optimise the number of
      skeleton instances, the communication in between the
      iteration steps and the control of the loop. To this end, we
      developed an iteration framework where iteration skeletons
      are composed from control and body skeletons. Central to our
      composition concept is remote data. We send a remote data
      handle instead of ordinary data, the data handle is used at
      its destination to request the referenced data. Remote data
      can be used inside arbitrary container types for efficient
      skeleton composition similar to ordinary distributed data
      types. The free combinability of remote data with arbitrary
      container types leads to a high degree of flexibility. The
      programmer is not restricted by using a predefined set of
      distributed data types and (re-)distribution functions.
      Moreover, he can use remote data with arbitrary container
      types to elegantly create process topologies. For the special
      case of skeleton iteration we prevent the repeated
      construction and deconstruction of skeleton instances for
      each single iteration step, which is common for the recursive
      use of skeletons. This minimises the parallel overhead for
      process and channel creation and allows to keep data local on
      persistent processes. To this end we provide a skeleton
      framework. This concept is independent of remote data,
      however the use of remote data in combination with the
      iteration framework makes the framework more flexible. For
      our case studies, both approaches perform competitively
      compared to programs with identical parallel structure but
      which are implemented using monolithic skeletons - i.e.
      skeleton not composed from simpler ones. Further, we present
      extensions of Eden which enhance composition support:
      generalisation of overloaded communication, generalisation of
      process instantiation, compositional process placement and
      extensions of Box types used to adapt communication
      behaviour.
description: 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.