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,...).
Maximilian Czerny |
Designing Efficient Sorting Algorithms for Manycore (GPUs) |
Tobias Ribizel |
Communication costs of Strassen's matrix multiplication |
|
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 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 |
Bevorzugte Themen und weitere Fragen mitte an Michael Axtmann per Mail senden.