2024-2025 - M1 Info

Summary

During these labs you will discover a few aspects of concurrent and parallel programming.

• Concurrent programming: how to write a correct multi-threaded program, and avoid data races and deadlocks using synchronisation primitives?

• Parallel programming: how to write an efficient parallel program that takes advantages of multi-threading and hardware (for us, GPU) to do computations on large data sets?

Requirements

• notions of C programming, memory management, Java programming, Python programming
• implementations of basic data structures (stacks, queues, lists, etc) in such languages
• a laptop with a development environment for C and Java
• VPN access to MIAGEIA, or access to a Python notebook with CUDA/GPU support

Evaluation

The last lab will be graded.

Syllabus

• oct 16th, oct 23rd Lab 1 (C)
  PThread library. Notion of thread, data race, mutex, deadlock, deadlock-avoidance.

• nov 5th Lab 2 (JAVA) / TP 2 Java threads. Atomic instructions, monitors, condition variable, semaphore.

• nov 13th TP 3 Loop parallelisation. Map Reduce. Cellular automaton simulation.

• nov 20th 15:45-18:45 Lab 4 (PYTHON) CUDA/GPU Programming. Image processing. Game of Life.

• nov 27th Lab 4 / Exam

Not seen in this lecture (among other interesting topics)

• non-blocking data structures, linearisability, various forms of “fairness” (wait free, obstruction free, etc)
• weak memory models
• message-passing (MPI, etc)

Resources

• Co-operating sequential processes by Edsger Dijsktra
• Ressources, concurrency, and local reasonning by Peter O’Hearn
• The art of multiprocessor programming by Maurice Herlihy and Nir Shavit

Annales

• sujet d’examen 2021-2022
• sujet d’examen 2022-2023