Instructor: Ajay Kshemkalyani

Office: 915 SEO (Office Hours: T 3:40-4:30 PM & by appt.)
Phone: 355-1309
Email: ajay@uic.edu

Grader: Riyansh Karani
Office: SEO 1337 (Office Hours: M 11-12:30pm; W 10:30-12pm)
Email: rkaran3@uic.edu

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 new EXTREME cluster and a list of FAQs and Slides from ACER
3. The class share for CS/ECE 566 this semester is /export/share/classes/cs-ece566 .
   The tutorial slideshow and MPI demonstration are available in: /export/share/classes/cs-ece566/MPIsample
4. Technical documentation, MPI instructions
5. MPI tutorial at Argonne National Lab
6. Interconnection Networks
7. Amdahl's Law
8. 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)
9. 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
10. The best and the fastest supercomputers! Study this site including the report on HPC benchmarks.
11. 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); Lab 1 due Oct 2 at 5:00pm
• Week 4: (Guest lecture by Greg Cross from ACCC); 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); Parallel graph algorithms (Ch 10); Lab 2 due Oct 25 at 5:00pm;
  Oct 4: 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 graph algorithms (Ch 10); 0/1-ILP, TSP. Parallel discrete optimization problems (Ch 11)
• Week 8: Parallel discrete optimization problems (Ch 11)
• Week 9: Shared memory
  Lab 3 due Nov 13 at 5:00pm
  
• Week 10:
  Oct 30: Midterm 2. Syllabus: Chapters 1-6, 9-11 + distributed shared memory chapter (Chapter 6.1-6.3.2) & distributed shared memory slides (1-24)
  Nov 1: Automatic parallelization and vector processors: Likith
• Week 11:
  Nov 6: Multicore processors: Ruy
  Nov 8: Programming GPGPUs: Manisha, Dipika
• Week 12:
  Lab 4 due Dec 3 at 5:00pm
  Nov 13: OpenMP and Posix threads: Ye, Yun
  Nov 15: Transactional memory for multithreaded environments: Jatinder, Srividyaa
• Week 13:
  Nov 20: Static and Dynamic Data Race Detection for Multithreaded Environmentss: Sanamdeep, Chirag
  Nov 22: Thanksgiving
• Week 14:
  Nov 27: QCUs and Quantum Computing I: Mathematical Foundations: Marco, Pistilli
  Nov 29: QCUs and Quantum Computing II: Systems: Samuele, Anthony
• Week 15:
  Dec 4: Hadoop and Mapreduce: Zhe, Bowen
  Dec 6: Cloud computing: Gabrielle, Mike