Parallele Algorithmen

Type: Vorlesung (V)
Semester: WS 17/18
Time: 16.10.2017
15:45 - 17:15 wöchentlich
50.34 Raum -101 50.34 INFORMATIK, Kollegiengebäude am Fasanengarten
weitere...

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
Lecturer: Prof. Dr. Peter Sanders
SWS: 2/1
Lv-No.: 2400053

Links

Links_bearbeiten

Voraussetzungen	Empfehlungen: Kenntnisse aus der Vorlesungen wie Algorithmen I/II werden empfohlen.
Beschreibung	Diese 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, ...?
Lehrinhalt	Modelle 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
Arbeitsbelastung	Vorlesung 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
Ziel	Die 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üfung	Die 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.

Prüfung

Sie müssen sich vor der Prüfung am Studierendenportal für diese Veranstaltung anmelden; falls zwei Einträge "Parallele Algorithmen" bei Ihnen vorhanden sind, wählen Sie bitte die Nummer 13331. Termine für die mündliche Prüfung vereinbaren Sie bitte mit Herrn Prof. Sanders direkt per E-Mail, mit CC an blancani ∂does-not-exist.kit edu.

Informationen/Voraussetzungen

Voraussetzungen	Empfehlungen: Kenntnisse aus der Vorlesungen wie Algorithmen I/II werden empfohlen.
Beschreibung	Diese 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, ...?
Lehrinhalt	Modelle 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
Arbeitsbelastung	Vorlesung 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
Ziel	Die 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üfung	Die 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.