Universidade Nova de Lisboa

Universidade Nova de Lisboa

Faculdade de Ciências e Tecnologia

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

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:

  1. Understand the concepts of concurrency and parallelism, and how they are useful when designing software;
  2. To identify the models used for problem solving in multiprocessors and highly-parallel systems;
  3. To know the paradigms used in the development of algorithms for multiprocessors and highly-parallel systems;
  4. To know the languages, libraries and tools used in the development of concurrent and parallel programs;
  5. Be familiar with common concurrency problems, and how to mitigate or avoid them.

Application:

  1. Be able to identify and exploit opportunities for concurrency and parallelization within a software system;
  2. Be able to partition a problem into multiple tasks to be executed in parallel system;
  3. Be able to reason about the behavior of concurrent and parallel programs;
  4. Be able to build correct and efficient concurrent and parallel algorithms;
  5. Be able to use the Java/C-like programming languages and parallel libraries to develop parallel software systems;
  6. Be able to use programming tools in the development of concurrent and parallel applications, including the design, implementation, debugging and deployment stages;
  7. Be able to predict and measure the performance characteristics of a parallel system.

Subject matter

  1. 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.
  2. Parallel architectures
    Flynn''''''''''''''''s taxonomy; performance theory (including Amdahl''''''''''''''''s and Gustafson''''''''''''''''s laws).
  3. 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.
  4. Safety and liveness
    Safety vs. liveness; progress; deadlock; deadlock prevention, avoidance, detection, and recovery; livelock; livelock avoidance; priority inversion; priority inheritance. Lock-free algorithms.
  5. The transactional model
    Composite operations; transactions (serializability), optimistic concurrency control (OCC) and transactional memory.
  6. Concurrency without shared data
    Active objects; message passing; actors.

Bibliography

Main bibliographic references:

  1. McCool M., Arch M., Reinders J.; Structured Parallel Programming: Patterns for Efficient Computation; Morgan Kaufmann (2012); ISBN: 978-0-12-415993-8
  2. Raynal M.; Concurrent Programming: Algorithms, Principles, and Foundations; Springer-Verlag Berlin Heidelberg (2013); ISBN: 978-3-642-32026-2

Courses