wissen.leben | WWU Münster 

Diplom- und Bachelorarbeitsthemen zur Parallelen Programmierung mit Algorithmischen Skeletten

  1. Parallelisierung des Cliquenproblems in Zusammenarbeit mit dem Lehrstuhl für Quantitative Methoden

    • Das Cliquenproblem ist ein np-vollständiges Entscheidungsproblem der Graphentheorie und beschäftigt sich mit der Suche nach so genannten Cliquen in einem Graphen G. Eine Clique ist formal definiert als Teilmenge der Knoten von G, innerhalb derer alle Knoten paarweise mit einer Kante verbunden sind. Bezogen auf beispielsweise soziale Netzwerke stellt eine Clique somit eine Art community dar, deren Identifizierung aus verschiedenen Gründen interessant sein kann, wie z.B. dem Anbieten von gezielter Werbung. Zur Lösung des Cliquenproblems existiert eine Vielzahl verschiedener sequenzieller Ansätze, auf Grund der Komplexitätsklasse des Problems bietet sich jedoch eine parallele Suche an.
    • Im Rahmen der Arbeit soll mindestens ein paralleler Algorithmus zur effizienten Lösung des Cliquenproblems implementiert und auf dem Parallelrechner des ZIV (ZIVHPC und/oder PALMA) getestet werden. Wahlweise können hierfür entweder task- und/oder datenparallele Skelette der Münster Skeleton Library Muesli oder eine Kombination aus Java/RMI oder C++/MPI verwendet werden. Im letzten Fall kann darüber hinaus optional OpenMP zum Einsatz kommen, um die Mehrkernprozessoren der Parallelrechner effizient zu nutzen.
    • Im Fall einer Masterarbeit ist die Arbeit in englischer Sprache zu verfassen.
    • Betreuer: Kuchen (Parallelisierung), Müller-Funk (Graphentheorie)

  2. Reeingineering der Münster Skeleton Library Muesli unter Nutzung kollektiver Kommunikationsoperationen

    • Algorithmische Skelette sind typische Muster zur parallelen Programmierung. Eine C++-Bibiothek solcher Skelette wurde am Institut für Wirtschaftsinformatik entwickelt. Diese Bibliothek soll im Rahmen einer Diplomarbeit von reiner Punkt-zu-Punkt-Kommunikation so umgebaut werden, dass die kollektiven Kommunikationsoperationen (wie z.B. Broadcasting) der Message-Passung-Biobliothek MPI in Zusammenhang mit Kommunikatoren (Prozessgruppen) benutzt werden und das Marshalling und Demarshalling von Objekten unterstützt wird.
    • Die Effizienz der modifizierten Bibliothek soll anhand von vorhandenen und ggf. zusätzlichen Beispielanwendungen mit der bisherigen Bibliothek verglichen werden.
    • Betreuer: Kuchen
    Literaturhinweis:

    • H. Kuchen: Optimizing Sequences of Skeleton Calls , Chapter of book Domain-Specific Program Generation (Eds. D. Batory, C. Consel, C. Lengauer, M. Odersky), LNCS 3016, 254-273, (C) Springer-Verlag, 2004.
    • H. Kuchen: A Skeleton Library , Proceedings of Euro-Par 2002, LNCS 2400, 620-629, (C) Springer-Verlag, 2002.
    • The Münster Skeleton Library Muesli

  3. Entwicklung von Benchmarks zur Münster Skeleton Library Muesli

    • Algorithmische Skelette sind typische Muster zur parallelen Programmierung. Eine C++-Bibiothek solcher Skelette wurde am Institut für Wirtschaftsinformatik entwickelt. Auf Basis dieser Bibliothek sollen im Rahmen einer Diplomarbeit Benchmarks entwickelt werden. Ein Beispiel hierfür ist ein paralleler Simplexsolver, der Ganzzahligkeitsbedingungen durch ein aufgesetztes Branch and Bound-Verfahren berücksichtigt. Knifflige Punkte sind hierbei die geeignete Kombination von daten- und taskparallelen Skeletten.
    • Die Effizienz der Bibliothek soll mit einer unmittelbar auf MPI basierenden Implementierung verglichen werden.
    • Betreuer: Kuchen
    Literaturhinweis:

    • H. Kuchen: Optimizing Sequences of Skeleton Calls , Chapter of book Domain-Specific Program Generation (Eds. D. Batory, C. Consel, C. Lengauer, M. Odersky), LNCS 3016, 254-273, (C) Springer-Verlag, 2004.
    • H. Kuchen: A Skeleton Library , Proceedings of Euro-Par 2002, LNCS 2400, 620-629, (C) Springer-Verlag, 2002.
    • The Münster Skeleton Library Muesli

  4. Erweiterung der Münster Skeleton Library Muesli um daten- und taskparallele Skelette

    • Algorithmische Skelette sind typische Muster zur parallelen Programmierung. Eine C++-Bibiothek solcher Skelette wurde am Institut für Wirtschaftsinformatik entwickelt. Diese Bibliothek soll im Rahmen einer Diplomarbeit angepasst oder um weitere daten- oder taskparallelen Skelette erweitert werden.

      • datenparallele Skelette: DH (distributable homomorphism), DS (double-scan), Varianten von map und fold , ...
      • taskparallele Skelette: Varianten von Divide-and-Conquer, Atomic, Tiefensuche, Breitensuche, Hill-Climbing, Simulated Annealing, Iterative Deepening, ...
    • Bei einer konkreten Umsetzung kommen i.d.R. unterschiedliche Varianten von Lastverteilungsverfahren, Kommunikationsmodi, interner Skelettarchitektur etc. in Frage, welche sich unmittelbar auf Skalierbarkeit, Engpasssituationen oder Performance auswirken. Die unterschiedlichen Skelettvarianten sollen anhand kleiner Performanztests vergleichend gegenübergestellt werden.
    • Betreuer: Kuchen
    Literaturhinweis:
    • H. Kuchen: Optimizing Sequences of Skeleton Calls , Chapter of book Domain-Specific Program Generation (Eds. D. Batory, C. Consel, C. Lengauer, M. Odersky), LNCS 3016, 254-273, (C) Springer-Verlag, 2004.
    • H. Kuchen: A Skeleton Library , Proceedings of Euro-Par 2002, LNCS 2400, 620-629, (C) Springer-Verlag, 2002.
    • The Münster Skeleton Library Muesli

  5. nach Absprache

    • weitere Themen können nach Absprache mit den Betreuern angeboten werden.

Formatvorlage

Für die Anfertigung von Seminar-, Bachelor- und Diplomarbeiten soll folgende Formatvorlage benutzt werden. Diese Vorlage beinhaltet nicht nur formatierungstechnische Feinheiten, sondern auch einige Hinweise zum logischen Aufbau der Arbeit, welche bei der Planung und Erstellung des Arbeitstextes beachtet werden sollten. Lesen Sie auch auf jeden Fall die Hinweise zum wissenschaftlichen Arbeiten.


Diese Seite:
Impressum | © Praktische Informatik