Parallel Programming (3:1)
Instructor: Sathish Vadhiyar
Meeting Hours: 14:0015:30 ; Tuesday, Thursday; Room 202, SERC
The objective of this course is to give you some level of confidence in parallel programming techniques, algorithms and tools. At the end of the course, you would (we hope) be in a position to apply parallelization to your project areas and beyond, and to explore new avenues of research in the area of parallel programming. The course covers parallel programming tools, constructs, models, algorithms, parallel matrix computations, parallel programming optimizations, scientific applications and parallel system software. MPI, OpenMP and CUDA will be covered.
Class
Sessionals
2 MidTerm Exams (February 14, March 16)  30
Assignments (2. Due: February 4, March 2)  20
Terminal
Assignment (1. Due: March 30)  10
Final project (Proposal: March 9, Final presentation: April 18, Final report: April 19)  20
Final Exam (April 26)  20
Topic  Reading Material 












Important  Look at the Rules section that contains important information on assignment deadlines, policies on plagiarism.
Assignments
Assignment 1  Collective communications and coalesced access
Assignment 2  Sample Sort on GPU
Assignment 3  MPI PageRank
Final Project
The final project has to clearly demonstrate the uniqueness of your work over existing work and show adequate performance improvements. You can work in a team of max 2 members. It can be in
parallelizing well known algorithms or problems. Examples:
hybrid executions on both CPU and GPU cores.
graph algorithms  spanning trees, shortest paths, satisfiability, mesh generation or refinement (e.g., Delaunay)
sorting, searching
clustering algorithms
parallelization of fundamental algorithms you would encounter in an algorithm book. e.g.,
parallelizing numerical methods, Examples:
Dense martrix or sparse matrix computations. e.g., Cholesky, QR, Inverse, SVD, conjugate gradient etc.
Transforms (FFT, wavelet etc.)
Any numerical method you would encounter in matrix/numerical methods book. e.g.,
System software. Examples:
Techniques for scheduling or mapping parallel tasks to processors to achieve least makespan or throughput
Load balancing techniques for irregular computations
Automatic techniques for splitting tasks among GPU and CPU cores.
Automatic data management techniques for GPU cores.
Proposing genetic programming abstractions
Fault tolerance
Sample Projects from Previous Years
Finding maximum clique in hybrid system  pdf
Parallel hybrid implementation of SVM  pdf
GPU TSP  pdf
GPU implementation of implicit RungeKutta methods  pdf
Parallel implementation of shared nearest neighbor clustering algorithm  pdf
Hybrid implementation of alternate least square algorithm  pdf
Approximate knearest neighbor search  pdf
Incremental Delaunay triangulation  pdf
kmaximum subarray problem  pdf
Scale Invariant Feature Transform (SIFT)  pdf
AKS algorithm for primality proving  pdf
Betweenness centrality  pdf
Important Assignment Notes
EthicsAll assignments will be evaluated for a maximum of 10. There will be a penalty of 1 for every additional day taken for submission after the assignment due date.
Thus, you will have to be judicious regarding deciding when to submit your assignments.
Example
Suppose you have completed 1/2 of the assignment by the due date.
Scenario 1:
You think that it will take another 1 day to finish 3/4 of the assignment. In this scenario, if you submit by the due date, you will get a maximum score of 5 and if you submit a day after, you will get a maximum score of 6.5 (=7.51, 1 for the extra day). Thus, you will get better score if you take an extra day, finish 3/4 of the assignment and then submit.
Scenario 2:
You think that it will take another 3 days to finish 3/4 of the assignment. In this scenario, if you submit by the due date, you will get a maximum score of 5 and if you submit 3 days after, you will get a maximum score of 4.5 (=7.53, 3 for the three extra days). Thus, you will get better score if you submit your assignment that is 1/2 complete by the due date than submit the assignment that will be 3/4 complete after 3 days.