Proseminar Parallele Algorithmik (WS2020/21)

Moderne CPUs haben immer mehr Prozessorkerne. Die Taktrate steigt hingegen kaum noch. Aus diesem Grund werden parallele Algorithmen immer wichtiger, da diese die vielen Kerne ausnutzen können. In diesem Proseminar beschäftigten wir uns mit Algorithmen in zwei parallelen Modellen: dem Shared-Memory- und dem Distributed-Memory-Modell. Der Große unterschied zwischen den beiden Modellen ist, dass zum einem (Shared-Memory) über einen gemeinsamen Speicher kommuniziert wird und zum anderen (Distributed-Memory) über ein Netzwerk kommuniziert wird. Für diese beiden Modelle werden wir im Proseminar parallele Algorithmen für fundamentale algorithmische Probleme wie Suchen, Sortieren und Hashing kennen lernen. Hierbei werden wir das Buch Sequential and Parallel Data Structures and Algorithms - The Basic Toolbox als primäre Literaturquelle verwenden. Diese und weitere Quellen werden im Moodle-Raum der Veranstaltung bereit gestellt.

Themenliste

Hier finden Sie eine gegliederte Liste der möglichen Proseminarthemen (beachten Sie, dass es sich bei den Themen immer um parallele Ansätze handelt, auch wenn es Abschnitte zu sequentiellen Varianten gibt).

Parallele Maschinenmodelle (McCool et al. Kap. 2.4-2.6 OHNE 2.5)
Performancemessung (Dietzfelbinger et al. Kap. 2.10 und McCool et al. Kap. 2.5)
Shared und Distributed Memory: (Cormen et al. Kap. 27.1 und Dietzfelbinger et al. Kap. 2.4.1-2.4.3 und 3.1)
Präfixsumme (Blelloch 1.1-1.2 und Dietzfelbinger et al. Kap. 13.2)
List-Ranking (Dietzfelbinger et al. Kap. 3.3)
Hashing (Dietzfelbinger et al. Kap. 4.6)
Selection (Dietzfelbinger et al. Kap. 5.8-5.9)
Queues und Prioritätswarteschlangen (Dietzfelbinger et al. Kap. 3.7 und 6.4)
Matrixmultiplikation (Cormen et al. Kap. 27.2)
Quicksort (Dietzfelbinger et al. Kap. 5.7)
Sample Sort (Dietzfelbinger et al. Kap. 5.13 und McCool et al. Kap. 14)
Merge Sort (Cormen et al. Kap. 27.3 und Dietzfelbinger et al. Kap. 5.14)
Breitensuche (Dietzfelbinger et al. Kap. 9.2)
DAG-Traversal (Dietzfelbinger et al. Kap. 9.4)
Kürzeste Wege (Dietzfelbinger et al. Kap. 10.9)
Minimale Spannbäume (Dietzfelbinger et al. Kap. 11.6)
Kommunikation 1 (Dietzfelbinger et al. Kap. 13.1, 13.2 und 13.4)
Kommunikation 2 (Dietzfelbinger et al. Kap. 13.4-13.7)
Lastbalancierung 1 (Dietzfelbinger et al. Kap. 14.1-14.3)
Lastbalancierung 2 (Dietzfelbinger et al. Kap. 14.4-14.6)

Organisatorisches

Allgemeine Hinweise

Die Modulbeschreibung für das Proseminar finden Sie hier. Dort finden sie Hinweise auf die Lerninhalte und den Aufwand des Moduls. Bitte beachten Sie, dass der Präsentationskurs teil dieser Veranstaltung ist. Eine Teilnahme ist für den Leistungsnachweis verpflichtend. Informationen zu dem Präsentationskurs (inklusive wichtiger Informationen zum Vortrag und zur Ausarbeitung) finden Sie hier.

Zeitplan

In diesem Proseminar gibt es wichtige Deadlines, welche im Folgenden beschrieben werden. Die Deadlines richten sich nach dem Anfang des Vortragblocks. Diese Deadlines sind strikt, bei Nichteinhalten einer Deadline oder dem unvorbereiteten Erscheinen zu einem der unten genannten Termine wird kein Leistungsnachweis ausgestellt.

Zwei Wochen vor dem Vortragsblock. Zwei Wochen vor dem Vortragsblock sollen Sie in einem halbstündigen Treffen die bis auf Feinkosmetik fertigen Folien bwz. vorbereiteten Tafelbilder zeigen und erklären können. Bitte vereinbaren Sie dieses treffen rechtzeitig, also mindestens vier Wochen vor dem Vortrag.

Zwei Wochen nach dem Vortragsblock. Zwei Wochen nach dem Vortrag müssen Sie die schriftliche Ausarbeitung abgeben. Die Abgabe erfolgt hier über Moodle. Ein entsprechender Bereich wird frühzeitig angelegt. Sie können Ihre Abgabe bis zur Deadline überarbeiten und nur die finale Version wird bewertet. Beachten Sie, dass die Abgabe automatisch um 23:59 Uhr endet. Nachträgliche Abgaben sind nicht möglich und werden nicht akzeptiert. Technische Probleme sind kein Grund für eine zu späte Abgabe.

Wichtiger Hinweis. Bitte beachten Sie, dass diese Deadlines für Sie bedeuten, dass Ihre Arbeit deutlich vor dem Vortragstermin beginnen muss. Aus der Erfahrung heraus sollten Sie spätestens acht Wochen vor Beginn des Vortragblocks mit der Arbeit beginnen.

Bei Fragen fragen!

Wenn Sie Fragen haben, die sich auch nach eigener Recherche nicht selbst klären lassen, zögern Sie bitte nicht nachzufragen. Bitte erwarten Sie an dieser Stelle jedoch nicht, dass Ihnen die Arbeit abgenommen wird sich in Ihr Thema einzuarbeiten und dies zu Verstehen. Denn hierbei handelt es sich um ein wichtiges Lernziel des Proseminars. Wenn Sie Detailfragen haben, so stellen Sie diese bitte zunächst per Mail, da solche Fragen oft nicht aus dem Stand heraus zu beantworten sind.