Parallel computing

Lectures

Lectures are on Fridays from 13.55 until 15.55 in room 01.03, Celestijnenlaan 200S.

We use the book `Parallel Scientific Computation -- a structured approach using BSP and MPI' by Prof. dr. R. H. Bisseling.

The course schedule follows. The material (slides) posted in the `Book paragraphs' and `Topics' column are mandatory to study, as is all corresponding material in the aforementioned book (including Chapter 4 up to and including section 4.5), with the exception of the chapter on the fast Fourier transform.

Lecture Date Book paragraphs Topics Additional material External links (optional material)
1 26th of September 1.4 Introduction & motivation to parallel scientific computation, parallel computing hardware. Exercise on basic communication primitives (solution) Multi-core processors, Infiniband.
2 3th of October 1.1, 1.2,
1.3, 1.4		 The BSP model and a standard BSP programming interface. - Guide on starting with MulticoreBSP for Java, BSP worldwide, BSPonMPI, MulticoreBSP.
3 10th of October 1.5-1.7;
2.1-2.2,
2.3		 Sequential in-place LU decomposition, BSP benchmarking, parallel in-place LU decomposition. Mandatory: follow the guide on starting with MulticoreBSP for C, or alternatively, follow the Java guide of the previous week. Do this sometime before the third practical session starts. Extra reading / exercise on the LU algorithm (optional, up to assignment D).
4 17th of October 2.4; 4.1,
4.2, 4.3
 The two-phase broadcast for LU decomposition.
Sparse matrix–vector multiplication.		 - -
Ex. 1 24th of October - Exercise session instead of lecture! (See below info on exercise session 1) - -
5 31th of October - Guest lecture by Prof. dr. Rob H. Bisseling on parallel graph matching - Corresponding papers Bisseling & Manne (preprint), 2007; Patwary, Bisseling, & Manne, 2010.
6 7th of November 4.4, 4.5 Sparse matrix partitioning and hyper-graph partitioning - The Mondriaan sparse matrix partitioner
Mandatory: follow these instructions before the coming exercise session. It is especially critical to register for use of the VSC supercomputers during those sessions!
7 14th of November - Shared-memory parallel computing, efficiency and scalability metrics for parallel computing. Amdahl's & Gustafson's Law (paper) The paper introducing the shared-memory MulticoreBSP, what is parallelism?.
8 21th of November - Parallel sorting. - -
9 28th of November - Mesh-based parallel algorithms, dynamic load-balancing, partitioning and load-balancing. Papers to summarise: Graph Partitioning, work-stealing I, or work-stealing II -
10 12th of December Appendix C Alternative approaches to parallelisation, other paradigms and programming interfaces. Multi-BSP (Valiant, 2011)
Practical sessions
Preliminary schedule; exercises will be announced in the week before the start of the session.

The practice sessions start on Thursday the 30th of October. There will be five in total. The first two will be pen-and-paper sessions, the last three will be hands-on parallel computing.
Session Date Time Location Exercises
1 24th of October 14.00-16.00 Celestijnenlaan 200S 01.03 Book section 1.9, exercises 1 and 2; plus additional material (See also: intro to mesh computations).
- 6th of November 10.30-13.00 Celestijnenlaan 200C 00.01 (PC-A) (cancelled)
2 13th of November10.30-13.00 Celestijnenlaan 200C 00.01 (PC-A) Introductory hands-on session on VIC-3
3 20th of November10.30-13.00 Celestijnenlaan 200C 00.01 (PC-A) Two-phase broadcast in the BSP LU decomposition. Pick up the following file; the exercise is contained within: bsp_lu.c. You can use testLU.m, extractLU.m, and readCyclic.m to test your LU algorithm (usage: `[orig,lu,pi]=testLU(M,N,1);' in octave, also see `help testLU').
4 27th of November10.30-13.00 Celestijnenlaan 200C 00.01 (PC-A) Pen and paper exercises
5 11th of December10.30-13.00 Celestijnenlaan 200A 00.124 Implementing the Sieve of Eratosthenes (see previous exercise)