CS 494 Parallel and Distributed Processing Spring 2021

Meets: MW 4:30pm - 5:45pm
Room: online sync
Call number: 42280 (ugrad) and 42281 (grad)
Instructor: Ajay Kshemkalyani
Office hours: W 5:45-6:30pm BB Collaborate
Email: ajay@uic.edu

Course Description: This class explores the foundations of parallel and distributed computing. Emphasis will be laid on parallel and distributed algorithms, for basic topics ranging from graph algorithms to mutual exclusion, deadlock detection, and predicates detection algorithms, to design of communication algorithms for elementary primitives such as multicast, broadcast, scatter, gather, all-to-all personalized communication on distributed systems as well as clusters based on specific topologies. Basic concepts such as scalability of systems (i.e., combination of architecture plus algorithm) will also be explored. As a case study, the Message-Passing Interface (MPI) will be introduced, and students will be exposed to programming using MPI on UIC’s Extreme cluster. Ultimately, the goal is to foster an understanding of the various ways in which concurrent actions in the system and the lack of global knowledge in the system can affect the design of parallel and distributed algorithms.

List of topics:

  1. Basics of cluster design (1 week)
  2. Algorithms for implementing basic communication primitives on topologies (2 weeks)
  3. Introduction to MPI (1 week)
  4. Scalability analysis of parallel systems (1 week)
  5. Distributed graph algorithms (for traversals, collaborative exploration, routing, MIS, synchronizers, etc) (3 weeks)
  6. Mutual exclusion algorithms, deadlock detection algorithms, termination detection algorithms, leader election algorithms (3 weeks)
  7. Predicate detection algorithms (1 week)
  8. Total order and causal order multicast (1 week)
  9. Search algorithms and dynamic load balancing for discrete optimization (1.5 week)

Prerequisites: Programming skills amenable to programming the UIC Extreme cluster, in a language such as C, is required. CS 401 and CS 450 are recommended but not required.

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.

Required Textbooks/ Sources:

  1. Introduction to Parallel Computing, by V. Kumar, A. Grama, A. Gupta, G. Karypis, Benjamin-Cummins, 2nd edition, 2003.
  2. Distributed Computing: Principles, Algorithms, and Systems, by Kshemkalyani and Singhal, Cambridge University Press, March 2011 edition
Auxiliary resources:
  1. An Overview Chart
  2. Winners of the Dijkstra Award for Most Influential Paper in Distributed Computing, 2000-.
  3. The best and the fastest supercomputers! Study this site including the report on HPC benchmarks.
  4. UIC's EXTREME cluster and a Knowledge base (how to login, run jobs, list of FAQs, etc.) and Slides from ACER
  5. MPI tutorial at Argonne National Lab
  6. Interconnection Networks
  7. Amdahl's Law
  8. The Travelling Salesman Problem
  9. Overhead slides used in class.

Course progress chart (tentative):