5.00 credits
30.0 h + 15.0 h
Q2
Teacher(s)
Language
English
> French-friendly
> French-friendly
Prerequisites
Required : principles of computer systems, as targeted in course LINFO1252
Main themes
For a long time, general-purpose CPUs focused on supporting efficiently a single thread of execution. Improvements in chip manufacturing allowed packing more transistors on the same surface of a silicon wafer, and run resulting CPUs at higher frequencies. Single-threaded applications would simply run faster with every new processor generation. This era is now over. The industry hit several limitations known as the power wall, the memory wall and the ILP wall. No longer able to vertically scale-up CPUs supporting a single thread of execution, chip manufacturers have started packing together multiple, simpler units of execution, or cores. Exploiting the power of multiple cores requires exploiting parallelism in applications using multiple threads. Writing concurrent code requires identifying and managing concurrency, and introducing the necessary synchronization for correctness. Writing scalable and performant concurrent code requires understanding this tradeoff between synchronization and parallelism and mastering efficient implementations of shared data structures and algorithms for concurrent execution. Finally, multicore CPUs employ a complex memory layout, and the assumption of uniform memory access times is no longer valid. Understanding the impact of non-uniform memory accesses (NUMA) is therefore important to write efficient code for multicore CPUs.
This course will provide students with the necessary tools and knowledge to write efficient and scalable code for modern multicore CPUs. It will detail the mechanisms available for synchronization, starting from the implementation of language constructs such as locks, monitors or condition variables, to the direct uses of CPU-provided synchronization primitives (e.g. compare-and-swap) to build efficient and scalable data structures. It will emphasize the performance aspects of multicore programming: the impact of synchronization primitives, the impact of non-uniform memory access, and the impact of multiple-level memory hierarchies. It will finally offer an opening to the future of multicore programming with an introduction to transactional memory and to the support for speculative execution in modern CPUs (e.g. Intel Haswell), and discuss the execution model for concurrent code running on GPUs.
This course will provide students with the necessary tools and knowledge to write efficient and scalable code for modern multicore CPUs. It will detail the mechanisms available for synchronization, starting from the implementation of language constructs such as locks, monitors or condition variables, to the direct uses of CPU-provided synchronization primitives (e.g. compare-and-swap) to build efficient and scalable data structures. It will emphasize the performance aspects of multicore programming: the impact of synchronization primitives, the impact of non-uniform memory access, and the impact of multiple-level memory hierarchies. It will finally offer an opening to the future of multicore programming with an introduction to transactional memory and to the support for speculative execution in modern CPUs (e.g. Intel Haswell), and discuss the execution model for concurrent code running on GPUs.
Learning outcomes
At the end of this learning unit, the student is able to : | |
Given the learning outcomes of the "Master in Computer Science and Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:
|
|
Content
This course targets programming models and methods for scalable applications on modern multi-processor and multi-core architectures.
In a first short part, it provides the necessary elements of theory and defines consistency protocols, in order to be able to understand the challenges and tradeoffs associated with shared-memory concurrent programming. The emphasis is on performance and scalability aspects (efficient simultaneous use of multiple cores).
The rest of the course surveys a number of fundamental algorithmic techniques for building shared memory concurrent data structures. It studies the performance implications of these data structures and algorithmic constructs in the context of modern architectures, taking into account various aspects such as the memory and cache hierarchy, hardware consistency protocols, and non-uniform memory accesses (NUMA).
The course is accompanied by a number of practical projects. A multi-core machine is available for the experiments. Students will be able to evaluate the performance and scalability of various algorithms and data structures seen in class.
In a first short part, it provides the necessary elements of theory and defines consistency protocols, in order to be able to understand the challenges and tradeoffs associated with shared-memory concurrent programming. The emphasis is on performance and scalability aspects (efficient simultaneous use of multiple cores).
The rest of the course surveys a number of fundamental algorithmic techniques for building shared memory concurrent data structures. It studies the performance implications of these data structures and algorithmic constructs in the context of modern architectures, taking into account various aspects such as the memory and cache hierarchy, hardware consistency protocols, and non-uniform memory accesses (NUMA).
The course is accompanied by a number of practical projects. A multi-core machine is available for the experiments. Students will be able to evaluate the performance and scalability of various algorithms and data structures seen in class.
Teaching methods
- Lectures
- Readings and/or production of tutorial videos
- Practical sessions
- Mini project
Evaluation methods
Modes d'évaluation :
L'évaluation des travaux soumis (projets, travaux pratiques, travail individuel, et de manière générale toute activité donnant lieu à évaluation) est basé sur la matériel (code, rapports, et tout autre matériel) soumis par l'étudiant·e, accompagné sur demande du professeur par un examen oral complémentaire.
Evaluation methods:
The evaluation of produced work (projects, practicals, individual work, and all graded activities in general) is based on the submitted code, reports, and other material submitted by the student and can be accompanied, upon request of the professor, by an oral examination.
Unless explicitly mentioned, any work or assignment in this course must remain confidential and personal. Sharing information and/or code with other students (out of the declared partner for group works) is a case of plagiarism.
Rules regarding the use of artificial intelligence (AI) for continuous assessment activities
The use of AI for practical work and the mini-project is not encouraged, since completing them manually is the best way to acquire the skills targeted by the course. If its use is authorized (whether to generate code or documentation), it is subject to the following rules:
- Projets et contrôle continu (40% de la note finale)
- Examen sur table comportant deux parties (60% de la note finale)
- Une première de questions de cours (questions ouvertes et QCM)
- Une seconde partie portant sur un ou plusieurs articles de recherche du domaine préalablement fournis aux étudiant·es.
- La proportion entre les deux parties est variable mais aucune ne dépassera 70% de la note. Les QCM n'entraînent pas de points négatifs pour une question individuelle mais la section QCM dans son ensemble peut demander un seuil minimal de réponses correctes avant de valoir des points.
L'évaluation des travaux soumis (projets, travaux pratiques, travail individuel, et de manière générale toute activité donnant lieu à évaluation) est basé sur la matériel (code, rapports, et tout autre matériel) soumis par l'étudiant·e, accompagné sur demande du professeur par un examen oral complémentaire.
Evaluation methods:
- Projects and continuous evaluation (40% of the final grade)
- Final exam (60% of the final grade), in two parts:
- First part: open questions and multiple-choice/answer questions about the course material;
- Second part: open questions and multiple-choice/answer questions about one or several scientific publication(s) provided to the student(s) ahead of the exam.
- The ratio of points between the two parts can vary but no part will count for more than 70% of the grade. Individual multiple-choice/answer questions cannot yield negative points, but the score for the complete multiple-choice/answer questions section may require a threshold number of correct answers to grant points.
The evaluation of produced work (projects, practicals, individual work, and all graded activities in general) is based on the submitted code, reports, and other material submitted by the student and can be accompanied, upon request of the professor, by an oral examination.
Unless explicitly mentioned, any work or assignment in this course must remain confidential and personal. Sharing information and/or code with other students (out of the declared partner for group works) is a case of plagiarism.
Rules regarding the use of artificial intelligence (AI) for continuous assessment activities
The use of AI for practical work and the mini-project is not encouraged, since completing them manually is the best way to acquire the skills targeted by the course. If its use is authorized (whether to generate code or documentation), it is subject to the following rules:
- Students must take full responsibility for their work and be able to explain orally all the code and deliverables (documentation, deployment scripts, etc.) submitted as part of the practical work.
- The use of AI must be precisely documented in the documentation of each submitted assignment, in a dedicated section indicating which AIs were used and for which part. Submitting code or documentation generated partially or entirely by AI without documenting this use will be considered plagiarism. Students who did not use AI must also indicate this in the section.
- Use of AI that is deemed abusive and undermines the acquisition of the knowledge targeted by the project may be considered an irregularity under Section 7, Articles 107 and following of the General Regulations for Studies and Exams (RGEE), with all the resulting consequences, as provided in Articles 111 and following of the RGEE. In the event of suspected abusive use of AI in the submitted project, or of an incomplete or inaccurate report of AI use, the course instructor may summon the student concerned for an additional oral consultation and take the necessary measures in agreement with the EPL jury chair.
Other information
All relevant course material and slides as well as practical information related to the course will be accessible on Moodle, which will also be the primary means of communication between the teacher(s) and the students.
Bibliography
The Art of Multiprocessor Programming, Maurice Herlihy and Nir Shavit, Morgan Kaufmann. ISBN 978-0-12-370591-4.
UCL library reference 10.620.426
UCL library reference 10.620.426
Faculty or entity
