Computing platforms have limited resources, such as memory, cache, bandwidth, and processing power. In the past, algorithms have been derived with optimal complexity and thus are supposed to make an efficient usage of processing power, while memory, cache and bandwidth limitations have often been ignored. However, it is often the case that these resources become the primary factors limiting overall performance, especially (but not only) when using accelerators such as GPUs. GPUs offer increased processing capabilities and superior energy efficiency compared to CPUs, making them a crucial element of many computing systems over the past decade.

In this course, we will present on one hand algorithmic approaches that have recently been proposed in order to utilize all resources efficiently, and on the other hand we will focus on how to implement these efficient algorithms on real hardware platforms. The typical use case will focus on linear algebra computations (matrix operations), which are the basis of both "traditional" high performance computing applications and recent neural network computations.

A sequential machine. A distributed memory machine. Nvidia Volta 100 architecture.

Outline

• Introduction
  • Course details and evaluation methods
  • Relevance of this course
• Models and algorithms for CPU computations
  • Matrix multiplications
  • I/O complexity bounds
  • Data transfer cost models
  • Communication avoiding sequential and parallel algorithms
  • 2D/2.5D/3D algorithms
  • Directed acyclic graph (DAG) scheduling
  • Memory aware computations
  • Exploratory research topics
• GPU fundamentals
  • GPU vs CPU architecture
  • CUDA basics
  • Memory model, threads, blocks
  • Memory optimizations using shared memory
  • Coalescing and memory alignment
  • Tensor cores
  • Exploratory research topics
• Implementation on CPUs and GPUs
  • Parallelization using OpenMP and MPI
  • Parallelization using CUDA

We will look at several interesting research projects in the course related to parallel computations in high performance computing, machine learning and data analytics.

Lectures

• Lecture 1 (Nov 20, by F. Vivien): Introduction to Scheduling Under Memory Constraints and Pebble Game Models slides notes.
• Lecture 2 (Nov 21, by S. Kumar): Overview of the GPU part slides and parallelization approaches on CPUs slides.
• Lecture 3 (Nov 27, by F. Vivien): Pebble Game Models (2/2) slides notes.
• Lecture 4 (Nov 28, by S. Kumar): Introduction to CUDA programming slides.
• Lecture 5 (Dec 04, by L. Marchal): Communication avoiding algorithms and parallel IO-efficient algorithms for matrix product slides
• Lecture 6 (Dec 05, by S. Kumar): Occupancy analysis for a Volta SM slides.
• Lecture 7 (Dec 11, by S. Kumar): Some basic CUDA APIs slides.
• Lecture 8 (Dec 12, by S. Kumar): Research articles for the projects slides and low rank approximations of matrices and tensors slides.
• Lecture 9 (Dec 18, by F. Vivien): Memory-Aware DAG Scheduling slides.
• Lecture 10 (Dec 19, by S. Kumar): Error handling on GPUs slides.
• No class on Jan 08.
• Lecture 11 (Jan 09, by F. Vivien): See the slides for Lecture 9 (Dec 18).
• Lecture 12 (Jan 15, by L. Marchal): Computing for LLMs: associated memory and IO challenges. Related articles: FlexGen, MoE optimization and slides for this paper.
• Lecture 13 (Jan 16, by S. Kumar & S. Singh): Parallel scan algorithms suggested reading; Parallel graph algorithms on GPUs slides.
• Lecture 14 (Jan 21, by S. Kumar): Parallel scan and sorting algorithms slides.
• Lecture 15 (Jan 22, by L. Marchal): External Memory Model and Cache-Oblivious Algorithms slides.
• Lecture 16 (Jan 23, by S. Kumar): Popular CUDA libraries slides.

Prerequisite

Experience with C/C++ is expected. Knowledge of parallel algorithms will be helpful, but not required.

Evaluation

The evaluation will be based on the following weightings:

• 2 pen-and-paper-based assignments (20% weight)
• 3 small programming assignments (30% weight)
• Project (50% weight): Each student will select an article based on their interests and work on it. The output will be accessed based on a written report and an oral prsentation.