Parallele Algorithmen: Materialien zur Vorlesung

  1. Vorlesungsfolien
  2. Gastvortrag Sorting
  3. Gastvortrag Collective Operations
  4. Gastvortrag Thrill
  5. Skript
  6. Seminarthemen
  7. Beispiel einer Praxisaufgabe
Uebung (Betreuung Michael Axtmann): Halten Sie einen 20min Minisemiarvortrag (Themen s.o.) oder programmieren Sie einen parallelen Sortieralgorithmus (bis zu 2 Persoenen). Waehlen Sie einen algorithmischen Ansatz (Quicksort, Samplesort, Mergesort, Multiway Mergesort, fast inefficient, BatcherSort, ColumnSort, ...) und ein Programmiermodell (OpenMP, Cilk, TBB, MPI, Cuda, OpenCL,...).

Miniseminar

Maximilian Czerny Designing Efficient Sorting Algorithms for Manycore (GPUs)
Tobias Ribizel Communication costs of Strassen's matrix multiplication
Fellipe Lima The Lock-free k-LSM Relaxed Priority Queue
Tobias Mueller A simple, fast parallel implementation of quicksort and its performance evaluation on SUN enterprise 10000

Die Präsentationen werden am Ende der letzten Vorlesung vorgetragen!

Programmieraufgabe

Die Algorithmen sollen beliebige Eingaben verarbeiten können. Dazu zählen Eingaben variabler Größe und Duplikate in der Eingabe. Eine Beispiel-Eingabe wäre (0, 0, 0, ...). Der Algorithmus muss mindestens Integer und Floats mit 32- und 64-bit Genauigkeit verarbeiten können. Die Ausarbeitung muss Benchmarks von zufälliger, gleichverteilter Eingabe, sowie der Eingabe (0, 0, ...), enthalten.
Heuer Tobias Shizophrenic Quicksort MPI
Manuel Leßmann, Patrick Bisenius Quicksort Cuda/OpenCL
Lars Gottesbueren, Sebastian Schmidt Samplesort MPI
Ulrich Berger Samplesort Cuda/OpenCL
Malte Schönbrunn Multiway Mergesort Cuda/OpenCL
Raphael Grimm Multiway Mergesort C++14
Oleksandr Khomenko, Mikhail Gavrish State of the Art Reduktion + Präfixsumme Cuda/OpenCL
Janis Estelmann Theo. CRCW S. 151 (beliebige n) OpenMP
Robin Hutmacher Bitonic Sort OpenMP
David Vogelbacher, Damir Ferizovic Samplesort TBB
Marco Neumann Samplesort Rust
Jonas Sauer, Patrick Schlosser Multiway Mergesort MPI
Jens Koenig Bitonic Sort Cuda/OpenCL
Anne Catherine Jäger, Alexandru Lesi Samplesort OpenMP
Hennadiy Yatskov, Nico Mürdter Radixsort Cuda/OpenCL
Matthias Stumpp Multiway Mergesort Cuda/OpenCL
Beskorovajnov Wasilij Radixsort MPI
Jonas Scholz, Moritz Baumann Multiway Mergesort Rust
Sebastian Gieße Radixsort C++11

Abgabefrist ist am 23.04.2016 (Vorlesungsbeginn ist am 24.04.2016)! Abgegeben wird die Implementierung sowie eine Ausarbeitung (siehe Beispiel einer Praxisaufgabe). Zusätzlich erklärt ihr eure Implementierung dem Betreuer.

Bevorzugte Themen und weitere Fragen mitte an Michael Axtmann per Mail senden.