Parallele Algorithmen

  • Typ: Vorlesung (V)
  • Semester: WS 17/18
  • Zeit: 16.10.2017
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten


    23.10.2017
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    30.10.2017
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    06.11.2017
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    13.11.2017
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    20.11.2017
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    27.11.2017
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    04.12.2017
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    11.12.2017
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    18.12.2017
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    08.01.2018
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    15.01.2018
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    22.01.2018
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    29.01.2018
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    05.02.2018
    15:45 - 17:15 wöchentlich
    50.34 Raum -101
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten
  • Dozent: Prof. Dr. Peter Sanders
  • SWS: 2/1
  • LVNr.: 2400053
VoraussetzungenEmpfehlungen:

Kenntnisse aus der Vorlesungen wie Algorithmen I/II werden empfohlen.

BeschreibungDiese Vorlesung erklärt grundlegende algorithmische Techniken zur Beherrschung paralleler Rechner:
  • einfache Programmiermodelle, die den Entwurf portabler und skalierbarer paralleler Algorithmen erlauben
  • grundlegende Kommunikationsmuster zwischen Prozessoren und ihre effektive Implementierung
  • Lastverteilung: Wie kann man komplizierte Berechnungen so verteilen, dass alle Prozessoren gleich viel zu tun haben?
  • Wie parallelisiert man grundlegende sequentielle Algorithmen: Sortieren, Datenstrukturen, Graphenalgorithmen, ...?
LehrinhaltModelle und ihr Bezug zu realen Maschinen:
  • shared memory - PRAM
  • Message Passing, BSP
  • Schaltkreise

Analyse: Speedup, Effizienz, Skalierbarkeit

Grundlegende Techniken:

  • SPMD
  • paralleles Teilen-und-Herrschen
  • kollektive Kommunikation
  • Lastverteilung

Konkrete Algorithmen (Beispiele)

  • Kollektive Kommunikation (auch für große Datenmengen): Broadcast, Reduce, Präfixsummen, all-to-all exchange
  • Matrizenrechnung
  • Sortieren
  • list ranking
  • minimale Spannbäume
  • Lastverteilung: Master Worker mit adaptiver Problemgröße, random polling, zufällige Verteilung
ArbeitsbelastungVorlesung und Übung mit 3 SWS, 5 LP entsprechen ca. 150 Arbeitsstunden, davon

ca. 30 Std. Besuch der Vorlesung und Übung bzw. Blockseminar
ca. 60 Std. Vor- und Nachbereitung
ca. 30 Std. Bearbeitung der Übungsblätter/Vorbereitung Minisemiar
ca. 30 Std. Prüfungsvorbereitung

ZielDie Studierenden erwerben ein systematisches Verständnis algorithmischer Fragestellungen und Lösungsansätze im Bereich der parallelen Algorithmen, das auf dem bestehenden Wissen im Themenbereich Algorithmik aufbaut. Außerdem können sie erlernte Techniken auf verwandte Fragestellungen anwenden und aktuelle Forschungstehmen im Bereich paralleler Algorithmen interpretieren und nachvollziehen.

Nach erfolgreicher Teilnahme an der Lehrveranstaltung können die Studierenden

  • Begriffe, Strukturen, grundlegende Problemdefinitionen und Algorithmen aus der Vorlesung erklären;
  • auswählen, welche Algorithmen und Datenstrukturen zur Lösung einer Fragestellung geeignet sind und diese ggf. den Anforderungen einer konkreten Problemstellung anpassen;
  • Algorithmen und Datenstrukturen ausführen, mathematisch präzise analysieren und die algorithmischen Eigenschaften beweisen;
  • Maschinenmodelle aus der Vorlesung erklären sowie Algorithmen und Datenstrukturen in diesen analysieren;
  • neue Probleme aus Anwendungen analysieren, auf den algorithmischen Kern reduzieren und daraus ein abstraktes Modell erstellen und auf Basis der in der Vorlesung erlernten Konzepte und Techniken eigene Lösungen in diesem Modell entwerfen, analysieren und die algorithmischen Eigenschaften beweisen.
PrüfungDie Erfolgskontrolle erfolgt in Form einer mündlichen Prüfung nach § 4 Abs. 2 Nr. 2 und einer Übung als Erfolgskontrolle anderer Art nach § 2 Abs. 2 Nr. 3.

Gewichtung: 80 % mündliche Prüfung, 20 % Übung.