Search

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., 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.

Como objetivo inicial de esta tesina se encuentra la investigación de modelos de sincronización para aplicaciones paralelas de alta complejidad computacional sobre cluster de multicores, teniendo en cuenta el auge de esta arquitectura. Como caso de prueba se utiliza el algoritmo de Smith-Waterman para determinar el grado de similitud de dos secuencias de ADN, cuya paralelización emplea un esquema de pipeline debido a la dependencia de datos inherente al problema. Resulta de interés comparar diferentes técnicas de descomposición paralela y mapeo de tareas concurrentes a procesadores para la aplicación mencionada anteriormente. También interesa analizar alternativas de los algoritmos paralelos conocidos para el alineamiento de secuencias, considerando la arquitectura multiprocesador de soporte. Finalmente, estudiar métricas de perfomance para los estudios experimentales que se realicen de manera de obtener una comparación real de la solución a esta clase de problemas, empleando sincronización por mensajes, por memoria compartida e híbrida., Facultad de Informática