Proseminar Rechnernetze:
Challenges in Parallel Computing

Ausgewählte Aspekte des parallelen Rechnens Seminar zu ausgewählten Themen der Informatik
für Bachelor im Sommersemester 2016 (LMU, TUM Bachelor - IN0014)
Prof. Dr. D. Kranzlmüller Prof. Dr. H.-G. Hegering (em.) Tobias Fuchs, M.Sc.

Aktuelles

Inhalt des Seminars

Überblick

Parallel Computing - Parallelrechnen - befasst sich mit der gleichzeitigen Verwendung von mehreren Rechenkernen zur Lösung eines Problems. Das historische Einsatzgebiet von Parallelrechnern ist das technisch-wissenschaftliche Hoch- und Höchstleistungsrechnen (High Performance Computing, HPC) wo heute in Supercomputern häufig mehrere Zehntausend Rechenkerne zum Einsatz kommen.

Der Einsatzbereich von Parallelrechnern hat sich jedoch in den letzten Jahren in alle Bereiche der IT ausgedehnt. Alle Server, Desktop und Notebook CPUs sind heute mit Multicore CPUs ausgestattet und seit kurzem folgen auch Smartphones und Tablets diesem Trend. In jedem Fall kann nur durch explizite parallele Programmierung das volle Potential einer solchen Platform ausgenutzt werden und Parallelrechnen wird zusehends zur "must have" Qualifikation für IT Fachleute.

Der Entwurf und die Implementierung paralleler Programme stellt Entwickler vor besondere Herausforderungen an mehreren Fronten wie z.B. Entwurf, Tests, formale Verifizierung und dem Zusammenspiel mit parallelen Rechnerarchitekturen.
Im Rahmen dieses Seminars werden ausgewählte Themen aus diesen Feldern vorgestellt.

Organisation

Ablauf

Um der Anzahl der Seminarteilnehmer gerecht zu werden, werden Sie in 2er-Gruppen arbeiten. Sie erstellen in der Gruppe zu dem Ihnen zugeteilten Thema eine Seminararbeit, die von beiden Gruppenmitgliedern am Ende des Semesters in einer Blockveranstaltung präsentiert wird. Jede Gruppe erhält einen Betreuer.
Termine und Agenda werden im Laufe des Semesters auf dieser Seite veröffentlicht.

Themen zur Bearbeitung werden in einer Einführungsveranstaltung vergeben, deren Zeit und Ort auf dieser Seite bekannt gegeben wird. Soweit möglich werden wir Ihren Themenpräferenzen entgegenkommen. Die Teilnahme an der Einführungsveranstaltung ist für alle Teilnehmer verpflichtend.

Im Laufe des Semesters werden zudem eine Veranstaltung zu Präsentationstechniken und zum Umgang mit der Textsetzungssoftware LaTeX, die Sie bevorzugt für Ihre Ausarbeitungen verwenden sollen, angeboten. Bitte beachten Sie dazu auch die Rubriken Aktuelles und Termine. Wir werden außerdem versuchen, der Bedeutung des Themas durch mindestens einen externen Expertenvortrag Rechnung zu tragen. Ort und Zeit dieser Veranstaltung werden rechtzeitig bekannt gegeben.
Die Teilnahme an diesen Veranstaltungen ist Pflicht.

Ausarbeitung und Vorträge

Das schriftlichen Ausarbeitungen der Seminararbeiten werden im Format
Springer Lecture Notes in Computer Science (LNCS, Proceedings)
verfasst.

Der Umfang der Ausarbeitung ist 10 bis maximal 12 Seiten.
Eine Überschreitung von 12 Seiten ist nur im Einzelfall nach Rücksprache mit Ihrem Betreuer möglich.

Vortragslänge im Blockseminar ist 25 Minuten. Die Bewertung basiert jeweils zur Hälfte auf Ausarbeitung und Vortrag.
Verwenden Sie für Ihre Präsentation bitte diese Vorlage.

Die Vortragslänge wird unbedingt eingehalten. Wir empfehlen als Vorbereitung ausdrücklich einen Probevortrag vor Ihrem Betreuer.

Voraussetzungen

Für eine erfolgreiche Teilnahme am Seminar ist die Anwesenheit an allen Präsenzterminen Pflicht. Kenntnisse der Vorlesungen Parallel Computing - Grundlagen und Anwendungen und Entwurf und Implementierung Paralleler Programme oder äquivalente Vorkenntnisse sind hilfreich, aber nicht Voraussetzung.

Termine

• Die Einführungsveranstaltung zum Seminar findet am
  14. April 2016 um 16 Uhr
  in der Oettingenstraße 67, Raum 057 statt.

• Die Veranstaltung zu Präsentationstechniken findet am
  12. Mai 2016 um 16 Uhr
  in der Oettingenstraße 67, Raum 057 statt.

• Die Veranstaltung zur Einführung in LaTex findet am
  19. Mai 2016 um 16 Uhr
  in der Oettingenstraße 67, Raum 057 statt.

• 22. Juni 2016 bis 12:00 Uhr:
  Abgabe der Vortragsfolien
  per Mail an Betreuer und seminar16@nm.ifi.lmu.de

• 23. Juni 2016 bis 12:00 Uhr:
  Abgabe der schriftlichen Ausarbeitungen
  per Mail an Betreuer und seminar16@nm.ifi.lmu.de

• 23. Juni 2016, 16 Uhr, Oettingenstraße 67, Raum 057:
  Vortrag des externen Experten
  Dr. Tobias Schüle, Siemens Corporate Research and Technology.
  Die Teilnahme ist verpflichtend.

• Die Blockveranstaltung zur Präsentation der Abschlussvorträge findet am
  Freitag, 24. Juni ab 16 Uhr und Samstag, 25. Juni ab 9 Uhr
  in der Oettingenstraße 67, Raum 057 statt.
  Die Teilnahme an beiden Tagen ist verpflichtend.
  Der endgültige Zeitplan der Voträge is jetzt verfügbar.
  Wichtiger Hinweis: Die angegebenen Zeiten beinhalten 5 Minuten Diskussion zu jedem Seminarthema, d.h. 25 bzw. 15 Minuten müssen für die Vorträge unbedingt eingehalten werden.

Themenliste

Die hier aufgeführten Referenzen zu den Seminarthemen sollen nur einen ersten Einstieg in das jeweilige Thema bieten.
Sie stellen also kein abgeschlossenes Quellenverzeichnis dar und müssen in Ihrer Ausarbeitung nicht zwingend berücksichtigt werden.

---

Allgemeine Referenzen:

• M. Moir and N. Shavit.
  Concurrent Data Structures. Handbook of Data Structures and Applications. Chapman and Hall/CRC Press, 2007.

• U. Gleim and T. Schüle.
  Multicore-Software: Grundlagen, Architektur und Implementierung in C/C++, Java und C#. Dpunkt Verlag, 2011.

Lesenswert zum Hintergrund des Seminars:

• Is Parallel Programming Hard, And, If So, What Can You Do About It?
  Paul McKenney, Linux Technology Center, IBM. 2014.

Hardware

• Acceleratoren: GPGPUs und CUDA

  • Sim, Dasgupta, Kim, Vuduc.
    A Performance Analysis Framework for Identifying Potential Benefits in GPGPU applications. ACM SIGPLAN Notices, 2012.

  • Halyo, LeGresley, Lujan et al.
    First Evaluation of the CPU, GPGPU and MIC Architectures for Real Time Particle Tracking Based on Hough Transform at the LHC. Journal of Instrumentation, IEEE, 2014

  • Yang, Xiang, Kong, Zhou.
    A GPGPU Compiler for Memory Optimization and Parallelism Management. ACM Sigplan Notices, 2010.

• Acceleratoren: Xeon Phi

  • Heinecke, Klemm, Bungartz.
    From GPGPU to Many-Core: NVidia Fermi and Intel Many Integrated Core Architecture. Computing in Science & Engieering, 2012.

  • Fang, Jianbin, et al.
    Test-driving Intel Xeon Phi. Proceedings of the 5th ACM/SPEC International Conference on Performance Engineering. ACM, 2014.

  • Ramachandran, Aditi, et al.
    Performance evaluation of NAS parallel benchmarks on Intel Xeon Phi. 42nd International Conference on Parallel Processing (ICPP). IEEE, 2013.

  • Jeffers, James, and James Reinders.
    Intel Xeon Phi Coprocessor High-Performance Programming. Newnes, 2013.

  • Heinecke, Alexander, et al.
    Design and implementation of the linpack benchmark for single and multi-node systems based on Intel Xeon Phi Coprocessor. IEEE 27th International Symposium on Parallel & Distributed Processing (IPDPS), IEEE, 2013.

• NUMA: Architekturen und Unterstützung in Betriebssystemen

  • Blagodurov, Zhuravlev, Dashti, Fedorov.
    A Case for NUMA-aware Contention Management on Multicore Systems. (2011-05-02).

  • Majo, Gross.
    Memory management in NUMA multicore systems: trapped between cache contention and interconnect overhead. ACM SIGPLAN Notices, 2011

  • Majo, Gross.
    Matching Memory Access Patterns and Data Placement for NUMA Systems. Proceedings of the Tenth International Symposium on Code Generation and Optimization - CGO'12.

  • Mallon, Taboada, Teijeiro, Tourino et al.
    Performance evaluation of MPI, UPC and OpenMP on multicore architectures. Recent Advances in Parallel Computing, 2009

  • Liu, Mellor-Crummey.
    A tool to analyze the performance of multithreaded programs on NUMA Architectures. Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming - PPoPP 2014.

• Transactional Memory

  • Hammond, Wong, Chen, Carlstrom et al.
    Transactional memory coherence and consistency. Proceedings of the 31st annual International Symposium on Computer Architecture (ISCA). 2004

  • Christopher J. Rossbach, Owen S. Hofmann, Emmett Witchel.
    Is Transactional Programming Actually Easier? 2012

  • Boehm, Gottschlich, Luchangco, Michael, Moir, Nelson, et al.
    Transactional Language Constructs for C++. Programming Language C++, Evolution Working Group. 2012

  • Herlihy, Moss.
    Transactional Memory: Architectural Support for Lock-Free Data Structures. 1993

  • Shavit, Touitou.
    Software transactional memory. 1997

  • Jacobi, Slegel, Greiner.
    Transactional Memory Architecture and Implementation for IBM System Z. 2012

• Non-Volatile Memory

  • Caulfield, Adrian M., et al.
    Understanding the impact of emerging non-volatile memories on high-performance, IO-intensive computing. Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society, 2010.

  • Li, Dong, et al.
    Identifying opportunities for byte-addressable non-volatile memory in extreme-scale scientific applications. Parallel & Distributed Processing Symposium (IPDPS), 2012 IEEE 26th International. IEEE, 2012.

  • Mittal, Sparsh, and Jeffrey Vetter.
    A survey of software techniques for using non-volatile memories for storage and main memory systems. 2014

  • Vetter, Jeffrey S., and Sparsh Mittal.
    Opportunities for nonvolatile memory systems in extreme-scale high-performance computing. Computing in Science & Engineering 17.2 (2015)

Formale Aspekte

• Performance Models: Roofline, ECM

  • Williams, Waterman, Patterson.
    Roofline: An Insightful Visual Performance Model for Multicore Architectures . Communications of the ACM, 2009

  • Sim, Dasgupta, Kim, Vuduc.
    A Performance Analysis Framework for Identifying Potential Benefits in GPGPU Applications . ACM SIGPLAN Notices, 2012

  • Hoefler, Gropp, Kramer, Snir.
    Performance Modeling for Systematic Performance Tuning . State of the Practice Reports, 2011

  • Hager, Treibig, Habich.
    Exploring Performance and Power properties of Modern Multicore Chips via Simple Machine Models . Practice and Experience in Concurrency and Computation. 2014. Presentation slides

  • Hofmann, Eitzinger, Fey.
    Execution-Cache-Memory Performance Model: Introduction and Validation . 2015

Algorithmen und Datenstrukturen

• Methoden für Work Sharing und Task Scheduling

  • Blumofe, Leiserson.
    Scheduling Multithreaded Computations by Work Stealing.
    J. ACM, 46(5):720-748, September 1999.

  • Muddukrishna, Jonsson, Vlassov.
    Locality-Aware Task Scheduling and Data Distribution on NUMA Systems.
    OpenMP in the Era of Low Power Devices and Accelerators, pages 156-170. Springer, 2013.

  • Vikranth, Wankar, Rao.
    Topology Aware Task Stealing for On-chip NUMA Multi-core Processors.
    2013 International Conference on Computational Science

  • Joao, Suleman, Mutlu, Patt.
    Bottleneck Identification and Scheduling in Multithreaded Applications.
    2012

• Parallele und verteilte Sortieralgorithmen

  • Peter Sanders, Thomas Hansch.
    Efficient massively parallel Quicksort.
    In: Solving Irregularly Structured Problems in Parallel. Springer, 1997, pp. 13-24.

  • Hanmao Shi and Jonathan Schaeffer.
    Parallel sorting by regular sampling.
    In: Journal of Parallel and Distributed Computing. 14.4 (1992), pp. 361-372.

  • Edgar Solomonik and Laxmikant Kale.
    Highly scalable parallel sorting.
    2010

  • Bruce Wagar.
    Hyperquicksort: A fast sorting algorithm for hypercubes.
    In: Hypercube Multiprocessors. 1987, pp. 292-299.

• Parallele und verteilte Allokatoren

  • Maged M. Michael.
    Scalable Lock-Free Dynamic Memory Allocation
    2004

  • Maged M. Michael.
    Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects.
    2004

  • Eunhwan Shin, Inhyuk Kim, Junghan Kim, Young Ik Eom.
    Waitfree Synchronization with Efficient memory Reclamation by using Chronological Memory Allocation.
    Proceedings of the 2011 International Conference on Computational Science and Its Applications - Volume Part V, ICCSA'11, pages 217-231. Berlin, Heidelberg, 2011. Springer-Verlag.

  • Stellwag, Krainz, Schröder-Preikschat.
    A Waitfree Dynamic Storage Allocator by Adopting the Helping Queue Pattern.
    Proceedings of the 9th IASTED International Conference, volume 676, page 79.

  • Gidenstam, Papatriantafilou, Sundell, Tsigas.
    Efficient and reliable lock-free memory reclamation based on reference counting.
    IEEE Transactions: Parallel and Distribed Systems, August 2009.

  • Alistarh, Eugster, Herlihy, Matveev.
    Stacktrack: An Automated Transactional Approach to Concurrent Memory Reclamation.
    2014

• Algorithmen und Datenstrukturen für parallele Echtzeitanwendungen

  • Timothy L. Harris.
    A pragmatic implementation of non-blocking linked-lists.
    In Proceedings of the 15th International Conference on Distributed Computing, DISC'01, pages 300-314, London, UK, 2001. Springer-Verlag.

  • Danny Hendler, Nir Shavit, and Lena Yerushalmi.
    A scalable lock-free Stack Algorithm.
    In Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'04, pages 206-215, New York, NY, USA,
    2004. ACM.

  • Alex Kogan and Erez Petrank.
    Wait-free queues with multiple enqueuers and Dequeuers.
    SIGPLAN Not. 46(8):223-234, February 2011.

  • Maged M. Michael.
    Hazard pointers: Safe Memory Reclamation for Lock-free Objects.
    IEEE Trans. Parallel Distrib. Syst. 15(6):491-504, June 2004.

  • Polytechnic Institute of Porto (ISEP-IPP).
    On the use of Work-Stealing Strategies in Real-Time Systems.
    Berlin, Germany, 2013.

  • Shahar Timnat, Anastasia Braginsky, Alex Kogan, and Erez Petrank.
    Wait-free Linked-lists.
    In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'12, pages 309-310, New York, USA, 2012. ACM.

  • Kunlong Zhang, Yujiao Zhao, Yajun Yang, Yujie Liu, and Michael Spear.
    Practical Non-blocking Unordered Lists.
    In Distributed Computing (Yehuda Afek, editor), volume 8205 of  Lecture Notes in Computer Science, pages 239-253.
    Springer Berlin Heidelberg, 2013.

Software Engineering

• Testen und Race Detection in parallelen Anwendungen

  • Lu, Park, Seo, Zhou.
    Learning from Mistakes - A Comprehensive Study on Real World Concurrency Bug Characteristics.
    ACM Sigplan Notices, Volume 43, pages 329-339. ACM, 2008

  • Choi, Lee, Loginov, Callahan, Sarkar, Sridharan.
    Efficient and precise datarace detection for multithreaded object-oriented programs.
    PLDI, 2002.

  • Kasikci, Zamfir, Candea.
    Data Races vs. Data Race Bugs: Telling the Difference with Portend.
    ACM SIGPLAN Notices Vol. 47, 185-198. ACM, 2012

  • Flanagan, Freund.
    Atomizer: a dynamic atomicity checker for multithreaded programs.
    POPL, 2004.

  • Jin, Zhang, Deng.
    Automated Concurrency-Bug Fixing.
    2012

• Debuggen paralleler Anwendungen

  • Abramson, Foster, Michalakes.
    Relative Debugging: A New Methodology for Debugging Scientific Applications.
    Communications of the ACM, 1996.

  • Bohm, Behalek, Meca et al.
    Visual Programming of MPI Applications: Debugging and Performance Analysis.
    Lecture Notes in Computer Science and Engineering, IEEE, 2013.

  • Suboti, Brinkmann, Marjanovi.
    Programmability and Portability for Exascale: Top Down Programming Methodology and Tools with StarSs.
    2013.

  • Humphrey, Meng, Berzins et al.
    Systematic Debugging Methods for Large-Scale HPC Computational Frameworks.
    Computing in Science, IEEE, 2014.

• Profiling paralleler Anwendungen / Performance Analysis Tools

  • Bohme, David, et al.
    Identifying the Root Causes of Wait States in Large-Scale Parallel Applications.
    39th International Conference on Parallel Processing (ICPP), IEEE, 2010.

  • Tallent, Nathan R., John M. Mellor-Crummey, Allan Porterfield.
    Analyzing lock contention in multithreaded applications.
    ACM Sigplan Notices. Vol. 45. No. 5. ACM, 2010.

  • Tallent, Nathan R., Laksono Adhianto, John M. Mellor-Crummey.
    Scalable identification of load imbalance in parallel executions using call path profiles.
    Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE Computer Society, 2010.

  • Adhianto, Banerjee, Fagan et al.
    HPCToolkit: Tools for performance analysis of optimized parallel programs
    Concurrency and Computation: Practice and Experience, 2010.

  • Treibig, Hager, Wellein.
    Likwid: A lightweight performance-oriented tool suite for x86 multicore environments.
    39th International Conference on Parallel Processing Workshops (ICPPW), 2010

  • Brunst, Mohr.
    Performance analysis of large-scale OpenMP and hybrid MPI/OpenMP applications with Vampir NG.
    OpenMP Shared Memory Parallel Programming, pages 5-14. Springer. 2008

  • Geimer, Wolf, Wylie et al.
    The Scalasca performance toolset architecture.
    Concurrency and Computation: Practice and Experience. Wiley, 2010

• Neuerungen in OpenMP 4.0 / 4.5

  • Martorell, Xavier, et al.
    Evaluating the Impact of OpenMP 4.0 Extensions on Relevant Parallel Workloads.
    OpenMP: Heterogenous Execution and Data Movements: 11th International Workshop on OpenMP, IWOMP 2015. Aachen, Germany, October 1-2, 2015, Proceedings. Vol. 9342. Springer, 2015.

  • Papadogiannakis, Alexandros, Spiros, Agathos, Dimakopoulos.
    OpenMP 4.0 Device Support in the OMPi Compiler.
    OpenMP: Heterogenous Execution and Data Movements. Springer International Publishing, 2015. 202-216.

  • Virouleau, Philippe, et al.
    Evaluation of OpenMP dependent tasks with the KASTORS benchmark suite.
    Using and Improving OpenMP for Devices, Tasks, and More. Springer International Publishing, 2014. 16-29.

• RDMA in MPI 3.x - Spezifikation und Implementierungen

  • Hoefler, Dinan, Thakur, Barrett et al.
    Remote Memory Access Programming in MPI-3.
    ACM Transactions on Parallel Computing, 2015

  • Hoefler, Dinan, Buntinas, Balaji, Barrett et al.
    Leveraging MPI’s One-Sided Communication Interface for Shared-Memory Programming.
    Springer, 2012

  • Zhou, Idrees, Gracia.
    Leveraging MPI-3 Shared-Memory Extensions for Efficient PGAS Runtime Systems.
    Euro-Par 2015: Parallel Processing, 2015

  • Li, Subramoni, Hamidouche et al.
    High Performance MPI Datatype Support with User-Mode Memory Registration: Challenges, Designs, and Benefits.
    2015 IEEE International Conference on Cluster Computing (CLUSTER). 2015

  • Dinan, Balaji, Buntinas, Goodell et al.
    An Implementation and Evaluation of the MPI 3.0 One‐sided Communication Interface.
    Concurrency and Computation: Practice and Experience, 2016

  • Gu, Small, Yuan, Marathe et al.
    Protocol Customization for Improving MPI Performance on RDMA-enabled Clusters.
    Springer. International Journal of Parallel Computing, 2013

  • Zhao, Buntinas, Zounmevo et al.
    Toward Asynchronous and MPI-Interoperable Active Messages.
    13th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid), 2013

• Chapel und Partitioned Global Address Space

  • Chamberlain, Bradford, Callahan, Zima.
    Parallel Programmability and the Chapel Language.
    International Journal of High Performance Computing Applications, 2007.

  • Diaconescu, Zima.
    An Approach to Data Distributions in Chapel.
    International Journal of High Performance Computing Applications 2007.

  • Weiland.
    Chapel, Fortress and X10: Novel Languages for HPC.
    EPCC, The University of Edinburgh, Tech. Rep. HPCxTR0706 (2007).

  • Sidelnik et al.
    Performance Portability with the Chapel Language.
    Parallel & Distributed Processing Symposium (IPDPS), 2012 IEEE 26th International. IEEE, 2012.

• Multithreading-Konzepte in C++11/14

  • Williams, Anthony.
    C++ Concurrency in Action.
    London, 2012.

  • Wu, Di, et al.
    An Empirical Study on C++ Concurrency Constructs.
    Empirical Software Engineering and Measurement (ESEM), 2015 ACM/IEEE International Symposium on. IEEE, 2015.

Kontakt

Fragen, Kritik und Anregungen sind immer willkommen. Nutzen Sie bitte die seminarspezifische E-Mail-Adresse seminar16@nm.ifi.lmu.de, um mit uns in Kontakt zu treten.