Parallele Algorithmen: Materialien zur Vorlesung
- Vorlesungsfolien
- Übungsfolien
- English lecture recordings (WS20/21)
- Deutsche Vorlesungsaufzeichung (WS17/18)
- Website vom WS19/20 (deutsch)
- Ilias-Kurs
Ankündigungen
- Die Deadline für die Programmieraufgabe inkl. Abschlussbericht und die Wikipediaartikel ist das Ende der Vorlesungszeit (12.02.2022)
- Die Miniseminarvorträge finden am Montag, den 7. Februar 2022 um 16:00 Uhr statt. Das ist der letzte reguläre Vorlesungstermin. An diesem Termin gilt für alle Kursteilnehmenden Anwesenheitspflicht, bitte teilen Sie uns rechtzeitig mit, falls Sie verhindert sind.
- Die Termine für die mündliche Prüfung sind: 23.02.2022, 31.03.2021 und 27.04.2022. Bitte kontaktieren Sie Frau Blancani (blancani (ät) kit.edu) falls Sie die Prüfung ablegen möchten.
- Die Benchmarkmaschine wurde am 10.12 umgezogen, daher kann das Verhalten der Plots abweichen. Die aktuelle Maschine hat 32 Kerne mit Hyperthreading (=64 Threads), verteilt auf 4 NUMA-Nodes. Sobald die Maschine final ist, folgt eine Ankündigung.
- Das Ilias Quiz steht ab Freitag, den 17. Dezember 8:00 Uhr bis Heilig Abend (24. Dezember) um 18:00 Uhr zur Verfügung. Die Ergebnisse werden pünktlich zur Bescherung an Heilig Abend um 18:00 Uhr angezeigt; die beiden Freitextaufgaben werden eventuell erst später bewertet.
- Die Ergebnisse des Ilias Quiz sind nun einsehrbar.
- Die Maschine für die Benchmarks wird sich nicht mehr ändern. Eine genauere Beschreibung der Hardware ist im Iliasforum zu finden.
- Die Bestenliste wurde zurückgesetzt. Um dort zu erscheinen, kann entweder ein neuer Commit gepusht werden oder die Pipeline manuell gestartet werden.
Übungsbetrieb
Der Übungsbetrieb wurde am 8. November vorgestellt (siehe Folien).
Die beiden für die Programmieraufgabe relevanten Paper sind: [1] Posypkin, M.A., Sigal, I.K.: A combined parallel algorithm for solving the knapsack problem. https://doi.org/10.1134/S1064230708040072 und [2] Rashid, Hammad and Novoa, Clara and Qasem, Apan.: An Evaluation of Parallel Knapsack Algorithms on Multicore Architectures. https://userweb.cs.txstate.edu/~aq10/papers/rashid_csc10.pdf [3] R. Bayer and B. Vöcking. Random knapsack in expected polynomial time. Journal of Computer and System Sciences, 69(3):306-329, 2004 [4] G. Nemhauser and Z. Ullmann. Discrete dynamic programming and capital allocation. Management Sciecne, 16(9):494-505, 1969 [] Siehe Buchlink unten, Kapitel 12.3.
Die Themen für die Miniseminarvorträge sind:
- An Algorithmic View on Big Data Frameworks (2 Personen): [1] Dean, Jeffrey, and Sanjay Ghemawat. "MapReduce: simplified data processing on large clusters." Communications of the ACM 51.1 (2008): 107-113. [2] Zaharia, Matei, et al. "Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing." Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association, 2012. [3] Bingmann, Timo, et al. "Thrill: High-performance algorithmic distributed batch data processing with C++." 2016 IEEE International Conference on Big Data (Big Data). IEEE, 2016. [4] S. Li, M. A. Maddah-Ali, and A. S. Avestimehr. Coded mapreduce. In Communication, Control, and Computing (Allerton), 2015 53rd Annual Allerton Conference on, pages 964– 971. IEEE, 2015. 2.2
- Concurrent Memory Reclamation Schemes: [1] Pöter, Manuel, and Jesper Larsson Träff. "A new and five older Concurrent Memory Reclamation Schemes in Comparison (Stamp-it)." arXiv preprint arXiv:1712.06134 (2017).
- Distributed Sorting with Histrograms: [1] Kale, Laxmikant V., and Sanjeev Krishnan. "A comparison based parallel sorting algorithm." 1993 International Conference on Parallel Processing-ICPP'93. Vol. 3. IEEE, 1993. [2] Solomonik, Edgar, and Laxmikant V. Kale. "Highly scalable parallel sorting." 2010 IEEE International Symposium on Parallel and Distributed Processing (IPDPS). IEEE, 2010. [3] Harsh, Vipul, Laxmikant Kale, and Edgar Solomonik. "Histogram sort with sampling." The 31st ACM Symposium on Parallelism in Algorithms and Architectures. 2019.
- Parallel Convex Hull: [1] Blelloch, Guy E., et al. "Randomized incremental convex hull is highly parallel." Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures. 2020. https://doi.org/10.1145/3350755.3400255
- Parallel String Sorting: [1] Ellert, Jonas, Johannes Fischer, and Nodari Sitchinava. "LCP-Aware Parallel String Sorting." arXiv preprint arXiv:2006.02219 (2020). [2] Die Conference Version des selben Papers: https://link.springer.com/chapter/10.1007%2F978-3-030-57675-2_21
- Parallel Tree Structure in Shared-Memory: [1] Sun, Y.: SPAA 2020 tutorial - Implementing Parallel Tree Structure in Shared-Memory. https://www.youtube.com/watch?v=anNSoQN5TC0 Sparse Matrix Multiplication [1] Gu, Zhixiang, et al. "Bandwidth-Optimized Parallel Algorithms for Sparse Matrix-Matrix Multiplication using Propagation Blocking." arXiv preprint arXiv:2002.11302 (2020).
- Parallelization and Load Balancing of Algorithms for Phylogenetic Inference: Kozlov AM, Aberer AJ, Stamatakis A. ExaML version 3: a tool for phylogenomic analyses on supercomputers. Bioinformatics. 2015;31(15):2577-2579. doi:10.1093/bioinformatics/btv184 und dort zitierte
- Parallel Merging of Paired-End Reads (Genome-Sequencing):
[1] T. Flouri, J. Zhang, L. Czech, K. Kobert, A. Stamatakis: "An efficient approach to merging paired-end reads and the incorporation of uncertainties". Chapter in Algorithms for NGS Data: Techniques, Approaches and Applications (Mourad Elloumi, editor), pages 299-325, Springer, 2017.
- Parallel Suffix Trees: Uwe Baier, Timo Beller, Enno Ohlebusch: Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies. ACM J. Exp. Algorithmics 22 (2017)
- Parallel SAT Solving: Nicolas Prévot, Mate Soos and Kuldeep S. Meel. Leveraging GPUs for Effective Clause Sharing in Parallel SAT Solving. SAT 2021 und Dominik Schreiber and Peter Sanders. Scalable SAT Solving in the Cloud. SAT 2021
- Concurrent Deferred Reference Counting with Constant-Time Overhead: Concurrent Deferred Reference Counting, Daniel Anderson, Guy E. Blelloch, Yuanhao Wei
Die möglichen Wikipediaartikel sind:
- „List Ranking“ auf Englisch.
- „Branch-and-Bound: Parallel Section“ auf Deutsch und Englisch.
- „Coordinator/Worker (früher Master/Slave) Load Balancing“ auf Deutsch oder Englisch.
- „h-Relation / irregular size messages“ auf Deutsch oder Englisch.
- „Distributed Memory Broadcasts (Binomial Tree, Hypercube, Pipelining)“ auf Deutsch.
- Eigene Themenvorschläge sind willkommen!
Buch
