Introduction to Parallel Algorithms and Programming

CSE 40833/60833 - Fall 2009

Instructor

Scott Emrich
Office: 351 Fitzpatrick Hall
Phone: (574)631-0353; E-mail: semrich at nd.edu
Office hours: Tues, 4-5:30pm; Wed 10:30-noon and by appointment

Teaching Assistant

Hoang Bui
Office: 222 Cushing Hall
Phone: (574)631-8854; E-mail: hbui at nd.edu
Office hours: Wed 4-5 pm; Thurs 10:30-11:30 am

Overview

This course will provide a comprehensive introduction to parallel algorithms and parallel programming. Emphasis will be on both algorithmic techniques and parallel programming using MPI. Lecture topics will be: models of parallel computation, performance measures, basic parallel constructs and communication primitives, and parallel algorithms for selected problems including sorting. Approximately 40% of the course will be seminar-style. Programming assignments and a research-oriented final project will be done on a 22 node partition of a campus computing cluster.

Text, reading and syllabus

Parallel Programming with MPI by Peter S. Pacheco

Chapters by Dr. Srinivas Aluru (Iowa State)

Parallel fundamentals
Parallel models
Embeddings
Discrete FFT

The syllabus can be found here

Announcements

MPI pointers gone over 11/3 have been posted here
The second programming assignment has been emailed early and posted here.
Solutions to the second homework have been posted here.
Solutions to the first homework have been reposted here.

Schedule

Date	Topic	Homework	Notes
08/25/2008	Introductions		PDF
08/27/2008	Basics		PDF
09/01/2008	Parallel models	HW # 1 out	PDF
09/03/2008	Hypercubes		PDF
09/08/2008	Intro to MPI, communication	Prog. Assn. # 1 out	MPI notes PDF
09/10/2008	Parallel prefix	HW #1 due	PDF
09/15/2008	Applications of parallel prefix	HW #2 out	PDF
09/17/2008	Embeddings of meshes and tori		PDF
09/22/2008	Parallel sorting: Bitonic merge and sample sort		PDF
09/24/2008	Guest lecture: Scientific portals	HW # 2 due
09/29/2008	Collective communication; sample sort	HW #3 out	PDF
10/01/2008	Matrix multiply; intro to FFT		PDF
10/06/2008	Finish FFT; review	Prog. Assn. # 1 due	PDF
10/08/2008	In-class midterm	HW #3 due
10/13/2008	Paper discussion #1		PDF
10/15/2008	Paper discussion #2		PDF
Midterm Break!
10/27/2008	GPUs (Prof. Kogge)	Prog. Assn. # 2 out	Reference material Lectures
10/29/2008	CUDA (Prof. Kogge)		Material for lecture
11/03/2008	Paper discussion #3
11/05/2008	finish GPUs (Prof. Kogge)
11/10/2008	Guest lecture (Condor/Abstrations)
11/12/2008	CRC Guest lecture (Dr. Paul Brenner)
11/17/2008	Projects / homework	Prog. Assn. # 2 due Prog. Assn. # 3 out
11/19/2008	Paper discussion #4
11/24/2008	Paper discussion #5
Happy Thanksgiving!
12/01/2008	Paper discussion #6
12/03/2008	Paper discussion #7
12/08/2008	Project presentations
12/10/2008	Project presentations	Project due Prog. Assn. # 3 due

Academic dishonesty

All are required to abide by the CSE and University honor code. Discussions are encouraged, but all answers/programs must be written/developed individually. Final projects may be performed in groups of up to three students if the permission of the instructor is obtained.