CS435 / CS635 - Parallel Scientific Computing: Models, Algorithms and Implementation


University of Western Ontario
Computer Science Department


Date: September 7, 2009

Current hardware improvements have focused on increasing the number of computations that can be performed in parallel rather than on increasing clock speed alone. This change has brought multi-core workstations to the desktop, expanding interest in parallel algorithms and software capable of exploiting these computing resources.

The aim of the course is to introduce you to the art of analyzing and designing parallel algorithms. The following concepts will guide our quest for high performance: finding parallelism, scalability, granularity, locality, synchronization, scheduling and load balance.

Out of the course, you are anticipated to have an in depth understanding of some important parallel machine models, parallel complexity theory, fundamental parallel algorithms (for sorting, linear algebra, FFT) and parallel programming environments and tools such as MPI, OpenMP, Cilk, Kaapi, UPC, Linpack.

Prerequisites.
CS 210a/b, 211a/b, 305a/b. A good familiarity with linear algebra and complexity analysis of algorithms is recommended.
Outlines.
This presents the contents of the course, its assignments, quizzes and projects. outline.html
Lectures (tentative schedule).
Week Jan. 7-13 Overview of the course
  Performance and scalability of parallel algorithms
Week Jan. 14-20 Parallel machine model
Week Jan. 21-27 Parallel Complexity Theory (I)
Week Jan. 28-3 Parallel Complexity Theory (II)
Week Feb. 4-10 Parallel Sorting
Week Feb. 18-24 Parallel Matrix Operations
Week Mar. 3-9 Solving systems of linear equations in parallel
Week Mar. 3-9 Parallel programming environments (I)
Week Mar. 10-16 Scheduling, load balancing (I)
Week Mar 17-23 Scheduling, load balancing (II)
Week Mar 24-30 Code optimization for parallelism and locality
Week Mar 31-6 Parallel programming environments (II)
Week Apr. 7-13 Project presentations
Student Evaluation.
The course is very oriented toward assignments and projects. Assignments and projects constitute 40% and 40% of the course mark, respectively. There is no midterm examination and no final examination. However, there will be at least four quizzes. Quizzes constitute 20% of the course mark.
Assignments and projects for Winter 2008.
Assignment 1 (compressed postscript). Assignment 1 (html pages). Posted Feb. 7 Due Feb. 21  
Software and Courses.
These are links to some books and software related to the course.
Conferences.
Papers on Parallel Scientific Computing.