CS4402/CS9635
Distributed and Parallel Systems

Course Description

To best utilize parallel and distributed systems (multi-core, many-core and cluster) 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:

• multi-core, GPGPU, cluster, distributed and shared memory, hierarchical memory,
• multi-thread (Julia, CilkPlus, OpenMP), multi-process, message passing (Julia, MPI),
• scheduling (work-stealing scheduler) and synchronization,
• parallel algorithm design and multithreaded program analysis: parallelism, granularity, memory bandwidth issue, scalability, data locality and cache complexity,
• Intel Parallel Composer (Cilk Plus, ArBB, TBB), data race and performance analyzer (Cilkview, Vtune)
• NVIDIA's CUDA for GPU
• Message Passing Interface (MPI)
• high-performance software engineering techniques,
• fundamental applications: matrix multiplication, matrix transposition, FFT, reduction, scan, sort, etc.

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 (http://www.csd.uwo.ca/~moreno/HPC-Resources.html).

Prerequisites for Undergraduate Students

• Students must be fluent in C or C++; they must also be familiar with UNIX software tools (shell scripts, makefiles, debuggers).

Instructor

Lecture Notes and Textbook

Notes of each lecture will be available on the course website, approximately one or two days after the oral presentation. There is no textbook.

Course and OWL Websites

The course web site is accessible here For CS4402 and CS9635, the OWL web sites are respectively here and there.

Please check the site often for updates on lecture notes and errata. Also be aware that the course website is not a substitute for actual classroom attendance!

Course outline

Lecture Topics

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

• Overview of parallel computing
• Hierarchical memories, cache complexity
• The Cilk concurrency platform
• Multithreading parallelism and performance
• Scheduling and Synchronizing
• Parallelism overheads
• Parallel Random-Access Machines.
• Many-core programming (GPGPUs)
• Code optimization techniques for multi-cores and GPGPUs
• High-Performance Computing with CUDA
• Pipelining
• Multiprocessed parallelism, message passing (MPI)
• Other concurrency platforms (Julia, Open MP, Threading Building Blocks)

Lecture Notes for 2019-2020

Problem Sets for 2019-2020

Problem Sets for 2019-2020

Quiz corrections from 2014-2015

Quiz corrections from 2016-2017

CS4402 projects in 2019-2020

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

• Parallel Algorithms for maximum subsequence and maximum subarray paper (selected)
• Fixing Performance Bugs: An Empirical Study of Open-Source GPGPU Programs paper (selected)
• Register Spilling and Live-Range Splitting for SSA-Form Programs paper (selected)
• 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 (selected)
• On-the-Fly Pipeline Parallelism paper (selected)
• Pipelining with futures paper
• Tapir: Embedding Fork-Join Parallelism into LLVM's Intermediate Representation paper (selected)
• 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 (selected)
• An efficient parallelization strategy for dynamic programming on GPU paper (selected)
• 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 (selected)
• A Performance Analysis Framework for Identifying Potential Benefits in GPGPU Applications paper (selected)
• Memory-level and Thread-level Parallelism Aware GPU Architecture Performance Analytical Model paper (selected)
• Optimal Loop Unrolling For GPGPU Programs paper
• In-Place Matrix Transposition on GPUs paper (selected)
• Dynamic Programming Parallel Implementation for the Knapsack problem paper (selected)
• Parallelizing MiniSat report
(selected)
• Sorting algorithms in CUDA (literaure review and comparative experimentation) paper (selected)
• prefix sum algorithms in CUDA (literaure review and comparative experimentation) wikipedia and one paper to start with (selected)

Computing Facilities

Each student will be given an account on the Computer Science Department senior undergraduate computing facility, GAUL. In accepting the GAUL account, a student agrees to abide by the department's

Note: After-hours access to certain Computer Science lab rooms is by student card. If a student card is lost, a replacement card will no longer open these lab rooms, and the student must bring the new card to a member of the Systems Group in Middlesex College Room 346.