Instructor: Ajay Kshemkalyani

Office: 915 SEO (Office Hours: T 5:00-5:50 PM & by appt.)
Email: ajay@uic.edu

Grader: no grader
Office: TBA
Email: TBA

Prerequisites: CS 401 and CS/ECE 466 or equivalents, or permission of instructor

Required Textbooks/ Sources:

1. Main text: Introduction to Parallel Computing, by V. Kumar, A. Grama, A. Gupta, G. Karypis, Benjamin-Cummins, 2nd edition, 2003.
   
2. Selection of papers to be studied in class.

1. An Overview Chart
2. UIC's EXTREME cluster and a Knowledge base (how to login, run jobs, list of FAQs, etc.) and Slides from ACER
3. MPI tutorial at Argonne National Lab
4. Interconnection Networks
5. Amdahl's Law
6. The Travelling Salesman Problem
   • TSP on Wiki
   • TSPLIB library
   • J. N. Magee, S. C. Cheung, Parallel algorithm design for workstation clusters, Software: Practice and Experience, Volume 21, Issue 3 , Pages 235 - 250.
   • Cesari G., Divide and conquer strategies for parallel TSP heuristics, Computers and Operations Research, Volume 23, Number 7, July 1996 , pp. 681-694(14) (Elsevier)
7. Overhead slides used in class.
   • Models: Chapter 2 (revised slides)
   • Principles of Designing Parallel Algorithms: Use Professor George Karypis's PDF lecture slides "GK lecture slides", for Chapter 3, Principles of Parallel Algorithms, from here and slides for Gaussian Elimination and LU Decomposition examples
   • Basic Communication operations: Chapter 3 (revised slides)
   • Performance and Scalability: Chapter 5 (revised slides)
   • Sorting: Chapter 9 (revised slides)
   • Graph Problems (Part 1): Chapter 10 (revised slides), Graph Problems (Part 2): Chapter 10 (revised slides), and Luby's MIS algorithm
   • Discrete Optimization: Chapter 11 (revised slides)
   • Dynamic Programming
   • Distributed Shared Memory
8. The best and the fastest supercomputers! Study this site including the report on HPC benchmarks.
9. Distributed Shared memory Chapter

Supplemental References and sources:

1. Introduction to Parallel Algorithms and Architectures, by Thomas Leighton, Morgan Kaufman, latest edition.
   Chapters 1.1, 1.5, 1.6, 1.7, 2.1, 2.2, 2.7, 3.1 - 3.7
2. Parallel Computation : Models and Methods, by Selim G. Akl / Prentice Hall / April 1997
3. Highly Parallel Computing (The Benjamin/Cummings Series in Computer Science and Engineering) by George S. Almasi, Allan Gottlieb / Addison-Wesley Pub Co / February 1994

Course Description:

1. Various parallel topologies (e.g., hypercube, torus) and algorithms on such topologies
2. Parallel algorithms for counting, sorting, routing, and graphs
3. Parallel alogrithms for NP-complete problems
4. Parallel matrix multiplication, Fast Fourier Transforms
5. Shared memory parallel systems
6. Programming using MPI (Message Passing Interface); case studies of systems/platforms
7. Special topics

Grading: Grading will be on the curve.
The following is only a tentative breakup of the evaluation scheme and is subject to (reasonable) changes as the course progresses.
Also depends on the class size.

• Midterm 1 (25%)
• Midterm 2 (25%)
• Programming assignments (40%)
• Class presentation (10%)

Course progress chart (tentative):

• Week 1: Introduction; processors; classification; platforms (Ch 1 + TOP500 + extra notes)
• Week 2: PRAM model; Architectures (Ch 2)
• Week 3: Basic Communication Operations (Ch 4)
• Week 4: Basic Communication Operations (Ch 4), Lab 1 due Thu 27 Feb at 2:00pm in class, (postponed to March 3 in classs)
  (Guest lecture by Greg Cross from ACER on Feb 6); Programming using MPI (self-study) (Ch 6); Principles of Parallel Program Design (Ch 3)
• Week 5: Performance and Scalability (Ch 5)
• Week 6: Parallel sorting (Ch 9)
  Feb 20: Midterm 1. Syllabus: Chapters 1-6 + all material covered in class, such as top500 web site, Interconnection Networks by Prof. Wilhelm, etc.
• Week 7: Parallel sorting (Ch 9), Parallel graph algorithms (Ch 10) Lab 2 due Thu March 19 at 2:00pm in class
• Week 8: Parallel discrete optimization problems (Ch 11)
• Week 9: Shared memory
• Week 10:
  Mar 17: Class cancelled due to extended Spring Break
  Mar 19: Class cancelled due to extended Spring Break
  
• Week 11:
  Mar 31: Automatic parallelization and vector processors: Yinbin Ma
  Lab 3 due Thu April 23 at 2:00pm in class
  Apr 2: Multicore processors: Jasmine Espindola
• Week 12:
  Apr 7: Programming GPGPUs: Jason Nardoni
  Apr 9: OpenMP and Posix threads: Smit Patel
• Week 13:
  Apr 14: Midterm 2. Syllabus: Chapters 1-6, 9-11
  Midterm 2 here, upload deadline in Gradescope is 3:30pm
  Apr 16: Static and Dynamic Data Race Detection for Multithreaded Environmentss: Yaozong Shen
  Lab 4 due May 7 at 2:00pm
• Week 14:
  Apr 21: QCUs and Quantum Computing I: Mathematical Foundations: Yuxin Qi
  Apr 23: QCUs and Quantum Computing II: Systems: Alexis Lopez
• Week 15:
  Apr 28: Hadoop and Mapreduce: Muhammad Khan
  Apr 30: Cloud computing: Dhruv Devani
• May 6, 3:30-4:30pm: Multicore processors: Jasmine Espindola