Email:
ajay@uic.edu
Prerequisites:
CS 401 and CS/ECE 466 or equivalents, or permission of instructor
Required Textbooks/ Sources:
-
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.
-
Selection of papers to be studied in class.
Auxiliary resources:
- An Overview Chart
- 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
- MPI tutorial at Argonne National Lab
- Interconnection Networks
- 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)
- Overhead slides used in class.
- The best and the fastest supercomputers! Study this site including the report on HPC benchmarks.
- Shared memory Chapter
Supplemental References and sources:
-
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
-
Parallel Computation : Models and Methods,
by Selim G. Akl / Prentice Hall / April 1997
-
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:
- Various parallel topologies (e.g., hypercube, torus)
and algorithms on such topologies
- Parallel algorithms for counting, sorting, routing, and graphs
- Parallel alogrithms for NP-complete problems
- Parallel matrix multiplication, Fast Fourier Transforms
- Shared memory parallel systems
- Programming using MPI (Message Passing Interface); case studies of systems/platforms
- 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