| CS/ECE 566 |
Parallel Processing |
Fall 2017 |
Meets: TR 3:30 PM - 4:45 PM.
Room: LC A7
Call number: 33741 (CS) and 33742 (ECE)
Instructor:
Ajay Kshemkalyani
Office: 915 SEO (Office Hours: T 5:00-6:00 PM & by appt.)
Phone: 355-1309
Email:
ajay@uic.edu
Grader:
Maram Sulimani
Office: SEO 1339 (Office Hours: T, R 11:00 - 12 noon & by appt.)
Email: msulim3@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.
-
Selection of papers to be studied in class.
Auxiliary resources:
- An Overview Chart
- UIC's new EXTREME cluster and a
list of FAQs
and Slides from ACER
- 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
-
Technical documentation,
MPI instructions
- MPI tutorial at Argonne National Lab
- Interconnection Networks
- Amdahl's Law
- 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.
- Distributed 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 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 3 at 3:30pm
- 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 24 at 3:30pm
- Week 7: Parallel graph algorithms (Ch 10); 0/1-ILP, TSP. Parallel discrete optimization problems (Ch 11)
- Week 8: Shared memory (from notes)
- Week 9: Shared memory
- Week 10:
Oct 31: Midterm 1. Syllabus: Chapters 1-6, 9-11
Nov 2: Automatic parallelization and vector processors: Rajesh, Aditya, Dinkar
- Week 11:
Nov 7: Multicore processors: Yash, Aakansha, Hardik
Nov 9: Programming GPGPUs: Trung, Antonio, Andrea
- Week 12:
Lab 3 due Nov 14 at 11:59pm
Lab 4 due Dec 7 at 11:59pm
Nov 14: OpenMP and Posix threads: Dan, Haoyu, Yichen
Nov 16: Transactional memory for multithreaded environments: Anil, Venkata, Vishesh
- Week 13:
Nov 21: QCUs and Quantum Computing I: Mathematical Foundations: Yelena, Mitch, Ed
Nov 23: Thanksgiving
- Week 14:
Nov 28: QCUs and Quantum Computing II: Mathematical Foundations and Systems: Pengzhen, Ahmed, Ziyi
Nov 30: Hadoop and Mapreduce: Greg, Balpreet, Riyansh
- Week 15:
Dec 5:
Dec 7: Midterm 2. Syllabus: Midterm 1 syllabus + distributed shared memory chapter & distributed shared memory slides