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.

Course and OWL Websites

The course web site is accessible here This course web site is used to post materials about the course projects.

For CS4402, the OWL web site is here. It is used to post lecture materials (slides, source code, videos, etc.) as well as for submitting assignments and quizzes. It is also used for managing the grades of CS9635 students.

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 site of CS4402.

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 BPASIntro-0923.mp4 BPAS-Parallel.mp4
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

Assignment/Project/Quiz Schedule

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

Quiz corrections from 2014-2015

Quiz corrections from 2016-2017

Research articles proposed for the CS4402 projects in 2025-2026

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
• Write-avoiding algorithms paper
• Exploiting multiple levels of parallelism in sparse matrix-matrix multiplication paper
• Communication lower bounds and optimal algorithms for numerical linear algebra paper
• Towards Zero Spawn Overhead: Work Stealing Without Deques paper
• Eliminating Bank Conflicts in GPU Mergesort paper
• Minimizing Processor Count for Fault Tolerant Toom-Cook Algorithms paper
• Don't Melt Your Cache: Low-Associativity with Heat-Sink paper
• A Fast Mutual Exclusion Algorithm paper
• Some Myths About Famous Mutual Exclusion Algorithms paper
• Memory Optimizations for Sparse Linear Algebra on GPU Hardware paper
• Low depth cache-oblivious algorithms paper
• Cache-efficient dynamic programming algorithms for multicores h paper
• A bridging model for multi-core computing paper
• On the design of algorithms for VLSI systolic arrays paper
• Some linear-time algorithms for systolic arrays paper
• Warp-Consolidation: A Novel Execution Model for GPUs paper
• Dynamically Finding Optimal Kernel Launch Parameters for CUDA Programs paper
• A User's Guide to MPI paper running a software demo of MPI is required: 2 students can work together on this project
• MapReduce in MPI for Large-scale graph algorithms paper
• Performance Evaluation of Advanced Features in CUDA Unified Memory paper
• How Much Parallelism is There in Irregular Applications? paper
• METAFORK: A Framework for Concurrency Platforms Targeting Multicores paper
• Optimization Techniques for GPU Programming paper long paper: 2 students can work together on this project
• GPUVerify: a verifier for GPU kernels (long paper: 2 students ) technical paper: 2 students can work together on this project

Research projects proposed for CS9635 in 2025-2026

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