Ähnlich wie zu meinem Artikel über das Modul Effiziente Graphenalgorithmen möchte ich auch zum Modul Advanced Parallel Computing eine Themenübersicht vorstellen. Dieses Modul weist die Besonderheit auf, dass es zwischen didaktischen Methoden wechselt. Viele Teile basieren auf Papern und Artikeln, manche Kapitel werden vom Dozenten mit Folienpräsentation vorgestellt. Manche der vorgestellten Paper sind von Professoren der Fernuni selbst, andere sind von Autoren anderer Universitäten.

Die folgende Aufstellung erhebt keinerlei Anspruch auf Vollständigkeit, sie soll (vor allem mir) nur einen ganz groben Überblick über die Lerninhalte geben.

Schauen wir uns zunächst einmal an, welche Papers bzw. Lehrmaterialien verwendet werden, bevor wir in die Details der Themen gehen:

  • Yu-Kwong Kwok, Ishfaq Ahmad: Static scheduling algorithms for allocating directed task graphs to multiprocessors (1999)
  • Anthony Sulistio, Udo Hoenig, Christoph Reich, Wolfram Schiffmann: Adaptive workflow scheduler with advance reservation in economic grid systems (2011)
  • Jörg Keller, Wolfram Schiffmann: Guiding performance tuning for grid schedules (2009)
  • Jörg Keller, N.-K. Nguyen, Wolfram Schiffmann: Evaluation and refinement of a tuning tool for grid applications (2010)
  • Videopräsentation zu Optimierungsproblemen
  • Christian Blum, Andrea Roli: Metaheuristics in combinatorial optimization (2003)
  • T.G. Crainic, M. Toulouse: Parallel Strategies for Meta-Heuristics (2003)
  • Videopräsentation zu Architektur von GPUs
  • Videopräsentation zu CUDA
  • Videopräsentation zu OpenCL
  • Videopräsentation zu Parallelem Sortieren
  • Thomas Bräunl: Tutorial in data parallel image processing (2001)
  • Wolfram Schiffmann: Efficient parallel implementation of growing neural gas networks on message passing architectures (2011)

Grob gesehen kann man die Vorlesung in folgende Themenblöcke einteilen, wobei jeder Themenblock mehrere Wochen umfasst:

  • Scheduling von Tasks (mit Abhängigkeiten zueinander)
  • Metaheuristiken für Optimierungsprobleme
  • Parallelisierung durch GPU
  • Parallelisierung spezieller Algorithmen: Sortieren, Bildverarbeitung, Neuronale Netze

Scheduling von Tasks

Beim Scheduling von Tasks muss man zwischen dem statischen und dem dynamischen Scheduling unterscheiden. Schauen wir uns zunächst das statische Scheduling an:

  • Unterschied zwischen Task Interaction Graph und Task Precedence Graph
  • Modellierung des Problems als gerichteter azyklischer Graph (DAG):
    • kritischer Pfad
    • static level
    • t-level
    • b-level
    • ASAP / ALAP
  • Task-Scheduling im Allgemeinen ist NP-vollständig; welche Vereinfachungen gibt es und welche Laufzeiten ergeben sich daraus?
  • Taxonomie der Graph-Scheduling-Algorithmen:
    • beliebige Struktur oder eingeschränkte Struktur, z.B. Baum
    • Rechenkosten: Beliebige Kosten oder Einheitskosten?
    • mit oder ohne Kommunikationkosten?
    • Duplizierung von Tasks auf mehrere Prozessoren (TDB)? (zur Reduzierung von Kommunikationskosten)
    • Limitierte oder unlimitierte Anzahl von Prozessoren (UNC)?
    • Fully-connected Mesh zwischen Prozessoren (BNP) oder eingeschränkte Kommunikationswege (APN)?

Anschließend werden zu den verschiedenen Varianten von Task-Graphen jeweils Algorithmen vorgestellt:

  • Eingschränkte Task-Strukturen
    • Hu’s Algorithmus für Baumstrukturen
    • Coffman/Graham-Algorithmus für Scheduling auf zwei Prozessoren
    • Scheduling von Intervall-geordneten DAGs
  • Beliebige DAGs ohne Kommunikationskosten
  • Scheduling mit unlimitierter Prozessorzahl (UNC)
    • Edge Zeroing
    • Linear Clustering
    • Dominant Sequence Clustering
    • Mobility Directed
    • Dynamic Critical Path
  • Scheduling mit limitierter Prozessorzahl (BNP)
    • Highest Level First with Estimated Times
    • Insertion Scheduling Heuristic
    • Modified Critical Path
    • Earliest Time First
    • Dynamic Level Scheduling
    • Localized Allocation of Static Tasks
  • Scheduling mit Duplizierung von Tasks (TDB)
    • PY-Algorithmus (Papadimitriou-Yannakakis)
    • Lower Bound (LWB)
    • Duplication Scheduling Heuristic
    • Bottom-up Top-down Duplication Heuristic
    • Linear Clustering with Task Duplication
    • Critical Path Fast Duplication
  • beliebig eingeschränkte Kommunikationswege zwischen den Prozessoren (APN)
    • Mapping Heuristic
    • Dynamic Level Scheduling
    • Bottom Up
    • Bubble Scheduling and Allocation

Außerdem werden im Paper verschiedene Scheduling-Implementierungen vorgestellt. Dieser Abschnitt ist aufgrund des hohen Alters des Papers jedoch heutzutage eher uninteressant, da die genannten Programme alle aus den 90ern stammen und meiner Recherche nach nicht mehr aktiv scheinen. Zumindest habe ich nur verwaiste Institutsseiten oder die wissenschaftlichen Papers zu den Programmen gefunden.

Zuletzt gibt es im Paper einen Verweis auf weitere Möglichkeiten zum Scheduling:

  • Genetische Algorithmen
  • Randomisierte Algorithmen
  • Parallelisierung der Scheduling-Algorithmen

Zum Themenblock dynamisches Scheduling (also Scheduling von nach und nach ankommenden Tasks) wird ein Paper verwendet, das einen Vorschlag für einen Resource Broker in einem Zusammenschluss mehrerer Rechen-Cluster präsentiert. Es handelt sich also nicht um ein Scheduling in einem eigenen selbst verwalteten Rechenzentrum, sondern mehrere Rechenzentren haben sich zu einem Rechencluster zusammengeschlossen und bieten ihre Rechenleistung zu verschiedenen Preisen an. Der Resource Broker hat die Aufgabe, die Tasks an die Rechenzentren zuzuweisen.

Im Paper werden dazu grob folgende Themen angesprochen:

  • Modellierung: zentraler Broker, lokale Scheduler bei den Resource Providern
  • Optimierungsziele der Nutzer können verschieden sein: z.B. Zeit, Kosten
  • Architektur des Brokers:
    • Handling von Workflows (Abhängigkeiten)
    • Scheduling unabhängiger Tasks
  • Kommunikation des Predictors mit den Resource Providern
  • Evaluation mithilfe einer Test Bench

Zuletzt befasst der Kurs sich mit dem Verbessern von Schedules. Die vorgestellten Papers wählen dabei den Weg, dass ein Programmierer den langsamen Programmcode optimieren soll. Dazu soll ihm vom Algorithmus die Codestelle (in Form des betroffenen Tasks) vorgeschlagen werden, die er sich anschauen muss, damit es überhaupt einen Einfluss auf die Laufzeit des Algorithmus geben kann.

  • relevanter Task muss auf dem Critical Path liegen
  • Optimierung eines Tasks oder mehrerer Tasks
  • Möglichkeit, Beschleunigungslimits anzugeben (eine Verbesserung um 90% ist in der Regel unrealistisch)

Metaheuristiken für Optimierungsprobleme

Dieser Abschnitt startet mit einem Exkurs in die Optimierung:

  • Formalisierung von Optimierungsproblemen über gültige Lösungen und Kostenfunktion (vgl. auch Effiziente Graphenalgorithmen mit feasible solutions)
  • Formulierung von Statischem Scheduling als Optimierungsproblem
  • Approximationsalgorithmen und Approximationsgüte
  • Online-Algorithmen und Kompetitivität
  • Beispiel für einen Online-Job-Scheduling-Algorithmus mit bekannter Kompetitivität

Anschließend wird eine Arbeit vorgestellt, die einen Überblick über verschiedene Metaheuristiken zur kombinatorischen Optimierung gibt. Metaheuristiken sind Algorithmen zur näherungsweisen Lösung eines Optimierungsproblems, die auf beliebige Optimierungsprobleme angewendet werden können (im Gegensatz zu spezialisierten Algorithmen, die bspw. nur Travelling Salesman lösen).

  • Approximationsmethoden:
    • lokale Suche
    • konstruktive Methoden
  • Klassifizierungen:
    • nature-inspired vs non-nature-inspired
    • population-based vs. single point search (=trajectory methods)
    • dynamische vs. statische Zielfunktion
    • eine oder mehrere Nachbarschaftsstrukturen
    • memory vs. memoryless
  • Trajectory Methods:
    • Iterative Improvement
    • Simulated Annealing
    • Tabu Search
    • Greedy Randomized Adaptive Search Procdecure (GRASP)
    • Variable Neighbourhood Search
    • Guided Local Search
    • Iterated Local Search
  • Population-based:
    • Evolutionary, zum Beispiel Genetische Algorithmen
    • Scatter Search / Path Relinking
    • EDA
    • Ant Colony Optimization

Im weiteren Verlauf wird dann eine Arbeit präsentiert, die die Möglichkeiten zur Parallelisierung der wichtigsten Metaheuristiken vorstellt:

  • übliche Elemente von Metaheuristiken:
    • Initialisierung
    • Nachbarschaften
    • Kriterium zur Nachbarschaftsselektion
    • Kandidatenselektion
    • Akzeptanzkriterium
    • Stopkriterium
  • Data parallelism vs functional parallelism
  • Möglichkeiten zur Parallelisierung:
    • Typ 1: Parallele Ausführung mehrerer Moves/Fitness-Evaluierungen (gleiche Ausführung wie sequentiell)
    • Typ 2: Partitionierung der Entscheidungsvariablen (andere Ausführung als sequentiell)
    • Typ 3: mehrere gleichzeitige Suchen im Lösungsraum (kooperativ oder unabhängig)
  • Parallelisierung verschiedener Metaheuristiken:
    • Genetische Algorithmen
    • Simulated Annealing
    • Tabu Search

Parallelisierung durch GPU

  • Multicore vs Manycore
  • Manycore-Beispiele:
    • Tilera Tile64
    • TRIPS
    • Intel Polaris
    • Intel SCC
    • Intel Larrabee
    • Intel Knights Ferry
    • Intel Xeon Phi
  • Ausführung auf GPU zuerst über Shader-Sprachen, später CUDA, OpenCL, DirectCompute, OpenACC
  • Beispiele für GPU-Architekturen:
    • GeForce 8
    • Fermi
    • Tesla
    • Kepler
    • Radeon HD7000
  • CUDA
    • Begriffe: Device, Kernel, Host, Grid, Block, Warps
    • Speichermodell
    • Synchronisierung
    • CUDA Streams
  • OpenCL
    • Begriffe: Host, Compute Device, Compute Unit, Processing Element, Kernel
    • OpenCL-C-Kernel vs nativer Kernel
    • Command Queues: in-order vs out-of-order
    • Speicherobjekte: Buffer und Image
    • Speichermodell
    • Synchronisierung

Parallelisierung spezieller Algorithmen

Zur Parallelisierung spezieller Algorithmen wird zunächst auf das Sortieren eingegangen. Hierzu werden mehrere Parallelisierungsmöglichkeiten für verschiedene Sortieralgorithmen vorgestellt:

  • Quick-Sort
    • simpler Ansatz
    • Parallelisierung der Partitionierung mit p-1 Pivots
    • Tsigas’ Algorithmus: Parallelisierung der Partitionsschleife
  • Bitonic Sort
    • Definition bitonischer Zahlenfolge
    • keine sequentielle Variante dieses Algorithmus
  • Merge-Sort
    • simpler Ansatz
    • Parallelisierung der Merge-Routingen (Achtung: Balance)

In der nächsten Arbeit wird die Parallelisierung von Bildverarbeitung thematisiert. Auch hier werden wieder Möglichkeiten zur Parallelisierung von bekannten Operationen der Bildverarbeitung behandelt. Die Algorithmen bauen darauf auf, dass jedes Bildpixel von einer anderen Recheneinheit bearbeitet wird und Informationen über Nachbarpixel daher zwischen den Recheneinheiten ausgetauscht werden müssen.

  • Point und Local Operators
    • Average / Median / Fast-Median
    • Dithering
    • Edge Detection: Sobel-Filter braucht nicht 6-mal Datenaustausch, sondern bei geschickter Implementierung nur 4
  • Morphological Operators
    • Erosion / Dilation
    • Open / Close
    • Fill / Connected
    • Boundary / Skeleton
  • Region-based Operators
    • Segmentation

Im letzten Abschnitt wird auf die Parallelisierung von Neuronalen Netzen eingegangen anhand des Growing-Neural-Gas-Netzwerks. Um dieses Paper zu verstehen, muss man sich vermutlich zunächst in Growing Neural Gas (1, 2) und Self Organizing Maps einarbeiten, da diese auf den ersten Blick sehr wenig mit den neuronalen Netzen aus Multilayer Perceptrons gemeinsam zu haben scheinen. Ein weiteres Thema, in das man sich zum Verständnis der Anwendung von Neural Gas Networks einlesen sollte, ist die Vector Quantization. Das Paper stellt auf diesen Grundlagen basierend dann zwei Varianten zur Parallelisierung von GNG vor:

  • Dynamic Partitioning
  • Advance Partitioning
I do not maintain a comments section. If you have any questions or comments regarding my posts, please do not hesitate to send me an e-mail to blog@stefan-koch.name.