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. Will be announced around week 4.

1. The Argo Beowulf Cluster at UIC, its MPI tutorial, and MPI Calls on Argo, with examples
2. PPT notes by Paul Sexton, on how to get started on ARGO
3. PPT presentation by Venkatram Vishwanath, on running MPI on Argo-new
4. MPI Notes from ARGO Sys Admin, Aleksandar Leposavic
5. MPI tutorial at Argonne National Lab
6. A simple matrix multiplication program. Note: May not work as is on ARGO, due to system differences.
7. Interconnection Networks
8. 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)
   • Parallel TSP, Assignment 3
9. 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
   • Basic Communication operations - 1
   • Basic Communication operations - 2
   • Performance and Scalability
   • Sorting
   • Graph Problems
   • Discrete Optimization
   • Dynamic Programming

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
4. The best and the fastest supercomputers! Overview of Recent Supercomputers! Study these sites, including the report on HPC benchmarks.
5. Shared memory Chapter

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 (30%)
• Class presentation (15%)

Course progress chart:

• Week 1 (Jan 14 -): Introduction; processors; classification; platforms (Ch 1 + TOP500 + extra notes)
• Week 2 (Jan 21 -): PRAM model; Architectures (Ch 2)
• Week 3 (Jan 28 -): Principles of Parallel Program Design (Ch 3)
• Week 4 (Feb 4 -): Basic Communication Operations (Ch 4), Programming Assignment 1
• Week 5 (Feb 11 -): Introduction to MPI. Scalability.
• Week 6 (Feb 18 -): Scalability.
• Week 7 (Feb 25 -): Parallel Sorting. Programming Assignment 2 , Parallel matrix multiplication (self-study)
• Week 8 (Mar 3 -): Parallel graph algorithms - routing, counting, MIS. Assignment 1 due on Mar 3.
• Week 9 (Mar 10 -): 0/1-ILP, TSP, Discrete optimization problems, Parallelizing dynamic programming solutions.
  Parallel TSP, Programming Assignment 3
• Week 10 (Mar 17 -): parallel FFT, Shared memory basics - coherence, consistency models Assignment 2 due on Mar 19.
• SPRING BREAK
• Week 11 (Mar 31 -): class cancelled
  Apr 3: Midterm.
• Week 12:
  Apr 8: Presentation 1: (Sangyoon/Sungwon) Technical and theoretical analysis of supercomputer design (Top 500)
  Apr 10: Presentation 2: (Yehua/Fatima) Interconnects for High performance computing (e.g., Infiniband/Myrinet)
• Week 13:
  April 15: Presentation 3: (Arthur/Kun) Chip multiprocessors CMPs
  April 17: Presentation 4: (Li/Krzysztof) Chord and p2p network structures
• Week 14:
  April 22: Presentation 5: (HyunSeok/Dongkyun) CAN and p2p network structures
  April 24: Presentation 6: (Jingye/Xitian) OpenMP and Posix threads
• Week 15:
  April 29: Presentation 7: (Jaroslaw/Alan) Cell Processor Threading Models OR Transactional memory for Multithreaded environments
  May 1: Presentation 8: (Masroor) OpenMP and Hybrid Programming / threading models
  Assignment 3 (TSP) due
• Final exam on Tuesday, May 6, 3:30pm-5:30pm
  Syllabus: TBA
  

Literature sources: The following is a listing of journals and conference proceedings (in roughly decreasing order of relevance to this course 566) that you may find useful in your literature search.

1. IEEE Transactions on parallel and distributed systems
2. ACM Symp. on Parallel Algorithms and Architectures (SPAA)
3. ACM-SIAM Symp. on Discrete Algorithms (SODA)
4. ACM Symp. on Principles of Distributed Computing (PODC)
5. IEEE Symp. on Parallel and Distributed Processing (SPDP)
6. Inter. Conf. on Structure Information and Communication Complexity (SIRROCCO)
7. Distributed Computing
8. IEEE/ACM transactions on networking
9. Information Processing Letters
10. Inter. Conference on Distributed Computing Systems (ICDCS)
11. Inter. Conference on Parallel Processing (ICPP)
12. IEEE Transactions on Computers