Tomas Plachetka

Concurrent and Distributed Programming and Systems 2020/2021

Friday 14:00-17:20 online (was M.IX)

The evaluation of work during the semester (homeworks) forms 50% of the final grade, at least 40% are required.

• Motivation. Separation of algorithmic and concurrent aspects in C. Memory and time complexity of programs with I/O operations and dynamic memory allocation. Polling and its consequences.
• Threads. Thread state diagram. Shared variables, atomicity of memory accesses, critical regions. Decker's and Peterson's algorithms, assumptions on memory accesses. Deadlock, livelock. POSIX threads (pthread), mutexes, condition variables.
  Lecture notes
  Open Group pthread reference
  A pthread tutorial
  Another pthread tutorial
  Historical recommendation (when to use threads and when not, 1995)
• Libraries, thread-safety. Case study: shared stack.
• Measuring time. Sources of time in PCs, real-time clock (RTC), programmable interrupt timer (PIT). Access to time sources and alarms in POSIX processes. Precision of time measurements.
  Lecture notes
  A tutorial on PC timers
  Linux man clock_gettime(CLOCK_MONOTONIC_RAW, ...)
  Linux Device Drivers (Chapter 7)
  
• Threads in Java. Creation of a thread. Synchronised methods, synchronised blocks. Built-in reentrant mutexes. Methods join(), wait(), signal(). Problem with a direct use of synchronized methods.
  SCJP Sun Certified Programmer for Java (Chapter 9)
  H. Schildt: Java, The Complete Reference (Chapter 11)
• Multi-level memory. Examples of counter-intuitive behaviour of programs and their explanation. Means of memory synchronisation in C and Java. Volatile variables, implicit memory synchronisation.
  H. Boehm: Threads cannot be implemented as a library, ACM PLDI, 2005
  Java memory model (JSR133)
• OpenMP. Filozofia OpenMP. Fork-join paralelizmus. Architektura OpenMP.
  Specifikacia OpenMP
  Introduction to OpenMP (University of Oregon)
  Introduction to OpenMP (RWTH Aachen University)
  GOMP (GNU OpenMP)
  
• Paralellelisation of independent loops. Probabilistic model. Deterministic model. Parameters of models, goals of optimisation. Methods of load balancing.
  Chunking, factoring
  Work stealing

Homeworks

Please send me your solutions via email.

For writing programs in C, use this template. Make sure that 0 errors and 0 warnings are produced during the compilation and linking (make).

Homework 1 (due to 20.10.)

Homework 2 (due to 22.10.), attachment

Homework 3 (due to 5.11.), attachment

Homework 4 (due to 9.12.)

Homework 5 (due to 9.12.)