Cpr E 426/526: Introduction to Parallel Algorithms and Programming

Cpr E 426/526: Introduction to Parallel Algorithms and Programming
Fall 2009

Tue, Thu 9.30am - 10.50am
Howe Hall Room 1304

Syllabus	Staff	Schedule	Homework	Assignments	Exams
Handouts	Textbooks	Grading	Course Policies	Links	WebCT

Course Staff

Instructor	Teaching Assistant
Suresh Kothari	Gui Kang
kothari@iastate.edu	kgui@iastate.edu
Room 3132 Coover	Room: TBA
Phone: (515) 294-7212
Office Hours: Wednesday 1:30 to 2:30 and Thursday 11 to 12	Office Hours: TBA

Course Description

This course will provide an introduction to parallel algorithms and parallel programming. The course emphasises both algorithm design techniques as well as the implementation of parallel programs. Exposure to parallel programming is provided through programming assignments using MPI. Programming assignments will be done on the Parallel Cluster at AIT, as well as the BlueGene supercomputer at ISU.

Tentative list of topics:

Principles and Algorithms:
- Models of Parallel Computation
- Performance Measures, Speedup, Efficiency
- Parallel Prefix and Applications
- Sorting and Selection
- Matrix Algorithms
- Fast Fourier Transform
- Embeddings
Parallel Programming:
- MPI (Message Passing Interface): Writing and Executing MPI programs, point-to-point communication, collective communication, communicators, topologies

Textbooks

The following text is required, and is available at the bookstore: Parallel Programming with MPI by Peter S. Pacheco.
The following text is a useful reference: "Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes" by F. T. Leighton

Grading

The grading will be based on quizzes, homework, programming assignments and other (class participation, exemplary work etc.) .

Quizzes: 55 % (On Thursdays, 15-20 minutes at the end of the class. Any changes will be announced in the class)
Homework 15%
Programming Projects: 25 %
Other: 5 %

(tentative) Schedule

Day	Topic	Reading/Homework
Tue, Aug 25	First Class, Introduction
Thu, Aug 27	Applications, Models, and Algorithms (PDF)
Tue, Sep 1	Profiling Performance & Source-level Optimizations (PDF)
Thu, Sep 3	Examples of an Important Pattern of Computations (PDF)
Tue, Sep 8	Parallel Prefix Algorithm & its Performance Estimation
Thu, Sep 10	Applications of Parallel Prefix Algorithm	Parallel Computing Basics
Tue, Sep 15	SPMD Programming & Intro to MPI Quiz1 due in class	Lect07 & Ch4-Code
Thu, Sep 17	Quiz 2: parallel prefix algorithm & applications	Lect08
Tue, Sep 22	Discussion of Quiz 2 Intro to parallel matrix multiplication Homework 1 Assigned (due Sep 29) - Use latex or other word processor of your choice - submit PDF	Lect09 HW-1 PDF & Tex
Thu, Sep 24	Qui 3: will be based on lectures 7, 8 & 9 Lecture 10: 2D Matrix Multiplication Algorithms	Lect10 Quiz 3 Solution
Tue, Sep 29	Lecture 11: Guest lecture on how to compile, debug, and run parallel programs 2D matrix multiply parallel algorithms represented by PLACE and STEP Program I Assignment - Matrix Multiplication Due Oct 15	Lect11: PLACE & STEP problems Program Assignment I
Thu, Oct 1	Quiz 4: will be based on 2-D matrix multiplication - PLACE STEP
Tue, Oct 6
Thu, Oct 8	Quiz 4:
Tue, Oct 13	MPI Collective Communication Quiz 5 will be on the three code examples	Slides by Dr. Tirthapura Overview Code: Example 1 - create groups Example 2 - create 2-D grid and 1-D sub-grids Example 3 - Fox algorithm
Thu, Oct 15	Program I Due ( hard copy in class and zip file to TA -see the problem statement for submission details) Derived Datatype Quiz 5
Tue, Oct 20	Derived Datatype Lecture Notes (PDF) Read Chapter 6	Code: Example 1 - constructing datatype Example 2 - sending column Example 3 - sending column to row Example 4 - sending upper triangle Example 5 - sending sparse row
Thu, Oct 22	Parallel Gaussian Elimination Quiz 6 will be on derived datatype	Gaussian Elimination Algorithm (PDF)
Tue, Oct 27	Discussion of load balance of parallel 1-D and 2-D BLOCK and SCATTER decomposition	Homework 2: computing the load balance of parallel Gaussian Elimination algorithms - Due Nov 3 (PDF)
Thu, Oct 29	Performance Analysis of Parallel Computing - going beyond misguided dogmas and performance laws
Tue, Nov 3	Homework 2 is due in class

Homeworks

Assignments

Exams

Handouts

Lecture Notes

Parallel Computing Basics
Sample Sort
Embeddings
Fast Fourier Transform

Course Policies

Disability

If you have a documented disability and anticipate needing accommodations in this course, please make arrangements to meet with me soon. Please request that a Disability Resources staff send a SAAR form verifying your disability and specifying the accommodations you will need.

Academic Integrity

All your work should be done individually unless otherwise specified. You are not allowed to use work done by others, or obtain the answers directly in any form (such as from the web). If you have any questions about what is allowed/not, please contact the instructor, and please refer to the university policies on academic dishonesty .