M1 IF, ENS Lyon, 2018-2019

TDs (tutorials) and TPs (lab sessions) - Valentin Le Fèvre and Laureline Pinault

- [ParAlg]
**Parallel Algorithms.**H. Casanova, A. Legrand, Y. Robert. Chapman and Hall/CRC Press, 2008. - [Tel]
**Introduction to Distributed Algorithms.**Gerard Tel. Second Edition, Cambridge University Press, 2000. - [Fokkink]
**Distributed Algorithms: An Intuitive Approach.**Wan Fokkink. MIT Press, 2013. - [Sched]
**Scheduling and Automatic Parallelization.**A. Darte, Y. Robert, F. Vivien. Birkhäuser, 2000.

The programming homework was distributed on October 12, and the due date is December

- Lecture 1: Mon Sep. 10, Amphi F:
Sorting networks: Odd-even merging network, and Batcher's merge sort
network.

**Reading:**[ParAlg Chapter 2.1]

**Wed Sep. 12 at 10.15am**: TP MPI 1

- Lecture 2: Mon Sep. 17, Amphi B: Sorting networks: 0-1 principle, Odd-even
transposition sort. Introduction to PRAMs.

**Reading:**[ParAlg Chapters 2.2 and 1.1]

**Todo:**Review the whole chapter on sorting networks: 01-SortingNetworks.pdf.

For the PRAMs, understand the list ranking algorithm, and which parts of the algorithm will need to be clarified.

Fri Sep. 21,**8-10am**: TD sorting networks

- Lecture 3: Mon Sep. 24, Amphi F: PRAMs: More algorithms with pointer
jumping, and performance evaluation of PRAM algorithms (cost, work,
speedup, efficiency, and simulation result).

**Reading:**[ParAlg Chapters 1.1 and 1.2]

Fri Sep. 28: TP MPI 2

- Lecture 4: Mon Oct. 1st: PRAMs: Brent's theorem, comparison of
PRAM models, and Cole's sorting machine.

**Reading:**[ParAlg Chapters 1.3 and 1.4]

**Todo:**Review the whole chapter on PRAMs: 02-PRAMs.pdf.

In particular, read carefully the last part of the chapter (1.4.2, 1.4.3) to fully understand how the sorting machine works.

Fri Oct. 5: TD PRAM 1/2

- Lecture 5: Mon Oct. 8: Algorithms on processor rings or grids:
Case study of the unidirectional ring (broadcast, scatter,
all-to-all, pipelined broadcast).

**Reading:**[ParAlg Chapter 3.3]

**Todo:**Read and understand the PRAM sorting machine (if not done yet), and be sure to fully understand the first algorithms on a ring, and the principle of pipelining, since we will move on to more complex algorithms next class.

Fri Oct. 12: TP MPI 3

- Lecture 6: Mon Oct. 15: Algorithms on processor rings or grids:
matrix-vector and matrix-matrix multiplication; stencil applications
on a ring of processors.

**Reading:**[ParAlg Chapter 4]

**Todo:**Review the whole chapter on processor rings: 03-Rings.pdf. We will move to processor grids next time.

Fri Oct. 19: TD PRAM 2/2

- Lecture 7: Mon Oct. 22: Algorithms on processor rings or grids:
matrix-matrix multiplication on a grid of processors.

**Reading:**[ParAlg Chapter 5]

**Todo:**Review the whole chapter on processor grids: 04-Grids.pdf. In particular, read carefully Section 5.3.2 (Grid vs Ring), Section 5.4 (2D block cyclic data distribution), and try to think how to do a matrix transposition in parallel (if possible, efficiently) on a 2D grid of processors.

Fri Oct. 26: TP MPI 4

- Autumn Break

- Mid-term exam: Mon Nov. 5

*Topics covered:*Sorting networks, PRAMs, Algorithms on rings/grids of processors.

*Documents allowed:*Only one double-sided A4 sheet of paper (with whatever you want on it). Nothing else is allowed (course notes, books, phones, computers...).

Fri Nov. 9: TP MPI 5

- ER01

- Lecture 8: Mon Nov. 19: Distributed algorithms: Model, and
first wave algorithms (Ring and Tree algorithms).

**Reading:**[Fokkink Chapter 2, Tel Chapter 2]

**Todo:**Make sure that the model is clear to you, and play with the Tree algorithm on examples to convince yourself that exactly two processes decide. What is the time complexity of the Ring algorithm and the Tree algorithm? Can you prove that they are wave algorithms?

Fri Nov. 23: TP MPI 6

- ER02

- Lecture 9: Mon Dec. 3: Distributed algorithms: Elementary
results about wave algorithms; theorems and proofs that Ring and Tree
are wave algorithms; more wave algorithms (Echo, Polling, Phase);
traversal algorithms.

**Reading:**[Fokkink Chapter 4, Tel Chapter 6]

Fri Dec. 7: TD Distributed algorithms

- Lecture 10: Mon Dec. 10: Distributed algorithms: DFS traversal
algorithms, and election algorithms.

**Reading:**[Fokkink Chapter 9, Tel Chapter 7]

**Todo:**Review the whole chapter on distributed algorithms: 05-Distributed-F.pdf and 05-Distributed-T.pdf

Fri Dec. 14: TP Distributed algorithms

Programming homework due~~Dec. 12~~Dec. 16

- Lecture 11: Mon Dec. 17,
**Amphi B**: Task graph scheduling: Where do task graphs come from, and what is a schedule of a task graph; scheduling with unlimited processors, and with p processors (NP-completeness).

**Reading:**[ParAlg Chapter 7.1, 7.2, 7.3, 7.4.1]

**Todo:**Play with the task graph coming from linear system solve to compute top levels, bottom levels, makespan with unlimited resources. Refresh your knowledge of NP-completeness and prove Theorem 5 (NP-completeness of variants of Pb(p)). Happy holidays!

Fri Dec. 21: TD Exam review

- Winter Break

- Lecture 12: Mon Jan. 7, Amphi B:
Task graph scheduling: list scheduling heuristics for Pb(p), and
adding communication costs.

**Reading:**[ParAlg Chapter 7.4, 7.5, 7.6]

Fri Jan. 11: TD Task graph scheduling

- Lecture 13: Mon Jan. 14, Amphi B:
Task graph scheduling: Naive and modified critical path heuristic
for Pb(p) with communications, and clustering heuristics.

**Reading:**[ParAlg Chapter 7.7, Sched Chapter 2.6]

**Todo:**Execute the heuristics on different task graphs to fully understand them, and read the guaranteed heuristic of 7.6.2. Review the whole scheduling chapter: 06-Scheduling.pdf, and the part on clustering: 07-Clustering.pdf.

Fri Jan. 18: TD Task graph scheduling

- Final exam: Monday, January 21, 9h-12h, Amphi B

*Topics covered:*Sorting networks, PRAMs, Algorithms on rings/grids of processors, Distributed algorithms, Scheduling.

*Documents allowed:*Only one double-sided A4 sheet of paper (with whatever you want on it). Nothing else is allowed (course notes, books, phones, computers...).

E-Mail: Anne.Benoit at ens-lyon.fr | Last modified: Mon Jan 14 15:41:00 CET 2019 |