Parallelism

This course is given at spring 2019

Objectives

  • Understanding the difference between sequential and parallel programming
  • Being able to write parallel algorithms from scratch
  • Implementing and measuring the performance of classical algorithms

Outline

  1. Introduction to parallelism and concurrency
    1. Hardware : multi-cpu, multi-core, GPUs, Flynn classification
    2. Low level tools : semaphore and monitor
  2. Data parallelism
    1. Data distribution (cyclic, bloc...)
    2. Introduction to OpenMP
    3. The P-RAM model
  3. Basic parallel algorithms
    1. Analysis of parallel algorithms (complexity, efficiency...)
    2. Simulation of P-RAMs, Brent's principle
    3. Reducing the number of processors
    4. SCAN/PREFIX
  4. Sorting in parallel
    1. Sorting on PRAM
    2. Bitonic sorting network

Grading

The course will be graded with two individual projects (50%) and a written exam (50%)

Lab Sessions

Projects