Description

Instructor:
Sanjay Rajopadhye
Office: 340 CS Building
Office Hours: T,Th 11-12
Email: cs575@cs.colostate.edu
GTA:
Nirmal Prajapati
Office: 335 CS Building
Office Hours: Th 8-9, Th 12-1
Email: cs575@cs.colostate.edu
Lecture Time and Place:
9:30-10:45, Tu, Th, CSB Room 325

This is a graduate level course on parallel computing with the objective to familiarize students with the fundamental concepts, techniques and tools of parallel computing. Participation in this course will enable you to better use parallel computing in your application area, and will prepare you to take advanced courses in more specific areas of parallel computing. The schedule tab contains the weekly schedule, links to lecture notes, quizzes, homework, etc. In addition, the actual discussions will be taking place on the Piazza, which many of us have found to be much more convenient than RamCT.

Prerequisites

In order to succeed in this course, the official prerequisites is CS 475. However, since this is a graduate class, and many students may have taken equivalent material in other underggraduate classes elsewhere, neither the registration system nor the instruction staff will enforce it. A second prerequisite is mathematical maturity, especially in analysis of algorithms and algorithmic complexity. At CSU this would be in the equivalent of a algorithms course like CS320. The first assignment is intended to be a review of prerequisites (it is due in week 3, which is after the add-drop deadline, but the first two weeks will give you ample opportunity to see if you cope with the material).

Textbook

Introduction to Parallel Computing, 2nd Edition Ananth Grama, Anshul Gupta, George Karypis,Vipin Kumar, The Addison Wesley Publishing Company, ISBN 0-201-64865-2

The schedule tab of this web site indicates each week's reading. Students are responsible for doing the assigned reading prior to the lecture in which the material is to be covered.

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

On campus Quizzes are pop quizzes. For online students, they are done online, within RamCT. To provide the same effect of a pop quiz, they will be announced in a limited window. In RamCT they may be taken twice, in which case, the grade is the average of the two grades. For all students, the worst quiz result is dropped. The quizzes are there to help you study.

Grading

Here are the formally graded elements of the course and associated weighting:

Activity Weight
Assignments (5) 30 %
Weekly discussions (online) 10 %
Quizzes 10 %
Midtermexam (in-class or take home, instructor's choice) 25%
Final Exam 25 %

Semester grades are determined by the weighted sum of points earned in each of these areas. A subjective curve (set by the instructor) is used to map points onto grades. Typically, the curve is set such that the class mean gets an B, one standard deviation above the mean is an A, one deviation below is a C, and so forth. However, the instructor retains the right to move the curve either direction. If the entire class is strong, the mean might be better than a B. Conversely, if the class as a whole is weak, the mean might be below a B

Professional Conduct

Exams and projects will be done individually and grades assigned on an individual basis. Further, students not already familiar with the CSU Honor Pledge should review this clear and simple pledge and always adhere to it.

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. Additionally, you are computing professionals. You should be familiar with the code of conduct for the primary professional society, ACM. You can read the ACM Code of Conduct HERE.

We work to maintain an environment supportive of learning in the classroom and laboratory. Towards that end, we require that you be courteous to and respectful of your fellow participants (i.e., classmates, instructors, GTAs and any tutors). In particular:

  • Please turn off the ring on your cell phone. If you are expecting an emergency call, sit near the door and slide out discretely to take it.
  • In class use of electronic devices in general, and laptops specifically, is permitted as a courtesy so that you may better participate and learn. If at any time the instructor judges that an electronic device is becoming a distraction the student may be asked to to turn it off and put it away.

Late and Makeup Policy

Midterm and Finals: Make-up exams are only given for extraordinary circumstances (e.g., illness, family emergency). Students must consult with the instructor as soon as possible, preferably before the start of the exam. Course examination dates are listed in the syllabus; be aware of them and plan accordingly.

Assignments: All assignments are to be submitted electronically through the Checkin tab. Specifics will be included in each assignment. Always check the assignment page for due dates. No late assignments will be accepted. Electronic submission is closed at the deadline when the assignment is due; students not having submitted programs receive an automatic zero on the assignment.

Any in-class midterms and the final exam will be held in the same classroom as regular lectures. While no change to the midterm dates is anticipated, the instructor reserves the right to change these dates with a weeks notice.