Parallele Algorithmen: Materialien zur Vorlesung

  1. Vorlesungsfolien
  2. Übungsfolien
  3. English lecture recordings (WS20/21)
  4. Deutsche Vorlesungsaufzeichung (WS17/18)
  5. Website vom WS19/20 (deutsch)
  6. Ilias-Kurs

Ankündigungen

Ü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:
  1. 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
  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).
  3. 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.
  4. 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
  5. 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
  6. 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).
  7. 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
  8. 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.
  9. 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)
  10. 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
  11. Concurrent Deferred Reference Counting with Constant-Time Overhead: Concurrent Deferred Reference Counting, Daniel Anderson, Guy E. Blelloch, Yuanhao Wei
Die möglichen Wikipediaartikel sind:
  1. „List Ranking“ auf Englisch.
  2. „Branch-and-Bound: Parallel Section“ auf Deutsch und Englisch.
  3. „Coordinator/Worker (früher Master/Slave) Load Balancing“ auf Deutsch oder Englisch.
  4. „h-Relation / irregular size messages“ auf Deutsch oder Englisch.
  5. „Distributed Memory Broadcasts (Binomial Tree, Hypercube, Pipelining)“ auf Deutsch.
  6. Eigene Themenvorschläge sind willkommen!

Buch

          Bookcover of Sequential and Parallel Algorithms and Data Structures