KIT-Bibliothek
Audio-/Videodatei publizieren
Anleitung zum Publizieren

Parallele Algorithmen, Vorlesung, WS 2017/18

Parallele Algorithmen, Vorlesung, WS 2017/18

Autor

Peter Sanders

Herausgeber

KIT | Webcast

Beteiligtes Institut

Genre

Vorlesung

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

Lernziele:
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.

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

Voraussetzungen:
Empfehlungen:

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

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz

Hinweis

Die Beiträge dieser Serie können Sie als Podcast abonnieren.

Embed-Code