CS4402B/CS9635B -- Parallel and Distributed Computing

Course Description

The efficient usage of parallel and distributed systems (multi-processors and computer networks) is nowadays an essential task for computer scientists.

This course studies the fundamental aspects of parallel systems and aims at providing an integrated view of the various facets of software development on such systems: hardware architectures, programming languages and models, software development tools, software engineering concepts and design patterns, performance modelling and analysis, experimenting and measuring, application to scientific computing.

Course topics may include but are not limited to: hierarchical memory, cache complexity, multi-core and many-core architectures, fork-join parallelism, scheduling, scalability, GPU computing, data parallelism, pipelining, message passing (MPI), parallel and distributed data-structures, and applications of parallel and distributed computing.

Follow this link for various resources (software tools and tutorials, hardware documentation, conferences, other HPC course web sites, etc.) regarding this course and HPC in general.

Instructor

Delivery mode, lecture Notes and Textbook

The format of the course lectures and tutorials will be on-line asynchronous presentations posted on the OWL web sites.

Office hours will be one-line synchronous meetings on Zoom. The office hours will not be recorded.

1. Structured Parallel Programming by Michael McCool, Arch Robison, James Reinder.
2. C++ Concurrency in Action, practical multithreading by Anthony Williams
3. Programming language pragmatics (Chapter 12 only) by Michael L. Scott
4. Models of Computation Exploring the Power of Computing by John E. Savage.
5. CUDA by example by JASON SANDERS and EDWARD KANDROT.

OWL Website

The course web site is accessible here

For CS4402, the OWL web site is here.

Please check both the course and OWL sites often for updates on lecture notes and errata, as well as the forum discussions and announcements in the OWL web sites.

Course outline

Lecture Topics

The list of topics will be something on the order of:

1. Overview of parallel and distributed computing
2. Programming patterns in parallel and distributed computing; illustration with Julia
3. Hierarchical memories, cache complexity
4. The fork-join model and the cilk concurrency platform
5. Multi-threading parallelism and performance
6. Pipelining
7. Scheduling and Synchronizing; parallelism overheads
8. Parallel Random-Access Machines.
9. Many-core programming (GPGPUs)
10. High-Performance Computing with CUDA
11. Multiprocessed parallelism, message passing (MPI)

Lecture Materials

The list of topics will be something on the order of:

1. Overview of parallel and distributed computing
2. Parallel and distributed patterns in Julia:
   1. Simple installation notes for Jupyter and Julia
   2. Jupyter notebooks illustrating parallel programming patterns in Julia
3. Hierarchical memories, cache complexity Extra materials used in the lectures:
   1. Animation of naive counting sort
   2. Animation of counting sort using buckets
   3. Animation of various transposition algorithms
   4. C programs for matrix multiplication, matrix transposition and counting sort.
4. The fork-join model and the cilk concurrency platform Extra materials used in the lectures:
   1. The OpenCilk web site
   2. OpenCilk examples
5. Dependence Analysis and (Automatic) Parallelization
6. Many-core Computing with CUDA. slides
7. Parallel Random-Access Machines
8. High-Performance Computing with CUDA slides.
9. Programming parallel patterns with C++ 11 slides
10. Multiprocessed parallelism, message passing (MPI):
    1. A Comprehensive MPI Tutorial Resource
    2. MPI intro lecture by Jon Eyolfson,
    3. MPI: Beyond the Basics by David McCaughan.
11. MetaFork: A Compilation Framework for Concurrency Platforms Targeting Multicores slides

Class Schedule

The materials (slides, recordings and other resources) of each lecture topic will be made available to the students in the course of Monday of each week of class, except for the reading week and the last week of classes.

Those materials will be accessible on the OWL web site of CS4402. Slides will also be posted on the public web site of the course.

Each student is expected to watch all the lecture recordings. Reading the slides may not be sufficient to fully comprehend the materials.

Assignment/Project/Quiz Schedule

All dates are tentative and currently subject to change, although it is doubtful by any significant amount.

Problem Sets for 2023-2024

Quiz corrections from 2014-2015

Quiz corrections from 2016-2017

Research articles proposed for the CS4402 projects in 2024-2025

Please find below papers that can be chosen for the course projects of CS4402.

• Effective automatic parallelization of stencil computations
• Automatic program parallelization
• Data Oblivious Algorithms for Multicores
• Analysis of the analytical performance models for GPUs and extracting the underlying Pipeline model
• Schönhage-Strassen algorithm with MapReduce for multiplying terabit integers
• The Pluto+ Algorithm: A Practical Approach for Parallelization and Locality Optimization of Affine Loop Nests
• The cache complexity of multithreaded cache oblivious algorithms
• Parallel Algorithms for maximum subsequence and maximum subarray paper
• Fixing Performance Bugs: An Empirical Study of Open-Source GPGPU Programs paper
• Fork/Join Parallelism in the Wild paper
• Register Spilling and Live-Range Splitting for SSA-Form Programs paper
• Beyond nested parallelism: tight bounds on work-stealing overheads for parallel futures paper
• Expressing pipeline parallelism using TBB constructs: a case study on what works and what doesn't paper
• On-the-Fly Pipeline Parallelism paper
• Pipelining with futures paper
• Tapir: Embedding Fork-Join Parallelism into LLVM's Intermediate Representation paper
• AUTOGEN: automatic discovery of cache-oblivious parallel recursive algorithms for solving dynamic programs paper
• GPU-ABiSort: optimal parallel sorting on stream architectures paper
• Optimizing Graph Algorithms for Improved Cache Performance paper
• An efficient parallelization strategy for dynamic programming on GPU paper
• Efficient Processing of Large Data Structures on GPUs: Enumeration Scheme Based Optimisation paper
• Automatic Restructuring of GPU Kernels for Exploiting Inter-thread Data Locality paper (seleted)
• A Performance Analysis Framework for Identifying Potential Benefits in GPGPU Applications paper
• Memory-level and Thread-level Parallelism Aware GPU Architecture Performance Analytical Model paper
• Optimal Loop Unrolling For GPGPU Programs paper
• In-Place Matrix Transposition on GPUs paper (selectd)
• Dynamic Programming Parallel Implementation for the Knapsack problem paper
• Parallelizing MiniSat report
• A work-efficient parallel breadth-first search algorithm (or how to cope with the nondeterminism of reducers paper
• Cross-loop Reuse Analysis and its Application to Cache Optimizations. paper
• The Tao of Parallelism in Algorithms paper

Research projects proposed for the CS9635 in 2023-2024

Please find topics that can be chosen for the course projects of CS9635.

• The polyhedral model in for-loop nestv optimization (literaure review and algorithm comparison) starrting with this paper and that paper
• Sorting algorithms in CUDA (literaure review and comparative experimentation) starrting with the paper
• prefix sum algorithms in CUDA (literaure review and comparative experimentation) starting with wikipedia and this paper