DAT2| SW6
Aalborg University| Computer Science Dpt.| Control Engineering Dpt.
Home| Course
Course
› Schedule › Lecture 1 › Lecture 2 › Lecture 3 › Lecture 4 › Lecture 5 › Lecture 6 › Lecture 7 › Lecture 8 › Lecture 9 › Lecture 10 › Lecture 11 › Lecture 12 › Lecture 13 › Lecture 14 › Lecture 15
Home
› Welcome ! › Prerequisites › Course Ojectives › Text Books › Additional Materials › Course Grading › Contact

Schedule

See Calendar

Lecture Title Date Time Room
1 Introduction to Parallel Computing
Introduction to the Case-Study
Wed 6/2/08 8h15-12h 0.1.95
2 Parallel Programming Platforms
The PRAM Model
Mon 11/2/08 12h30-16h15 0.1.95
3 Physical Organization of Parallel Platforms
Parallelizing the Model-Checker
Wed 13/2/08 8h15-12h 0.1.95
4 Help on the API Programming Shared Address Space Platforms Mon 25/2/08 12h30-16h15 0.1.95
5 Communication Costs in Parallel Machines
Process-Processor Mapping
Preliminaries to Parallel Algorithm Design
Wed 27/2/08 8h15-12h 0.1.95
6 Decomposition Techniques and Tasks
Mapping Techniques for Load Balancing
Methods for Containing Interaction Overheads
Parallel Algorithm Models
Mon 3/3/08 12h30-16h15 0.1.95
7 Programming Using the Message Passing Paradigm Mon 10/3/08 12h30-16h15 0.1.95
8 MPI (cont.)
MPI in our model-checker
API of the MPI library
Wed 12/3/08 8h15-12h 0.1.95
9 Basic Communication Operations
Wed 26/3/08 8h15-12h 0.1.95
10 Communication Operations (cont.) Mon 31/3/08 12h30-16h15 0.1.95
11 Analytical Modeling of Parallel Programs Wed 2/4/08 8h15-12h 0.1.95
12 Sorting Mon 14/4/08 12h30-16h15 0.1.95
13 Dense Matrix Algorithms Wed 16/4/08 8h15-12h 0.1.95
14 Graph Algorithms Mon 21/4/08 12h30-16h15 0.1.95
15 Guest Lecture by Gerd Behrmann Wed 30/4/08 8h15-12h 0.1.95
The schedule is preliminary and will be changed.
Since the exercises count in your assignments, no solution will be provided unless you all finish them.

Lecture 1: Introduction to Parallel Computing, Introduction to the Case-Study.

Abstract: In this lecture, I present the course, its goals, the textbook, etc... Then I present the case-study we will be using during the course. It is important to get familiar with it as early as possible.
Download the source here.

Reading: Chapter 1 and Sections 2.1.

Slides: Introduction to Parallel Computing, Model-Checker Case-Study, and Parallel Programming Platforms.

Exercises: During this first exercise session, you are expected to refresh your skills in C. Please look at these C introduction slides and this web page on Pointers and memory on your own before the lecture. Exercises:

This is the first half of assignment 1.

Remarks:

Lecture 2: Parallel Programming Platforms, The PRAM Model.

Abstract: I start the chapter on parallel programming platforms that will serve mostly as an introduction to parallelism from the hardware aspects. I introduce the architecture of an ideal parallel computer, known as the PRAM model. I use extra material from Sven Skyum to present Brent's scheduling principle and go through examples on sorting and merging.

Reading: Sections 2.2, 2.3, and 2.4.1. Sven Skyum's lecture notes
(typo p6, read "O(n/lg n) processors" instead of "O(nlg n) processors"
typo p9, read "Time O(log(n + m))" instead of "Time O(1)").

Slides: Parallel Programming Platforms and PRAM Model.

Exercises: Exercises 2.1 (design only, implementation is optional), 2.2, and 2.3. This completes assignment 1.
Remark: The exercises are not very precise and there are degrees of freedom. It is very good that you see these imprecisions. To solve them, you fill in the gaps with your own assumption, e.g., assume a[i] is one word etc... You may come up with different answers depending on your assumptions, which is fine.

Assignment 1: Exercises of lecture 1 and lecture 2. All exercises are compulsory unless stated otherwise. Deadline February 27th.

Lecture 3: Physical Organization of Parallel Platforms and Parallelizing the Model-Checker

Abstract: I treat the part on physical organization of parallel platforms and show you different ways to parallelize our little model-checker. From now on we'll alternate between theory and practice.

Reading: Sections 2.4.

Slides: Physical Organization of Parallel Platforms, Parallelizing the Model-Checker, and

Exercises:

Remarks: The exercises related to the case-study will be used for further assignments. Please do them carefully.

Lecture 4: Programming Shared Address Space Platforms and Help on the API

Abstract: I give you some help to use the API of the pthread library and I treat Pthreads.

Reading: Chapter 7.

Slides: Help on the API and Programming Shared Address Space Platforms.

Exercises:

Assignment 2: Exercises of lecture 3 and lecture 4. Deadline March 10th.

Remarks: The exercises related to the case-study will be used for further assignments. Please do them carefully. In particular, you will have to use the library.

Lecture 5: Communication Costs in Parallel Machines, Process-Processor Mapping, Preliminaries to Parallel Algorithm Design.

Abstract: I discuss different communication costs (message passing and shared adress space), the impact of process-processor mapping, and start on parallel algorithm design (decomposition techniques of apparently sequential algorithm into parallel algorithms).

Reading: Sections 2.5, 2.6, 2.7, and 3.1.

Slides: Communication Costs, Process-Processor Mapping, and Principles of Parallel Algorithm Design.

Assignment 3: Implement incrementally 4 of the 5 solutions presented in lecture 3.

Lecture 6: Decomposition Techniques and Tasks. Mapping Techniques for Load Balancing, Methods for Containing Interaction Overheads, Parallel Algorithm Models.

Abstract: I continue on parallel algorithm design, treating characteristics of tasks and their interactions and mapping techniques. The point is to use techniques to minimize interaction.

Reading: Chapter 3.

Slides: Principles of Parallel Algorithm Design and Principles of Parallel Algorithm Design (cont.).

Exercises: Continue on assignment 3.

Lecture 7: Programming Using the Message Passing Paradigm.

Abstract: I start on MPI.

Reading: Sections 6.1, 6.2, 6.3, 6.4, and 6.5.

Slides: MPI.

Exercises: Continue on assignment 3. Extra time granted: Deadline March 25th. The 24th is a holiday so you get until the 25th.

Remarks: The API of the library (utils.pthread.h) offers everything you could possibly need for the assignments. It does not mean that you must use everything. In particular, you can do assignment 3 without using the local_queue_t type and its shared version. This type is provided here for those of you who want a challenge and implement a multi-threaded solution with non-blocking calls. Sorry for the confusion if you felt that you had to use this type.

Lecture 8: MPI cont., MPI in our Model-checker, and API of the MPI library.

Abstract: I finish MPI and I discuss problems and solutions related to parallelizing our model-checker using MPI. This is to prepare assignment 5. I'll also give you some help on the API of the MPI library.

Reading: Chapter 6 and section 11.4.4.

Slides: MPI, MPI in our Model-Checker, and MPI API.

Exercises: 3.2, 3.7, and 3.21. [Optional: 2.24, 3.11, 3.12, 3.13]

Solutions: solutions for the optional exercises.

Lecture 9: Basic Communication Operations.

Abstract: I start chapter 4. It's about how to implement collective communication operations that we saw during the lectures on MPI. There are interesting algorithms for that.

Reading: Sections 4.1, 4.2, 4.3, and 4.4.

Slides: Basic Communication Operations.

Exercise: 4.5.

Assignment 4: Exercises of lectures 8 and 9. Deadline April 9th.

Lecture 10: Basic Communication Operations cont.

Abstract: I finish chapter 4 and I summarize and complete on thread synchronization.

Reading: Sections 4.5, 4.6, and 4.7. Tutorial page of LAM/MPI.

Slides: Basic Communication Operations and Thread Synchronization.

Assignment 5: This assignment is split on 3 exercise sessions (that do not necessarily map to the following 3 sections for the exercises). There is very little coding to be made but on the other side, you need to read and analyse quite some code. Questions:

Deadline April 30th.

Note: Progress is not implemented at this time. You should not add it. You can test MPI with the following hellompi simple program.

Lecture 11: Analytical Modeling of Parallel Programs.

Abstract: I treat chapter 5. This chapter looks scary but it's not! It's actually very interesting.

Reading: Chapter 5.

Slides: Analytical Modeling.

Exercises: Work on assignment 5.

Lecture 12: Sorting.

Abstract: I will discuss different issues in sorting on parallel computers, present some well-known (sequential) sorting algorithms and their parallel versions.

Reading: Chapter 9.

Slides: Sorting.

Exercises: Work on assignment 5.

Lecture 13: Dense Matrix Algorithms.

Abstract: I go through dense matrix algorithms for matrix*vector and matrix*matrix multiplications. I give the idea of parallel versions of Gauss' elimination algorithm.

Reading: Chapter 8.

Slides: Dense Matrix Algorithms.

Exercises: This exercise is not part of assignment 5 but you should try it anyway.

Lecture 14: Graph Algorithms.

Abstract: I treat of some parallel algorithms for dense graphs.

Reading: Sections 10.1 to 10.6.

Slides: Graph Algorithms.

Lecture 15: Guest Lecture by Gerd Behrmann

Abstract: I will talk about the last 2 exercises during the first 30 min and then Gerd will take over. Gerd will talk about the GRID and his work on a distributed file server that is needed for the famous LHC.

Slides: To appear.

Exercises: Finish your completions if any.