M2R Parallel Systems

Table of Contents


---> misc
| ---> 2016
| ---> 2015
| ---> 2014
| ---> 2013
| ---> 2012
`--> Agenda

Parallel Systems

General Informations

These lectures take place from 9h30 to 12h45 every Monday or Wednesday depending on the lecturer in room


The coordinator for these lectures is Arnaud Legrand. The lecturers are Vincent Danjean and Arnaud Legrand .

In doubt, the planning with lecture rooms is available


(login/password is voirIMATEL/imatel, in case the link is broken go to the root of the server to get the whole schedule and look for PDES).


Today, parallel computing is omnipresent across a large spectrum of computing platforms. At the ``microscopic'' level, processor cores have used multiple functional units in concurrent and pipelined fashions for years, and multiple-core chips are now commonplace with a trend toward rapidly increasing numbers of cores per chip. At the ``macroscopic'' level, one can now build clusters of hundreds to thousands of individual (multi-core) computers. Such distributed-memory systems have become mainstream and affordable in the form of commodity clusters. Furthermore, advances in network technology and infrastructures have made it possible to aggregate parallel computing platforms across wide-area networks in so-called ``grids.'' The popularization of virtualization has allowed to consolidate workload and resource exploitation in ``clouds'' and raise many energy and efficiency issues.

An efficient exploitation of such platforms requires a deep understanding of both architecture, software and infrastructure mechanisms and of advanced algorithmic principles. The aim of this course is thus twofold. It aims at introducing the main trends and principles in the area of high performance computing infrastructures, illustrated by examples of the current state of the art. It intends to provide a rigorous yet accessible treatment of parallel algorithms, including theoretical models of parallel computation, parallel algorithm design for homogeneous and heterogeneous platforms, complexity and performance analysis, and fundamental notions of scheduling and work-stealing. These notions will always be presented in connection with real applications and platforms.

Program and expected schedule

Check last year's schedule to get a foretaste.

  • 23 September 2013 (9:30 - 12:45): Arnaud Legrand Introduction to parallel computing. High Performance Architectures Processors (superscalar, simultaneous multi-threading, multi-core, GPU…). Symmetric MultiProcessors. OS features for cluster computing Multi-threading. Cache-aware vs. cache-oblivious algorithms.
  • 02 October 2013 (9:30 - 12:45): Vincent Danjean How to Efficiently Program High Performance Architectures ? Classical HPC API: MPI, pthreads, openMPI, CUDA, openCL, …
    • Documents: slides PC_02_HPC_languages.pdf
    • Expexted work: Your next lecture with Vincent will be in the end of November. In the meantime, you should play with MPI on G5K: First, you may want to have a look at the following documents to know how to run an MPI code on G5K (Wikipage, and Cheat Sheet). Then, there are two possible options that do not illustrate the same issues:
      • Practical session on performance evaluation of parallel programs. PC_par_sort.pdf, parsort-1.0.tar.gz, mpi_sort.c This session is great for understanding the problems of measurement and parallel speedup. This kind of aspects is partially adressed in the Performance evaluation lecture but with multi-threaded code so you can compare between the two approaches.
      • Double broadcast parallel matrix multiplication 07_MPI_tutorial.tgz This session is great for understanding the data movements and distribution in an SPMD program and the power of collective communication operations. You'll probably need to have seen the lectures on Parallel algorithms first.
  • 07 October 2013 (9:30 - 12:45): Arnaud Legrand From clusters to Grids. Communication models.
    • Documents: slides PC_02_parallel_algorithms.pdf
    • References: I don't think reading these books will be particularly useful to you for this lecture (read more condensed information in wikipedia instead) but here are two classical references on Grid computing.

      • Fran Berman, Geoffrey Fox, and Anthony Hey. Grid Computing: Making the Global Infrastructure a Reality. John Wiley & Sons, 2003.
      • Ian Foster and Carl Kessellman. The Grid 2: Blueprint for a New Computing Infrastructure. Morgan Kaufmann, 2003.

      Regarding parallel algorithms, there are huge books on it but here is a more condensed one if you need:

      • Henri Casanova, Arnaud Legrand and Yves Robert. Parallel Algorithms Chapman & Hall, 2008.

      Note however that the set of slides is huge and self-content so that you do not have to study in additional books.

  • 14 October 2013 (9:30 - 12:45): Arnaud Legrand Parallel algorithms on a ring and on a grid. The key notions are speedup/efficiency, Amhdal's law, pipelining, changing granularity to improve efficiency, and searching for sequential time in parallel algorithms.
    • Documents: The series of slides from the previous lecture.
    • Work to do: You need to read the whole set of slides even if I haven't presented all of them during the lecture.
  • 21 October 2013 (9:30 - 12:45): Arnaud Legrand From fine-grain to coarse-grain. PRAM, sorting networks and application to implementation on NOWs.
    • Documents: PC_05_theory.pdf (you need to read and understand the whole set of slides, even those on FFT that have not been presented during the lecture; they are very similar in essence to the sorting networks and are thus a good exercise)
  • 4 November 2013 (9:30 - 12:45): Arnaud Legrand Modeling parallel programs and platforms. Fundamental characteristics: Work and Depth. Dataflow graph representation of an execution. BSP programs. Introduction to Scheduling.
  • 20 November 2013 (09:30-12:45): Vincent Danjean High Performance Networks: bandwidth, latency, DMA, PIO, overlapping. How to Efficiently Communicate on Distributed Architectures ? Research aspects of mixing different HP API (e.g. how to efficiently use MPI and pthreads, how to efficiently use threads on hierarchical platforms, ….)
  • 27 November 2013 (09:30-12:45): Vincent Danjean From parallelism-aware algorithms to parallelism-oblivious algorithm. Work, depth and work-stealing. Illustration with a real implementation of such technique.
  • 4 December 2013 (09:30-12:45): Vincent Danjean Work-stealing and data locality. Sorting and merging, FFT, matrix operations. Adaptive algorithms and cascading divide & conquer: prefix computation, data compression, linear system solving
  • 9 December 2013 (9:30-12:45): Arnaud Legrand Hype and trends: cloud computing and how Virtualization changed the Grid perspective, exascale computing and how energy issues changed the HPC perspective. Desktop Grids. On the convergence of cloud computing and desktop grids; Google Map Reduce.
  • 16 December 2013 (9:30-12:45): Arnaud Legrand Recent challenges and trends in HPC linear algebra: a recap on the whole lecture.
  • 16 December 2013 (13:45-16:00): Arnaud Legrand Answering last year's exam questions.
  • 20 January 2014 Exam

Course Organization

The course gives 6 credits (ECTS). In previous years, each student used to performs an individual performance evaluation study. Now that the MOSIG comprises a series of lectures on Performance Evaluation, this does not need to be done anymore solely in the context of the Parallel Systems lecture. There will be an exam at the end of the year and an extra lecture will be devoted to study together one of the exam of the previous years.


  • Henri Casanova, Arnaud Legrand and Yves Robert. Parallel Algorithms Chapman & Hall, 2008.