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


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.