Topics

1. Introduction
   1. Need for Parallel Computing
   2. Scope of Parallel Computing
   3. Issues in Parallel Computing
2. Models of Parallel Computing
   1. Taxonomy of Parallel Architectures
   2. Dynamic Interconnection Networks
   3. Static Interconnection Networks
   4. Message Transfer
   5. Reduction, Parallel Prefix
   6. GPU thread model
3. Performance Modelling
   1. Metrics
   2. Granularity
   3. Scalability
   4. Overhead
   5. Isoefficiency
4. Matrix Algorithms
   1. Matrix Partitioning
   2. Matrix Transposition
   3. Matrix Vector Multiply
   4. Matrix Multiply
   5. CUDA, vector add, matrix multiply, sequence alignment
   6. Linear Equations
   7. LU(P) Decomposition
5. Searching and Optimization
   1. The knapsack problem
   2. Branch and Bound
   3. Dynamic Programming
6. Sorting
   1. Types of sorters
   2. Sorting networks
   3. Radix / Bucket sorts
7. Graph algorithms
   1. Minimum Spanning Tree
   2. Single Source Shortest Paths
   3. All Pairs Shortest Paths
8. Fast Fourier Transforms
   1. Fourier Series, basis functions, Euler
   2. Discrete and Fast Fourier Transforms
   3. Convolution, roots of unity, divide and conquer
   4. Evaluation and Interpolation
   5. Recursive, bitreversal, iterative Cooley-Tukey FFT
   6. Pease FFT, locality

Quizzes and Discussions

• On campus Quizzes are pop quizzes.
  Distance learning quizzes are to be done after study to check whether the material is comprehended. They are to be done before work on discussions and assignments is started (when available). Quizzes are available on RamCT in the indicated period and can be taken twice. If taken twice, the grade is the average of the two grades. The worst quiz result is dropped. The quizzes are there to help you study.
• On campus discussions are spontaneous. Distance learning discussions are done more formally in discussion groups, so that students can extend their understanding by learning from each other. Discussion 0 is there to create the discussion groups.

On line Discussion Instructions

Each student submits an initial solution to his/her discussion group. This is the starting point for the discussions. All students of that discussion group participate in discussing the pros and cons of each solution. They must then arrive at a solution agreed upon by the whole group.

Each group selects a representative to write and submit a consensus report. The consensus report can be a text, doc or PDF file. It must contain the following information:

1. Dicusssion number/topic
2. Discussion group name
3. Names of people who participated in the discussion.
4. Name of the representative
5. Actual report: This must contain the solution agreed upon by the whole discussion group. If you submit only the final solution (and it is incorrect), you will not get any partial credit. If you submit the steps followed to arrive at the solution, you will get partial credit depending on where the actual mistake occured.

The campus course is similarly structured, with the difference that discussions and quizzes happen spontaneously in class. The distance learning equivalents are an attempt to create a similar situation on line.

Study textbook chapters from Introduction to Parallel Computing, 2^nd Edition Ananth Grama, Anshul Gupta, George Karypis,Vipin Kumar, The Addison Wesley Publishing Company, ISBN 0-201-64865-2 , lecture notes (in PowerPoint or PDF), and video taped lectures. The lecture notes highlight and extend book material and indicate which parts of the book are most important. As pointed out on the front page, the notes are brief and indicate what you need to study in more detail.

Assignments and Exams are done individually. Assignments will be due by the indicated date and time. Assignments are submittede via RamCT.

For the distance learners, both midterm and final Exams are taken in the form of online quizzes, each of which can be taken only once in the designated week. For the on campus students, the tests are in class.

The schedule is subject to change. We will be studying GPUs and GPU (CUDA) programming.

Checking Grades

Your grades will be posted on RamCT.

Grading

The grade is based on

• lab/homework assignments   (30%)
• discussion assignments (on campus: audience participation)   (10%)
• online and on campus quizzes   (10%)
• a mid-term exam   (25%)
• a final exam   (25%)

Policy

• Midterm and Finals: For on campus students these exams occur in class. For distance learners these exams are taken in the form of on line quizzes. Exams can only be taken once. Make-up exams are only given for extraordinary circumstances (e.g., illness).
• Quizzes: No make-ups will be given for missed quizzes.

Professional Conduct

All students are expected to conduct themselves professionally. We (the instructor and the GTA) assume you are familiar with the policies in the student information sheet for the department. The guidelines outlined in these documents will be followed in this course.

Copyright © 2002-2015: Colorado State University. All rights reserved.