Resource-aware computations on CPUs and GPUs

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.

 

 

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

Prerequisite

Evaluation

• 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.

Course project for the final evaluation

Project presentation schedule for Jan 30

Research articles

• Various hardness results in different red-blue pebbling variants. Assigned to Isaline PLAID. On the Hardness of Red-Blue Pebble Games (Specific part: proof of Theorem 2 (NP-hardness))
• Rules of the pebble game. Assigned to Alexandre KEJIKIAN. Move rules and trade-offs in the pebble game (Specific part: proof of Theorem D (removing one pebble leads to exponential time)
• Expression tree evaluation. Assigned to Marius GOYET. Memory-optimal evaluation of expression trees involving large objects (Specific part: code the algorithm, compare it to a simpler strategy, optional: compare it to this paper)
• Inference of Mixture-of-Experts (MoE) language models. Assigned to Kylian FONTAINE. Fast Inference of Mixture-of-Experts Language Models with Offloading (Specific part: test LRU on (provided) expert activation traces, possibly improve it)
• Improving MoE inference. Assigned to Yanis DZIKI. AdapMoE: Adaptive Sensitivity-based Expert Gating and Management for Efficient MoE Inference (Specific part: implement the strategy and test it (through simulation) on actual expert activation traces (provided), possibly extend it to other expert patterns (4/16, 6/64, …))
• A speculative algorithm to improve LLM inference. Cascade Speculative Drafting for Even Faster LLM Inference (Specific part: proof of Theorem 4.3)
• Deep neural network training strategies on heterogeneous systems. Assigned to Karl FLYGAR. Optimal GPU-CPU Offloading Strategies for Deep Neural Network Training (Specific part: explanation of Algorithm 1)
• I/O analysis for symmetric computations. I/O-Optimal Algorithms for Symmetric Linear Algebra Kernels (Specific part: explain the optimal algorithm and discuss how it can be implemented efficiently)



• Low rank approximations for stencil computations. LoRAStencil: Low-Rank Adaptation of Stencil Computation on Tensor Cores
• Exploiting structured sparsity for stencil computations. SparStencil: Retargeting Sparse Tensor Cores to Scientific Stencil Computations via Structured Sparsity Transformation
• Rectangular matrix multiplications on GPUs. Assigned to Lucien LORIFERNE. KAMI: Communication-Avoiding General Matrix Multiplication within a Single GPU
• Sparse-dense matrix multiplication on tensor cores. Bridging the Gap between Unstructured SpMM and Structured Sparse Tensor Cores
• Sparse-dense matrix multiplications on GPUs. Assigned to Armand DIDIERJEAN. StraGCN: GPU-Accelerated Strassen’s Sparse-Dense Matrix Multiplication for Graph Convolutional Network Training
• Sparse matrix multi-vector products on GPUs. Assigned to Timothy COURTOIS. Efficient Sparse-Matrix Multi-Vector Product on GPUs
• Sparse tensor operations on GPUs. Load-Balanced Sparse MTTKRP on GPUs
• Matrix multiplication using sparsity. Assigned to Ulysse DURAND. NM-SpMM: Accelerating Matrix Multiplication Using N:M Sparsity with GPGPU
• Minimum spanning trees on GPUs. Assigned to Clement REMY. A High-Performance MST Implementation for GPUs
• IO-aware attention algorithm for GPUs. Assigned to Alimzhan GUMRAN. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness

Bibliography