Concurrency and Paralelism (2017/2018) - Departamento de Informática
Description

This course aims at exposing the students to a set of knowledge and competences that enable them to tackle the increasingly relevant problem of programming parallel and concurrent systems. To achieve this, the course addresses both the parallel programming “in the large”, oriented towards clustering architectures and the cloud, and the development of concurrent programs, oriented towards multiprocessor architectures.

The topic of parallel programming emphasizes the methodologies for the design of parallel algorithms and applications, including using the map-reduce model. The topic of concurrent programming emphasizes the properties of concurrent programs and the methodologies, techniques and tools for developing correct concurrent programs.

In the laboratorial component of this course the students will apply the concepts acquired in the lectures in the development of parallel or concurrent applications, making use of existing parallel libraries (e.g., Hadoop for map-reduce) and tools to access application’s correctness and predict and evaluate the performance.

The choice of using Java provides access to a series of valuable tools; additionally, the object-oriented nature of the language allows for encapsulating, when convenient, unnecessary details.

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.
Syllabus
  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
Student work
  Hours per credit 28
  Hours per week Weeks Hours
Aulas práticas e laboratoriais   28.0
Aulas teóricas   28.0
Avaliação   8.0
Self study   56.0
Project   48.0
Total hours 168
ECTS 6.0