Concurrency and Paralelism
Objectives
This course aims at providing the students with a solid background on 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 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, Pedro Abílio Duarte de Medeiros
Hours
Weekly - 4
Total - 56
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 sylabus 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
The evaluation is continuous and composed by:
a) Average of three multiple-choice tests to be taken during the semester (in the absence or failure of tests, students may take an exam at the end of the semester). The average grade of the tests (rounded to the hundredths) or the exam will have a weight of 65% in the final classification.
b) Individual classification in the project (rounded to the hundredths), with a weight of 30% in the final classification.
c) Active participation in theoretical and practical classes, as well as in the Piazza forum and in interaction with colleagues, will have a 5% weight in the final grade (note that "active participation in classes" is not "being present").
Note: The final exam, when taken for both passing and grade improvement, replaces assessment component a) in the final grade calculation.
To obtain frequency to UC it is necessary:
- Obtain a minimum grade of 9.50 values in the evaluation component b) (project).
Note: If the previous year''s frequency is used, the weight of components a), b) and c) will be 70%, 30% and 0% respectively.
To pass the course you need:
i) Attend the discipline obtained in this edition or in the previous year.
ii) That the classification in the evaluation component a) is greater than or equal to 9.50 values.
iii) That the final grade is greater than or equal to 9.50 values.
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.