Department of Computer Science

Graduate Program

521: Parallel Algorithms and Architectures (term1)

(September 1, 2009)


Instructor: Alan Wagner (wagner@cs.ubc.ca, room 321 ICICS/CS)

Prerequisites: Graduate standing or consent of instructor, students should have taken an analysis of algorithms course and have experience with Java, C and Unix.

Term: Fall 2009

Time: M W 3:30 - 5:00 (First class September 9th)

Location: ICCS 238

Course Description

The main objective of the course is to have you "think parallel". We will look at the design of algorithms, the basic models of computation, and different types of architectures for parallel computing. The focus of the course is on basic questions about how to evaluate parallel programs, strategies for parallelizing programs and tools available for programming.  There is a heavy programming component to the course, which will be message-passing using MPI.  We do not cover shared memory programming or GPU programming in any detail. 

Some of the material will come from the following textbook:

Wilkinson B., Allen M., "Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers", Prentice-Hall, 2005 (2nd Edition)

The following book gives an excellent introduction to MPI.  The reading room has a copy, which I will put on reserve.  There are a number of tutorials online as well.  As a start-up exercise you may want to try running the MPI equivalent to the “Hello World” program.

P. Pacheco. Parallel Programming with MPI. Morgan Kaufmann Publishers, 1996.

Evaluation

The evaluation will be based on one programming assignment and a project spread out into several phases.   The programming assignment will be to a relatively simple MPI program.  The project will be group based (2 maximum 3 to a group) and the objective will be to design a tutorial for one of the programming motifs as described in the paper “Landscape of Parallel Computing Research: A view from Berkeley” (http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.html).  There are thirteen in total: Structured Grid Computation, Unstructured Grid Computation, Dense Matrix Operations, Sparse Matrix Operations, Spectral Methods (FFT), Particle methods (N-body), Finite State Machines (CSP), Combinational logic (circuits), Graph Traversal, Search, Dynamic Programming, Graphical Models (Bayesian networks), Map-Reduce. 

The project will have three parts (a) Initial description of the motif, resource materials, research materials, (b) meeting with me outlining the tutorial (including demos) (c) In-class presentation along with a short demo.  Each assignment and project part is worth approximately 25% of the course.

Please feel free to contact me if you have any questions.