Concurrency and Paralelism
Objectives
At the end of this course, the student will have acquired the knowledge, skills and competencies that will enable them to:
Know:
- Understand the concepts of concurrency and parallelism, and how these are useful in the software development process;
- Identify the models used to solve problems using multiprocessor systems;
- Know the paradigms used to develop algorithms on multiprocessor systems;
- Know the languages, libraries and tools used to develop concurrent programs;
- Understand the correctness properties of concurrent systems, e.g. linearization, progress, fairness and deadlock-freedom.
- Understand the properties of shared memory, e.g., register constructions and atomic snapshots.
- Be able to evaluate the use of synchronization primitives used in concurrent data structures, from atomic registers, consensus protocols and FIFO queues, to universal constructs such as consensus universality.
- Be familiar with common concurrency problems and how to mitigate and avoid them.
At the end of this course, the student will have acquired the knowledge, skills and competencies that will enable them to:
Know:
- Understand the concepts of concurrency and parallelism, and how these are useful in the software development process;
- Identify the models used to solve problems using multiprocessor systems;
- Know the paradigms used to develop algorithms on multiprocessor systems;
- Know the languages, libraries and tools used to develop concurrent programs;
- Understand the correctness properties of concurrent systems, e.g. linearization, progress, fairness and deadlock-freedom.
- Understand the properties of shared memory, e.g., register constructions and atomic snapshots.
- Be able to evaluate the use of synchronization primitives used in concurrent data structures, from atomic registers, consensus protocols and FIFO queues, to universal constructs such as consensus universality.
- Be familiar with common concurrency problems and how to mitigate and avoid them.
Know-how:
- Identify and exploit opportunities for concurrency and parallelization in a software system;
- Partition a problem into multiple tasks to be executed in a concurrent system.
- Reason about the behavior of concurrent systems;
- Build correct and efficient concurrent systems;
- Apply programming patterns, including spin-locks, monitors, barriers and work-stealing.
- Use programming languages such as Java and C and libraries to develop concurrent software systems;
- Develop concurrent data structures, e.g. linked lists, queues, stacks, scatter tables and skiplists.
- Use programming tools to develop concurrent applications, including the design, implementation, debugging and installation phases.
- Analyze synchronization patterns, e.g., coarse- and fine-grained locks, optimistic and lazy locks, non-blocking synchronization and atomic synchronization primitives.
- Predict and measure the performance characteristics of concurrent systems.
General characterization
Code
11158
Credits
6.0
Responsible teacher
João Manuel dos Santos Lourenço
Hours
Weekly - 4
Total - 52
Teaching language
Inglês
Prerequisites
Available soon
Bibliography
Main textbook:
• Herlihy, M., Shavit, N., Luchangco, V., & Spear, M. (2020).
The art of multiprocessor programming (2nd ed.).
Morgan Kaufmann. ISBN 978-0-12-415950-1.
Additional textbooks:
• Paul E. McKenney (2024).
Is Parallel Programming Hard, And, If So, What Can You Do About It?
Release v2024.12.27a. Meta Platforms, Inc. Available at https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.2024.12.27a.pdf
• Guerraoui, R., & Kuznetsov, P. (2018).
Algorithms for concurrent systems.
PPUR Presses Polytechniques.
Teaching method
Lectures with presentation and discussion of the conceptual content covered in the course. Most of these classes are conducted in an interactive way, where after motivation, the concepts, problems and their approaches/solutions are discussed. At this point, attempts are made to encourage student participation by asking them about possible solutions to solve the problem being addressed. Generally, even if they are not able to present the complete solution, when properly guided and with the appropriate “tips”, students are able to make suggestions that go in the right direction, which is motivating for them and great for the classe’s dynamics.
The main objective of the laboratory classes is to allow the students to consolidate the knowledge, acquired both in the lectures and by non-supervised study, by addressing the practical aspects of the course, namely the techniques, methodologies and tools for developing correct and well-performing concurrent programs. The direct contact with the teacher when solving programming problems, either the lab classes’ mini-projects or the home project, gives them the opportunity to discuss and evaluate their ideas, work-plans and solutions.
Evaluation method
Any student involved in cheating in any assessment element (detected immediately or afterwards) will fail the course. In these cases, the provisions of article 10.3 of the NOVA FCT Assessment Regulations will always be taken into account.
During the semester, in lab classes, the proposed exercises will be solved individually or in a group of students. These exercises are not assessed.
During the semester, a project will be developed in groups of three students. This project will be assessed using group criteria and individual criteria. This assessment will contribute to the Laboratory Assessment component (CLB) of the final grade for the course. Students who do not sign up to any of the projects submitted for assessment will receive a mark of zero in the CLB.
Two individual theoretical-practical tests will be carried out during the semester. These tests will be assessed and will contribute to the Theoretical-Practical Assessment (TPA) component of the final grade for the course. If a student misses a theoretical-practical test, they will score zero for that test.
At the end of the semester, students who have failed the course are entitled to take an exam. The exam will be assessed and will be considered as the Theoretical-Practical Assessment (TPA) component of the final grade for the course.
At the end of the semester, students who have already passed the course may (with prior registration) take an exam to improve their grade. The exam will be assessed and will be considered as the Theoretical-Practical Assessment (TPA) component of the final grade for the course.
All tests and exams are written, face-to-face and individual, with no consultation materials or access to a cell phone or calculator allowed.
Students who, under the Assessment Regulations, are not obliged to attend practical classes will still have to carry out the group project and submit it for assessment on the due date.
Assessment:
- Laboratory component (CLB): grade obtained in the project, on a scale of 0.00 to 20.00 (to two decimal places). Minimum mark: CLB >= 9.5.
- Theoretical-Practical Component (CTP): arithmetic average of the two theoretical-practical tests, on a scale of 0.00 to 20.00 (to two decimal places). Minimum mark: CTP >= 9.5.
- Failure to obtain a minimum mark in the CLB or CTP component implies immediate failure of the course.
Final Grade (FC):
- Weighted average of the CLB (20%) and CTP (80%) components, rounded to the nearest integer.
In accordance with the FCT assessment regulations, due to the lack of attendance this academic year (and the consequent change in the formula for calculating the final mark) the attendance and respective marks obtained last year are not taken into account.
Subject matter
1. Introduction to concurrency and its challenges.
2. Mutual exclusion: Time; Critical Sections; Locks; Fairness.
3. Concurrent objects: Correctness; Progress; Sequential Objects; Quiescent and sequential Consistency; Linearizability.
4. Foundations of shared memory: Registers; Register Constructions; Atomic Snapshots.
5. Primitive synchronization operations: Monitors and Conditions; Spin-Locks, Readers–Writers Locks; Semaphores.
6. Universality of consensus: Universality; Lock-Free Universal Constructions.
7. Spin locks and contention: Test-And-Set Locks Spin Locks; Exponential Backoff; Queue and hierarchical Locks.
8. Lock-free data structures: Lists; Queues; the ABA Problem.
9. Transaction memory: Transactions and Atomicity; Software TM; Hardware TM.
10., Work management: Parallelism; Multiprocessor scheduling; Work distribution; Futures; Work-stealing dequeues.
11. Concurrency without shared data: Message passing, Actors, and Active objects.