Wahlmöglichkeiten

Wir bieten folgende drei Wahlmöglichkeiten für die Zusatzaufgabe (1 ECTS) zur Vorlesung Parallele Algorithmen an:


Wikipedia-Artikel

Wir wollen den Themenbereich verteilte Algorithmen in Wikipedia deutlich verbessern. Als Zusatzaufgabe zur Vorlesung Parallele Algorithmen soll daher ein oder mehrere Wikipedia-Artikel neu geschrieben oder verbessert werden.

Es folgt unten eine Liste mit Themen aus der Vorlesung, zu denen jeweils die Wikipedia-Artikel zu wünschen übrig lassen. Diese sollen mit neuem Text, hinreichend vielen Referenzen, schönen (animierten) Illustrationen, Pseudocode, Analysen, und vielem mehr angereichert oder neu erstellt werden. Eine Aufgabe kann auch durch mehrere Personen bearbeitet werden, wovon eine/r den englischen Wikipedia-Artikel schreibt und die/der andere die deutsche Version. Die Liste der Aufgaben ist nicht vollständig und kann um sinnvolle Vorschläge ergänzt werden.

Teil der Aufgabe besteht auch darin den bearbeiteten Text zu "verteidigen", falls Wikipedia-Editoren den Inhalt anfechten. Sollte es zu unbegründeten Konflikten kommen, fließt dies jedoch natürlich nicht in die Bewertung ein.

Ein Beispiel für den vorgesehen Umfang eines guten Artikels ist https://de.wikipedia.org/w/index.php?title=Präfixsumme&oldid=165432173, mindestens jedoch 2000 Wörter. Zur Aufgabe gehört auch die Recherche von Sekundärquellen und weiteren Zitaten, da diese für einen enzyklopädischen Artikel unerlässlich sind. Die Wikipedia-Richtlinen (https://de.wikipedia.org/wiki/Wikipedia:Richtlinien) fordern explizit die Verwendung von Sekundärquellen, Primärquellen allein reichen nicht.

Die Artikel müssen bis 1.4.2018 fertig in der Wikipedia stehen und einen Monat (danach) "verteidigt" werden, also auf die Hinweise und Vorschläge der Editoren reagiert werden.


Matrixmultiplikation -- Betreuer: Lamm

Aufgabe 1: Trivial parallelization und Cannon's algorithm [1 Teilnehmer: Eng+Deu]

Aufgabe 2: Fox's algorithm und Dekel Nassimi Sahni [2 Teilnehmer: MK + ?]

Relevante Artikel

Anmerkungen: Englischer Artikel enthält bereits Informationen über verteilte Algorithmen

Quellen:


Kommunikationsprimitive -- Betreuer: Lamm

Hypercube

Aufgabe 1: Hypercube Grundalgorithmus [2 Teilnehmer]

Gut den Grundalgorithmus darstellen und dann die mit Applikationen: Präfixsumme, Broadcast, All-Reduce, All-to-All.

Relevante Artikel:

Quellen:

Reduce

Aufgabe 1: PRAM/DMM Binomial Tree und 3-2 Elimination [2 Teilnehmer]

Relevante Artikel:

Quellen:

Broadcast

Aufgabe 1: Binomial Tree, Linear Pipeline and Binary Tree [2 Teilnehmer]

Aufgabe 2: 2-3-Broadcast (and ESBT) [2 Teilnehmer: ? + AW]

Relevante Artikel:

EBST = Kurzer Abschnitt mit Link zu Hypercube Artikel

Quellen:

Präfix Summen

Aufgabe 1: Pipelined Binary Tree [1 Teilnehmer: Eng+Deu]

Relevante Artikel:

Anmerkungen: PRAM Algorithmus bereits auf Seite beschrieben

Quellen:

All-to-All

Aufgabe 1: 1-Factor + hierarchical [2 Teilnehmer]

Aufgabe 2: h-Relation + irregular messages [2 Teilnehmer]

Relevante Artikel:

Quellen:


Sortieren -- Betreuer: Bingmann

Aufgabe: Übersichtsartikel zu Sorting und String Sorting [2 Teilnehmer: SK + SV]

Quicksort

Aufgabe 1: Parallel Quicksort [2 Teilnehmer: reserviert FX + ?]

Relevante Artikel:

Anmerkungen: Englischer Artikel enthält bereits Informationen über verteilte Algorithmen

Quellen:

Samplesort

Aufgabe 1: Parallel Samplesort und Splitter Selection [2 Teilnehmer: CB + JD]

Relevante Artikel:

Anmerkungen: Englischer Artikel enthält bereits Informationen über verteilte Algorithmen

Quellen:

Mergesort

Aufgabe 1: Multiway Mergesort - Variants [2 Teilnehmer]

Aufgabe 2: Multiway Mergesort - Multisequence Selection after Varman et al. [2 Teilnehmer: JH (deu) + AG?]

Relevante Artikel:

Anmerkungen: Englischer Artikel enthält bereits Informationen über verteilte Algorithmen.

Quellen:


Priority Queues -- Betreuer: Lamm

Aufgabe 1: Parallel PQ [2 Teilnehmer: MN (deu) + ?]

(Aufgabe 2: Branch-and-bound and Parallel Select [1 Teilnehmer])

Relevante Artikel:

Quellen:


Graph Algorithmen

List Ranking -- Betreuer: Bingmann

Aufgabe 1: Pointer Chasing/Doubling und Ranking mit Independent Sets [2 Teilnehmer]

Anmerkungen: Englischer Artikel enthält bereits Informationen über Pointer Chasing/Doubling

Quellen:

Minimum Spanning Trees -- Betreuer: Lamm

Aufgabe 1: Parallel Boruvka [2 Teilnehmer: CÖ + SK]

Aufgabe 2: Parallel Prim/Kruskal + Filter Kruskal [2 Teilnehmer: KM + SG]

Relevante Artikel:

Anmerkungen: Es existiert bereits eine Seite über verteilte MSTs, allerdings ohne die Algorithmen aus der Vorlesung

Quellen:

BFS -- Betreuer: Lamm

Aufgabe 1: Parallel BFS und Graph 500 [2 Teilnehmer: JN + ?]

Relevante Artikel:

Quellen:

Shortest Paths -- Betreuer: Lamm

Aufgabe 1: Parallel All-pair Shortest Paths [2 Teilnehmer: JK + LR]

Relevante Artikel:

Quellen:


Load Balancing -- Betreuer: Lamm

Aufgabe 1: Master/Worker [2 Teilnehmer: Artikel sind stark verbesserungswürdig, aber könnte ein kontroverses Thema werden]

Aufgabe 2: Tree-shaped computations und (simplified/asynchronous) random polling [2 Teilnehmer]

Relevante Artikel:

Anmerkungen: Artikel enthalten bereits parallele Algorithmen und müssen ggf. ergänzt werden

Quellen:


Diverses

Mögliche Aufgaben:

Anmerkungen: Mögliche weitere Themen auf Nachfrage


Programmieraufgabe

Collectives in Thrill [reserviert: CM]


Miniseminar

Das Mini-Seminar wird ab Ende der Vorlesungszeit statt finden.

Zu jedem Thema sollen ein 20 minütiger Vortag gehalten werden mit anschließend 5 min Diskussion. Die Vorträge finden an ein oder zwei Blockterminen in den letzten zwei Wochen der Vorlesungszeit statt. Der Termin für die Vorträge ist der 5.2.18 um 15:45 in Raum -101.

Aufgaben: