Parallel computing
Lectures
Lectures are on Fridays from 13.55 until 15.55 in room 00.04, 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 (after lecture 9, the schedule is tentative). The material (slides) posted in the `Book paragraphs' and `Topics' column are mandatory to learn, as is all corresponding material in the aforementioned book (including Chapter 4 up to and including section 4.5).
| Lecture |
Date |
Book paragraphs |
Topics |
Additional material |
External links
|
| 1 |
27th of September |
1.4 |
Introduction & motivation to parallel scientific computation, parallel computing hardware. |
Exercise on basic communication primitives (solution) |
Multi-core processors, Infiniband. |
| 2 |
4th 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 |
11th of October |
1.5-1.7;
2.1-2.2,
2.3 |
BSP programming in practice, BSP benchmarking. Sequential in-place LU decomposition, 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 |
18th of October |
2.4;
4.1,
4.2, 4.3,
4.4
|
The two-phase broadcast for LU decomposition.
Sparse matrix–vector multiplication. |
- |
- |
| 5 |
25th of October |
- |
Guest lecture by Prof. dr. Rob H. Bisseling on parallel graph matching. |
- |
Optional: corresponding papers Bisseling & Manne (publically available preprint), 2007; and Patwary, Bisseling, & Manne, 2010. |
|
| - |
1st of November |
|
All Saint's Day -- no lecture |
|
| 6 |
8th of November |
- |
Parallel sorting, parallel mesh-based computations, parallel efficiency, and scalability metrics |
- |
Amdahl's & Gustafson's Law (paper) |
| 7 |
15th of November |
4.5 |
Sparse matrix partitioning and (hyper-)graph partitioning |
- |
The Mondriaan sparse matrix partitioner |
| 8 |
22nd of November |
- |
Shared-memory parallel computing
Includes a case studies on the Intel Xeon Phi accelerator. |
- |
The paper introducing the shared-memory MulticoreBSP. |
| 9 |
29th of November |
Appendix C |
Alternative approaches to parallelisation, other paradigms and programming interfaces. |
What is parallelism? |
- |
| - |
6th of December |
|
No class! |
|
|
| 10 |
13th of December |
- |
Dynamic load-balancing, partitioning and load-balancing. |
Papers to summarise: Graph Partitioning, work-stealing I, Multi-BSP, or work-stealing II |
- |
- |
Practical sessions
Preliminary schedule; exercises will be announced in the week before the start of the session.
The practice sessions start on Thursday the 7th of November. There will be five in total. The first two will be pen-and-paper sessions, the last three will be hands-on parallel computing.
Note the location changes from exercise session 3 on!
| Session |
Date |
Time |
Location |
Exercises |
| 1 |
7th of November | 10.30-13.00 |
Celestijnenlaan 200B 01.14 |
Book section 1.9, exercises 1 and 2; plus additional material (See also: intro to mesh computations). |
| 2 |
14th of November | 10.30-13.00 |
Celestijnenlaan 200B 01.14 |
Exercises |
| 3 |
21th of November | 10.30-13.00 |
Celestijnenlaan 200C PC-A |
Introductory hands-on session on VIC-3 |
| 4 |
28th of November | 10.30-13.00 |
Celestijnenlaan 200C 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'). |
| 5 |
5th of December | 10.30-13.00 |
Celestijnenlaan 200C PC-A |
Implementing the Sieve of Eratosthenes |