Concurrency and Paralelism
Objectives
This course aims at providing the students with a solid background in concurrency. Namely, at the end of the course, the students are expected to understand the problems related to concurrency and the execution of concurrent programs, to know the mechanisms available in the programming languages to specify concurrent programs, to know how to develop correct and efficient concurrent programs applying common programming techniques and patterns.
Knowledge:
- Understand the concepts of concurrency and parallelism, and how they are useful when designing software;
- To identify the models used for problem-solving in multiprocessors and highly-parallel systems;
- To know the paradigms used in the development of algorithms for multiprocessors and highly-parallel systems;
- To know the languages, libraries, and tools used in the development of concurrent and parallel programs;
- Be familiar with common concurrency problems, and how to mitigate or avoid them.
Application:
- Be able to identify and exploit opportunities for concurrency and parallelization within a software system;
- Be able to partition a problem into multiple tasks to be executed in a parallel system;
- Be able to reason about the behavior of concurrent and parallel programs;
- Be able to build correct and efficient concurrent and parallel algorithms;
- Be able to use the Java/C-like programming languages and parallel libraries to develop parallel software systems;
- Be able to use programming tools in the development of concurrent and parallel applications, including the design, implementation, debugging, and deployment stages;
- Be able to predict and measure the performance characteristics of a parallel system.
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 bibliographic references:
- McCool M., Arch M., Reinders J.; Structured Parallel Programming: Patterns for Efficient Computation; Morgan Kaufmann (2012); ISBN: 978-0-12-415993-8
- Raynal M.; Concurrent Programming: Algorithms, Principles, and Foundations; Springer-Verlag Berlin Heidelberg (2013); ISBN: 978-3-642-32026-2
Teaching method
Teaching consists of exposing the syllabus in lectures and problem-solving in laboratory practical classes. In the lab, students analyze, implement, and evaluate concurrent and parallel algorithms. Some practical classes are dedicated to the realization of programming projects.
Evaluation method
Theoretical-Practical Component (CTP)
The theoretical-practical component (CTP) is obtained by solving two individual tests during the semester or one individual exam. Both the tests and the exam will be closed-book and take place in-site at FCT-NOVA (dates to be defined by FCT-NOVA services).
Both the tests and the exam will have questions about the practical/lab exercises and the final project. No student (first-attempt/repeating) is exempt from answering the questions about the lab works and the project.
Use of a simple (non-alphanumeric and non-programmable) claculator is allowed in both the tests and the exam.
Units: CTP will be rounded to one hundredth.
Minimum grade: a CTP grade ≥ 8.50 is required.
Laboratory Component (CL)
The laboratory component (CL) is obtained by applying the following formula:
CL = 0.6 * CG + 0.4 * CI
Where
CG = group classification
CI = individual classification
Group classification (CG) is defined by the merit of developing a programming project and preparing a report that describes, evaluates, and analyzes the solution developed. The project is developed in groups of four students, and the CG classification is identical for all the group members.
Individual classification (CI) is defined by individual merit in the development process of the programming project referred to in CG. This component is measured by weighting the distribution of work among the elements of the group, as reported by the students in the project report, with the amount, difficulty, and relevance of individual work perceived through the commits in the group''s GIT repository.
Both the teacher and the students can request an oral test (with all the group members or just a subset) to present and discuss the project work done and reported.
Units: CG, CI, and CL will be rounded to one hundredth.
Relevant dates:
- Project assignment: TBD (see course slides)
- Code submission: TBD (see course slides)
- Report submission: TBD
- How to submit code and report: fill a form with the ID of the commit (issued within the deadline) to be considered
Participation Component (CP)
The participation component (CP) is obtained through participation in the various channels of communication with the teacher and colleagues. This component will be defined by weighting the individual participation of each student, considering the amount and content of the participation in the Piazza forum. The participants with higher impact on the group/class and/or support/clarification to colleagues will be more valued.
Units: CP will be rounded to one hundredth.
Minimum grade: there is no minimum limit for this classification.
Final Classification (CF)
CF = 0.5 * CTP + 0.5 * CL + 0.05 * CP
Units: the CF will be rounded to the nearest whole number.
Subject matter
- Parallel programming
The spectrum of high-demanding computational problems; regular and irregular problems; strategies for problem decomposition and their mapping to programming patterns; the transactional and map-reduce models. - Parallel architectures
Flynn''''s taxonomy; performance theory (including Amdahl''''s and Gustafson''''s laws). - Concurrency control and synchronization
Competition and collaboration; atomicity; linearization; monitors; locks; semaphores; barriers; producer-consumer; multi-reader single-writer locks; futures; concurrency in practice in Java and C. - Safety and liveness
Safety vs. liveness; progress; deadlock; deadlock prevention, avoidance, detection, and recovery; livelock; livelock avoidance; priority inversion; priority inheritance. Lock-free algorithms. - The transactional model
Composite operations; transactions (serializability), optimistic concurrency control (OCC), and transactional memory. - Concurrency without shared data
Active objects; message passing; actors.