Aufgaben zu Parallele Algorithmen WS2018/2019

Aufgabe 1: Ein Übersichtsartikel mit einer ein-paragraphen Kurzbeschreibung von allen anderen Artikeln zu parallelem Sortieren erstellen. Eventuell eine Laufzeitübersicht, falls möglich (siehe sequentiellen Artikel).

Insbesondere: Einteilung der Algorithmenübersicht in Modelle auf denen parallele Sortierer arbeiten: PRAM, shared-memory Rechner, distributed Rechner, oder Concurrent Hardware (Sorting) Netzwerke.

Ziel des Artikels: zwei Teile

a) Maschinen Modelle für Sorting. "Wo kann man parallel Sortieren? -> welche Modelle?"

b) Liste von Grundalgorithmen, e.g. Mergesort (wie auf der Sorting Hauptseite), und dann wie sie in den Modellen eingesetzt werden. Jeweils ein Paragraph den Algorithmus + Liste wie Eingesetzt wird in verschiedenen Modellen.

Relevante Artikel:

• https://en.wikipedia.org/wiki/Sorting_algorithm
• https://de.wikipedia.org/wiki/Sortierverfahren

Quellen:

• Grama, A., 2003. Introduction to parallel computing. Kapitel 6.6 "Bibliographic Remarks" zu Sorting

Aufgabe 1: Parallel Quicksort

Relevante Artikel:

• https://en.wikipedia.org/wiki/Quicksort#Parallelization
• https://de.wikipedia.org/wiki/Quicksort

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

Quellen:

• Grama, A., 2003. Introduction to parallel computing. Kapitel 6.4
• JáJá, J., 1992. An introduction to parallel algorithms (Vol. 17). Kapitel 4.3
• Tsigas, P., and Yi Zhang. “A Simple, Fast Parallel Implementation of Quicksort and Its Performance Evaluation on SUN Enterprise 10000.” In Eleventh Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2003. Proceedings., 372–81, 2003. https://doi.org/10.1109/EMPDP.2003.1183613.
• Heidelberger, Philip, Alan Norton, and John T. Robinson. "Parallel quicksort using fetch-and-add." IEEE Transactions on Computers 39.1 (1990): 133-138.

Aufgabe 1: Multisequence Selection nach Varman et al. [1 Teilnehmer: HT + HL]

Aufgabe 2: K-way Tournament Tree für Multiway Merging [1 Teilnehmer: HT + HL]

Aufgabe 3: Practical Parallel Merge Sort - Parallel and Distributed Variants [2 Teilnehmer: frei] Vorlesungsstoff -> 4.1.7. MCSTL Multiway Mergesort im Skript

Relevante Artikel:

• https://en.wikipedia.org/wiki/Merge_algorithm
• https://en.wikipedia.org/wiki/K-Way_Merge_Algorithms
• https://en.wikipedia.org/wiki/Merge_sort#Parallel_merge_sort
• https://de.wikipedia.org/wiki/Mergesort
• https://en.wikipedia.org/wiki/K-way_merge_algorithm

Anmerkungen: Englischer Artikel enthält bereits Informationen über verteilte Algorithmen. Ein wichtige Teilaufgabe wäre auch den K-way Merge Tournament Tree Artikel zu verbessern!

Quellen:

• JáJá, J., 1992. An introduction to parallel algorithms (Vol. 17). Kapitel 4.3
• Blelloch, Guy E., et al. "A comparison of sorting algorithms for the connection machine CM-2." Proceedings of the third annual ACM symposium on Parallel algorithms and architectures. ACM, 1991.
• Varman, Peter J., et al. "Merging multiple lists on hierarchical-memory multiprocessors." Journal of Parallel and Distributed Computing 12.2 (1991): 171-177.
• https://github.com/tlx/tlx/blob/master/tlx/algorithm/multisequence_selection.hpp
• Timo's Doktorarbeit: https://arxiv.org/abs/1808.00963 (LCP Loser Tree, page 117)

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

• https://en.wikipedia.org/wiki/List_ranking
• https://en.wikipedia.org/wiki/Pointer_jumping

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

Quellen:

• Sibeyn, Jop F. "Better trade-offs for parallel list ranking." Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures. ACM, 1997.
• Sibeyn, Jop F., Frank Guillaume, and Tillmann Seidel. "Practical parallel list ranking." Journal of Parallel and Distributed Computing 56.2 (1999): 156-180.

Aufgabe 1: Parallel PQ [2 Teilnehmer]

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

Relevante Artikel:

• https://en.wikipedia.org/wiki/Branch_and_bound
• https://de.wikipedia.org/wiki/Branch-and-Bound
• https://en.wikipedia.org/wiki/Priority_queue
• https://en.wikipedia.org/wiki/Heap_(data_structure)
• https://de.wikipedia.org/wiki/Vorrangwarteschlange
• https://de.wikipedia.org/wiki/Heap_(Datenstruktur)

Quellen:

• Rihani, Hamza, Peter Sanders, and Roman Dementiev. "Multiqueues: Simpler, faster, and better relaxed concurrent priority queues." arXiv preprint arXiv:1411.1209 (2014).
• Sanders, P., 1995. Fast priority queues for parallel branch-and-bound.
• Rönngren, R. and Ayani, R., 1997. A comparative study of parallel and sequential priority queue algorithms.
• Brodal, G.S., Träff, J.L. and Zaroliagis, C.D., 1998. A parallel priority queue with constant time operations.
• Lindén, Jonatan, and Bengt Jonsson. “A Skiplist-Based Concurrent Priority Queue with Minimal Memory Contention.” In Principles of Distributed Systems, 206–20. Lecture Notes in Computer Science 8304. Springer International Publishing, 2013. http://link.springer.com/chapter/10.1007/978-3-319-03850-6_15.

Aufgabe: Einen neuen Artikel zu concurrent/parallel hash tables erstellen oder den bestehenden hash table Artikel ergänzen.

Relevante Artikel:

• https://en.wikipedia.org/wiki/Hash_table
• https://de.wikipedia.org/wiki/Hashtabelle

Quellen:

• Shun, Julian, and Guy E. Blelloch. "Phase-concurrent hash tables for determinism." Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures. ACM, 2014.
• Maier, Tobias, Peter Sanders, and Roman Dementiev. "Concurrent hash tables: Fast and general?(!)." ACM SIGPLAN Notices. Vol. 51. No. 8. ACM, 2016.
• Intel Thread Building Blocks Hash Tables: https://software.intel.com/en-us/node/506171

Aufgabe: Ein Artikel zu parallelen MST Algorithmen schreiben. Die Seiten zu Prim's und Kruskal's Algorithmen enthalten schon Information über deren Parallelisierbarkeit. In einem neuen Artikel kann auf diese verwiesen werden und um die besseren alternativen in den Quellen unten erweitert werden:

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

Relevante Artikel:

• https://en.wikipedia.org/wiki/Category:Spanning_tree
• https://en.wikipedia.org/wiki/Borůvka's_algorithm
• https://de.wikipedia.org/wiki/Algorithmus_von_Borůvka
• https://en.wikipedia.org/wiki/Prim's_algorithm
• https://de.wikipedia.org/wiki/Algorithmus_von_Prim
• https://en.wikipedia.org/wiki/Kruskal's_algorithm
• https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal
• https://en.wikipedia.org/wiki/Minimum_spanning_tree#Parallel_and_distributed_algorithms
• https://en.wikipedia.org/wiki/Distributed_minimum_spanning_tree
• https://de.wikipedia.org/wiki/Spannbaum

Quellen:

• Osipov, Vitaly, Peter Sanders, and Johannes Singler. "The filter-kruskal minimum spanning tree algorithm." Proceedings of the Meeting on Algorithm Engineering & Expermiments. Society for Industrial and Applied Mathematics, 2009.
• Wassenberg, Jan, Wolfgang Middelmann, and Peter Sanders. "An efficient parallel algorithm for graph-based image segmentation." International Conference on Computer Analysis of Images and Patterns. Springer, Berlin, Heidelberg, 2009.
• Grama, A., 2003. Introduction to parallel computing. Kapitel 7.2 + 7.3
• JáJá, J., 1992. An introduction to parallel algorithms (Vol. 17). Kapitel 5.2
• Dehne, F. and Gotz, S., 1998, October. Practical parallel algorithms for minimum spanning trees.

Aufgabe: Parallel BFS und Graph 500

Relevante Artikel:

• https://en.wikipedia.org/wiki/Graph500
• https://en.wikipedia.org/wiki/Breadth-first_search

Quellen:

• JáJá, J., 1992. An introduction to parallel algorithms (Vol. 17). Kapitel 5.1
• Buluç, A. and Madduri, K., 2011, November. Parallel breadth-first search on distributed memory systems.
• Leiserson, C.E. and Schardl, T.B., 2010, June. A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers).

Aufgabe: Ein neuen Artikel zum Parallel External Memory (PEM) model und die Übersichtsartikel zu anderen Modellen ergänzen.

Relevante Artikel:

• https://en.wikipedia.org/wiki/Parallel_programming_model
• https://en.wikipedia.org/wiki/Parallel_random-access_machine

Quellen:

• Arge, Lars, Michael T. Goodrich, Michael Nelson, and Nodari Sitchinava. “Fundamental Parallel Algorithms for Private-Cache Chip Multiprocessors.” In Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures, 197–206. SPAA ’08. New York, NY, USA: ACM, 2008. https://doi.org/10.1145/1378533.1378573.
• Arge, L., M. T. Goodrich, and N. Sitchinava. “Parallel External Memory Graph Algorithms.” In 2010 IEEE International Symposium on Parallel Distributed Processing (IPDPS), 1–11, 2010. https://doi.org/10.1109/IPDPS.2010.5470440.
• Ajwani, Deepak, Nodari Sitchinava, and Norbert Zeh. "Geometric algorithms for private-cache chip multiprocessors." European Symposium on Algorithms. Springer, Berlin, Heidelberg, 2010.
• Sitchinava, Nodari, and Norbert Zeh. "A parallel buffer tree." Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures. ACM, 2012.

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:

• https://en.wikipedia.org/wiki/Master/slave_(technology)
• https://de.wikipedia.org/wiki/Master/Slave
• https://en.wikipedia.org/wiki/Work_stealing
• https://de.wikipedia.org/wiki/Work_stealing

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

Quellen:

• Sanders, P., 1994. Massively Parallel Search for Transition-Tables of Polyautomata.
• Sanders, P., 1998. Tree shaped computations as a model for parallel applications.
• Sanders, P., 1999. Asynchronous random polling dynamic load balancing.

Es soll ein paralleler Radixsort Algorithmus für Integer entwickelt und in C++ implementiert werden. Dazu kann viel bestehender Code von unserem parallelen String Radix Sort wiederverwendet werden. Die eigentliche Herausforderung ist die Lastbalance bei ungleich verteilten Eingaben sicher zu stellen.

Diese Aufgabe wird an mehrere Gruppen vergeben werden, die verschiedene Ansätze ausprobieren können. Die performanteste Implementierung soll in unsere Algorithmen-Bibliothek aufgenommen werden (sofern der Quellcode lesbar und wartbar ist).

Eine Gruppe soll work-stealing implementieren, eine Gruppe kann voluntary work-sharing implementieren, und eine Gruppe kann einen spezielle Version für Permutation entwickeln.

• Grund Radix Sort in-place sequentiell: https://github.com/thrill/thrill/blob/master/thrill/common/radix_sort.hpp
• Parallelisiertes String Radix Sort: https://github.com/bingmann/parallel-string-sorting/blob/master/src/parallel/bingmann-parallel_radix_sort.hpp
• Timo's Doktorarbeit: https://arxiv.org/abs/1808.00963 (Kapitel 2,4)
• Algorithmen Bibliothek zur Verwendung in die der Sorter eingebunden werden soll: https://tlx.github.io/
• Ein github Repository: https://github.com/PiotrSypek/pradsort/
• Paper aus der Gruppe mit radix sort + virtual memory hack: Wassenberg, Jan, and Peter Sanders. "Engineering a multi-core radix sort." European Conference on Parallel Processing. Springer, Berlin, Heidelberg, 2011.

Ideensammlung:

• Ziel: als Benchmark werden integer pairs sortieren (`std::pair<uint32<sub>t</sub>, uint32<sub>t</sub>>`), die Funktion soll aber mit templates alle Typen unterstützen.
• Ziel: ohne OpenMP (am Ende, eventuell während der Entwicklung schon)
• Beobachtung: im Internet gibt es einige parallel radix sort, doch oft ohne Lastbalancierung.
• Unklar ob LSD oder MSD besser ist, das hängt vom Keyraum ab, auch hybride Techniken sind möglich.
• Als Interface würde ich folgende gemeinsame Definition vorschlagen, die aus Thrill's sequentiellen radix sort template method kommt:

/*!
 * Radix sort the iterator range [begin,end). Sort unconditionally up to depth
 * MaxDepth, then call the sub_sort method for further sorting. Small buckets
 * are sorted using std::sort() with given comparator. Characters are extracted
 * from items in the range using the at_radix(depth) method. All character
 * values must be less than K (the counting array size).
 */
template <
    size_t MaxDepth, typename Iterator,
    typename Comparator =
        std::less<typename std::iterator_traits<Iterator>::value_type>,
    typename SubSorter = NoOperation<void> >
static inline
void radix_sort_CI(Iterator begin, Iterator end, size_t K,
                   const Comparator& cmp = Comparator(),
                   const SubSorter& sub_sort = SubSorter());

Ein atomic counter, der zeitgleich von verschiedenen Threads verändert wird, ist eine häufige Quelle von Zugriffskonflikten auf shared-memory Maschinen. Bei einem alternativen Ansatz speichert man Änderungen in thread-lokalen Zwischenvariablen und ermittelt nur periodisch oder bei Bedarf die richtige Gesamtsumme.

Diese beiden Ansätze sollen implementiert werden. Weiter sollen Experimente auf verschiedenen multi-core Rechnern durchgeführt werden, um die Performance der zwei Ansätze mit verschiedenen CPU Befehlen zu messen.

Ziel ist es ein Wrapper Framework zu konstruieren, das Allokationen und Berechnungen koordiniert auf NUMA Knoten verteilt. Dazu soll ein bestehender C++ thread pool um NUMA Funktionalität erweitert werden und Wrapper-Funktionalität erstellt werden um die ausgeführten Jobs zu den auf den NUMA Knoten allozierten Speicherteilen passend zuzuordnen.

• https://en.wikipedia.org/wiki/Non-uniform_memory_access
• https://github.com/tlx/tlx/blob/master/tlx/thread_pool.hpp
• https://github.com/stanford-mast/Silo
• https://gist.github.com/lorenzhs/0a2a67b669779ab7a60e34fa0c566227