- Instructor:
- Sanjay Rajopadhye

Office: 340 CS Building

Office Hours: see Sanjay's hope page

Email: cs575@cs.colostate.edu - GTA:
- Prashant Mehta

Office: 376 CS Building

Office Hours: Monday 1:00-3:00 (Lab 120)

Email: cs575@cs.colostate.edu

- Lecture Time and Place:
- 3:30-4: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. Preerquisites are an undergraduate course in parallel programming (equivalent of CS 475) and amiliarity with analysis of algorithms and complexity theory (equivalent of CS 320, or CS 420). 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.

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).

**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 **

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.

**Introduction**- Need for Parallel Computing
- Scope of Parallel Computing
- Issues in Parallel Computing

**Models of Parallel Computing**- Taxonomy of Parallel Architectures
- Dynamic Interconnection Networks
- Static Interconnection Networks
- Message Transfer
- Reduction, Parallel Prefix
- GPU thread model

**Performance Modelling**- Metrics
- Granularity
- Scalability
- Overhead
- Isoefficiency

**Matrix Algorithms**- Matrix Partitioning
- Matrix Transposition
- Matrix Vector Multiply
- Matrix Multiply
- CUDA, vector add, matrix multiply, sequence alignment
- Linear Equations
- LU(P) Decomposition

**Searching and Optimization**- The knapsack problem
- Branch and Bound
- Dynamic Programming

**Sorting**- Types of sorters
- Sorting networks
- Radix / Bucket sorts

**Graph algorithms**- Minimum Spanning Tree
- Single Source Shortest Paths
- All Pairs Shortest Paths

**Fast Fourier Transforms**- Fourier Series, basis functions, Euler
- Discrete and Fast Fourier Transforms
- Convolution, roots of unity, divide and conquer
- Evaluation and Interpolation
- Recursive, bitreversal, iterative Cooley-Tukey FFT
- Pease FFT, locality

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.

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 Project+ Poster | 25 % |

Semester grades are determined by the weighted sum of points earned in each of these areas. The standard grading cutoffs (70-8-90%) will be default for C, B and A grades respectively. However, a subjective curve (set by the instructor) may be 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.

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.

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.