Instructor: Ajay Kshemkalyani

Office: 915 SEO (Office Hours: T,R 1:00-1:45PM & by appt.)
Phone: 355-1309
Email: ajay@uic.edu

Grader: Xiuyan (Kevin) Zhang
Office: 1333 SEO (Office Hours: F 11am-12noon & by appt.)
Email: xzhang87@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 ACCC
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. MPI instructions and FAQ online
5. MPI tutorial at Argonne National Lab
6. Interconnection Networks
7. 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)
8. Example Lab 1
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 (25%)
• Exam (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 4 at 3:30pm
• Week 4: (Sept 13: 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). Parallel sorting (Ch 9)
• Week 6: Parallel sorting (Ch 9); Parallel graph algorithms (Ch 10)
• Week 7: Parallel graph algorithms (Ch 10); 0/1-ILP, TSP. Parallel discrete optimization problems (Ch 11); Lab 2 due Oct 27 at 3:30pm
• Week 8: Shared memory (from notes)
• Week 9: Shared memory
  
• Week 10:
  Oct 25: Midterm. Syllabus: Chapters 1-6, 9-11
  Oct 27: Principles of Supercomputer and Cluster design: Aalap Narvekar, Sahil Pandey, Jitesh Doshi
• Week 11:Lab 3 due Nov 17 at 3:30pm
  Nov 1: Automatic parallelization and vector processors: Akanksha Mahajan, Aishwarya Gupta, Aarthy Natarajan
  Nov 3: Multicore processors: Muthaiah Murugappan, Gowtham Kanakasabapathy, Tanima Chatterjee
• Week 12: Lab 4 assigned
  Nov 8: Programming GPGPUs: Vibhu Rangavasan, Sundar Baskaran, Sriganesh Balakumar
  Nov 10: OpenMP and Posix threads: Sai Chinmayananda Korlimarla, Avinash Reddy Penugonda, Darsheel Hirpara
• Week 13: Lab 4 due Dec 1 at 3:30pm
  Nov 15: Transactional memory for multithreaded environments: Surya Selvaraj, Janani Neelakantan, VNJS Pavani
  Nov 17: QCUs and Quantum Computing: Andrew Klitzke, Bennett Clarke, Maram Sulimani
  
• Week 14:
  Nov 22: Hadoop and Mapreduce: Bhavya Mahajan, Vinit Kumar, Akhil Kateja
  Nov 24: Thanksgiving
• Week 15:
  Nov 29: Cloud computing: Shalakha Panchabhai, Priyanka Thortre, Sujaritha Sundaresan
  Dec 1: Internet of Things: Ragib Ahsan, Hasan Iqbal
• Dec 9, 1-3pm: Final. Syllabus: Midterm syllabus + distributed shared memory chapter & distributed shared memory slides