Modul

Siehe Teilleistung.

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 kann er/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 Datenstruktuen 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;
• Machinenmodelle 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; auf Basis der in der Vorlesung erlernten Konzepte und Techniken eigene Lösungen in diesem Modell entwerfen, analysieren und die algorithmischen Eigenschaften beweisen.

Siehe Teilleistung.

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

Siehe Teilleistung

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