Concurrency and Paralelism
Code
11158
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Informática
Credits
6.0
Teacher in charge
João Manuel dos Santos Lourenço, Pedro Abílio Duarte de Medeiros
Weekly hours
4
Total hours
56
Teaching language
Português
Objectives
The course is included in the consolidation block of the degree. Its main objective is to give an overview of the abstractions and tools used in multiprocessor programming.
Knowledge:
• To identify the models used for problem solving in multiprocessors;
• To know the paradigms used in the development of algorithms for multiprocessors;
• To evaluate the correction and performance of concurrent and parallel algorithms;
• To know the languages, libraries and tools used in the development of concurrent and parallel .programs
Application:
• Partitioning a problem to execute it efficiently on a multiprocessor;
• To use the Java language for developing concurrent applications;
• To make contact with the tools used in the development of a concurrent and parallel application, during the design, implementation, debugging and deployment stages.
Subject matter
1. Introduction to concurrent execution.
1.1. Properties and basic abstractions of concurrent execution.
1.2. Races and deadlocks. Techniques to avoid them.
2. Multiprocessors.
2.1. Taxonomy of multiprocessor architectures.
2.2. Cache coherence in shared memory multiprocessors.
2.3. Speedup. Amdahl’s law.
3. Concurrent programming with shared memory.
3.1. Basic mechanisms for shared memory synchronization.
3.2. Monitors.
3.3. Concurrent data structures. Case study: lists.
4. Transactions and transactional memory.
4.1. Concept of transaction.
4.2. Concurrency control: principles and algorithms.
4.3. Software transactional memory. Hardware support.
5. Parallel programming.
5.1. Basic synchronization and communication mechanisms for distributed memory.
5.2. Strategies for problem decomposition.
5.3. Programming models and their mappings.
5.3. Map-Reduce model case study.
Bibliography
Main reference:
[1] Michel Raynal. "Concurrent Programming: Algorithms, Principles, and Foundations". Springer Heidelberg. ISBN: 978-3-642-32026-2(print), 978-3-64232027-9(ebook).
Additional references:
[2] Michael L. Scott. Shared-Memory Synchronization. Synthesis Lectures on Computer Architecture 2013 8:2, 1-221. Morgan&Claypool Publishers. ISBN: 9781608459568 paperback. ISBN: 9781608459575 ebook.
[3] Michael. Breshears, The Art of Concurrency: A Thread Monkey’s Guide to Writing Parallel Applications. O’Reilly Media, Inc., 2009.
[4] M. Herlihy, N. Shavit. The Art of Multiprocessor Programming. Morgan Kauffman, 2008.
[5] P. Pacheco. An Introduction to Parallel Programming. Morgan Kauffman, 2011
[6] T. Mattson, B. Sanders, B. Massingill. Patterns for Parallel Programming. Addison-Wesley, 2004.
Evaluation method
The final grade is calculated with the following parameters:
a) 3 tests scheduled during the semester. The average of the classification of the testes (always rounded to two decimal digits) will weigt 70% in the final grade.
b) 2 group projects. The average of the classification of the projects (always rounded to two decimal digits) will weigt 30% in the final grade.
c) presence and participation in lectures and lab classes will give a bonus of at most 10%.
Note: The final exam, taken for either approval or grade improvement ("melhoria de nota"), will replace the component a) above in the evaluation for the final grade.
To get frequency ("frequência") in the course it is necessary:
d) to have each project graded with at least 6,0 points.
e) that the average of the grades of the projects is larger or equal to 9.5 points.
Note: students with frequency from last years may require for the classification of frequency to be considered this year.
To get approved in the course it is required that:
f) the student has frequency in the course, obtained either this year or last year.
g) the average of the component a) to be larger or equal to 9.5 points.
g) the final grade to be larger or equal to 9.5 points.