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.
   All Chapters except Chapter 7.
2. Selection of papers to be studied in class.

1. An Overview Chart
2. The Argo Beowulf Cluster at UIC, and MPICH2 and How to use MPICH on ARGO and troubleshooting and to know which nodes are reserved on which queues
3. MPI tutorial at Argonne National Lab
4. Interconnection Networks
5. The Travelling Salesman Problem
   • TSP on Wiki
   • Repository and Data Sets
   • 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)
6. Overhead slides used in class.
   • Models
   • 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 - 1
   • Basic Communication operations - 2
   • Performance and Scalability
   • Sorting
   • Graph Problems and Luby's MIS algorithm
   • Discrete Optimization
   • Dynamic Programming
   • Distributed Shared Memory
7. The best and the fastest supercomputers! Study this site including the report on HPC benchmarks.
8. 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 (25%)
• Exam (30%)
• MPI programming assignments (35%)
• Class presentation (10%)

Course progress chart:

• Week 1 (Aug 27 -): Introduction; processors; classification; platforms (Ch 1 + TOP500 + extra notes)
• Week 2 (Sep 3 -): PRAM model; Architectures (Ch 2)
• Week 3 (Sep 10 -): Basic Communication Operations (Ch 4)
• Week 4 (Sep 17 -): Basic Communication Operations (Ch 4), Lab 1 assigned, due Oct 9
• Week 5 (Sep 24 -): Principles of Parallel Program Design (Ch 3), Introduction to MPI
• Week 6 (Oct 1 -): Performance and Scalability (Ch 5), Lab 2 assigned, due Oct 25
• Week 7 (Oct 8 -): Parallel sorting
• Week 8 (Oct 15 -): Parallel graph algorithms
• Week 9 (Oct 22 -): 0/1-ILP, Parallel discrete optimization problems, Parallel matrix multiplication (self-study), Lab 3 assigned, due Nov 15 (extended to Nov 20)
• Week 10 (Oct 29 -): Parallelizing dynamic programming solutions, TSP; Nov 1: Midterm. Syllabus: everything covered up to Oct 11 (till end of Parallel Sorting).
• Week 11 (Nov 5 -):
  Nov 6: Analysis of supercomputer design and cluster design: Alessandro Vallero and Alberto Scolari
  Nov 8: Automatic parallelization/Vector Processors: Ganesh Chandrasekaran and Eman Aldakheel
• Week 12 (Nov 12 -):
  Nov 13: Multicore processors: Archana Subramanian and Nikhar Farha
  Nov 15: Programming GPGPUs: Viktor Mateevitsi and Tomas Gerlich; Parallel TSP, Programming Lab 4 assigned, due Dec 4 at 3:30pm
  
• Week 13 (Nov 19 -):
  Nov 20: OpenMP and Posix threads (shared memory paradigm): James Baxter Thorne and Qun Li
  Nov 22 (Thanksgiving)
• Week 14 (Nov 26 -):
  Nov 27: Hadoop and Mapreduce: Swati Gore
  Nov 29: Transactional memory for multithreaded environments: Jamar Drue and Brian Mykietka
  
• Week 15 (Dec 3 -):
  Dec 4: Cloud Computing: Harshavardhan Thirividi and Venkgada Rangaraju
• 1:00-3:00 p.m. Friday, December 14: Final. Syllabus: everything in class during the semester + links on this web site + presentations, i.e., Chapters 1,2,3,4,5, (6 is implicitly there due to MPI), 9,10,11,12 + the links from the class web site + presentations