Numerical Methods

Параллельные вычисления в линейной алгебре

Цели урока

  • Понять алгоритм Кэннона и условия линейного ускорения параллельного умножения матриц
  • Освоить методы Крылова в распределённой памяти: параллельный SpMV и коммуникационные паттерны CG/GMRES
  • Разобраться в рандомизированном SVD и GPU-ускорении через cuBLAS и смешанную точность

Предварительные знания

  • Спектральные методы
  • Спектральные методы

Google PaLM 540B: 6144 TPU v4, 56 петафлопс - весь обмен данными построен на параллельном GEMM

  • Google PaLM 540B: 6144 TPU v4, 56 петафлопс - весь обмен данными построен на параллельном GEMM
  • Netflix распределённый SVD: матрица 100M пользователей x 500K фильмов факторизуется рандомизированными методами
  • ECMWF 4D-Var: параллельный CG на 100K процессорах для ассимиляции данных погоды
  • GPT-4 инференс: смешанная точность FP8/FP16 даёт 2x ускорение на H100 без потери качества

История параллельной линейной алгебры

Lynn Elliot Cannon (1969, докторская диссертация) предложил алгоритм для SIMD-компьютеров - задолго до современных GPU. Jack Dongarra (Tennessee) создал LAPACK (1992) и ScaLAPACK (1995) - стандарты, используемые до сих пор. TOP500 суперкомпьютеров ранжируется по HPL (High Performance Linpack) - решению плотной системы СЛАУ, алгоритмически это ScaLAPACK. NVIDIA cuBLAS (2007) перенёс BLAS на GPU, изменив всё.

Параллельное умножение матриц и алгоритм Кэннона

Google обучил PaLM 540B параметров за 1400 часов на 6144 TPU v4 с пиковой производительностью 56 петафлопс. Каждый шаг обучения - миллиарды матричных умножений. Алгоритм Кэннона распределяет их по сетке процессоров с линейным ускорением при правильном соотношении размера матрицы и числа процессоров.

0

1

Sign In

ScaLAPACK (Scalable LAPACK) - стандарт параллельной линейной алгебры для MPI-кластеров. Использует блочно-циклическое распределение (размер блока 64-128). Hypre, PETSc, TRILINOS строятся поверх ScaLAPACK/PBLAS.

При каком условии алгоритм Кэннона достигает линейного ускорения S(p) = p?

Соотношение вычислений к коммуникациям: (2n^3/p) / (n^2/sqrt(p)) = 2n/sqrt(p). При n >> sqrt(p) вычисления доминируют. Для GPT-3: n~12288, p~1024, n/sqrt(p) = 384.

Параллельные методы Крылова: GMRES и CG на кластере

Прямые методы (LU, Cholesky) не масштабируются на распределённую память: факторизация матрицы n x n требует O(n^3) коммуникаций. Методы Крылова (CG, GMRES, BiCGSTAB) итерационные: каждая итерация - одно матрично-векторное произведение. На разрежённых матрицах это O(nnz) операций и минимальные коммуникации.

GMRES (Generalized Minimal RESidual) для несимметричных систем хранит m векторов базиса Крылова - pipe-parallelism: m матрично-векторных произведений за счёт m*(m+1)/2 скалярных произведений. При restart m=50 это 1275 Allreduce на restart - latency bound при большом p.

Trunk-parallel GMRES (pipeline GMRES) переупорядочивает вычисления так, что Allreduce перекрывается с умножением матриц. Библиотека Trilinos реализует CA-GMRES (communication-avoiding), снижающий число Allreduce в K раз за счёт K шагов без синхронизации.

Почему методы Крылова масштабируются на распределённую память лучше прямых методов?

Параллельная эффективность определяется соотношением вычислений к коммуникациям. SpMV для разрежённой матрицы: O(nnz/p) вычислений, O(border_elements) коммуникаций. LU: wavefront-паттерн зависимостей не допускает независимых обновлений.

Распределённый SVD и рандомизированные алгоритмы

Для матрицы 10^6 x 10^5 полный SVD занимает 10^16 операций - недостижимо. Усечённый SVD нужен в рекомендательных системах (Netflix Prize) и снижении размерности. Рандомизированный SVD (Halko, Martinsson, Tropp, 2011) вычисляет k старших компонент за O(mnk) операций - и легко параллелизуется.

В распределённой памяти рандомизированный SVD эффективен: Y = A*Omega вычисляется как p+k параллельных SpMV. QR через TSQR (Tall-Skinny QR, Demmel 2012) - communication-optimal алгоритм на MPI. Netflix и Spotify используют распределённый SVD для матричной факторизации рекомендательных систем.

Почему рандомизированный SVD работает надёжно, несмотря на случайную проекцию?

Ключевое свойство: случайный вектор из гауссовского распределения почти наверняка не ортогонален ни одному из k главных направлений. k+p проекций охватывают k-мерное сигнальное пространство с вероятностью 1 - exp(-p^2/2) примерно.

GPU-ускорение линейной алгебры: cuBLAS и смешанная точность

NVIDIA A100 имеет 312 TFLOPS на TF32 и 624 TFLOPS на FP16. Разрыв с CPU - более 1000x для матричных умножений. CUDA ядра cuBLAS достигают 80-90% пиковой производительности для GEMM. Именно на этом стоит весь современный deep learning.

Смешанная точность (mixed-precision training) - FP16 для умножений, FP32 для накопления - стандарт с 2018 года (NVIDIA Apex, затем PyTorch native). На матрицах 4096x4096: FP16 GEMM 2x быстрее FP32 при той же точности обучения. Nvidia H100 добавил FP8 - ещё 2x ускорение для LLM-инференса.

Параллельная линейная алгебра в обучении трансформеров

GPT-3 (175B параметров) обучается на 1024 GPU A100. Тензорный параллелизм (Megatron-LM): матрица внимания делится по головам между GPU. Пайплайн-параллелизм: слои распределяются по GPU, micro-batching скрывает латентность. Model parallelism + data parallelism + pipeline parallelism = 3D-параллелизм, позволивший обучить GPT-4.

Что такое тензорный параллелизм в обучении трансформеров?

Tensor parallelism (Megatron-LM): матрица W делится по столбцам W = [W1 | W2]. GPU1 вычисляет y1 = xW1, GPU2 - y2 = xW2. AllReduce объединяет y = [y1, y2]. Для Q,K,V матриц в attention - деление по головам.

Связь с другими темами

Параллельная линейная алгебра - фундамент современного ML: обучение LLM требует тензорного параллелизма (GEMM распределение), рандомизированного SVD (snapshotting, LoRA) и эффективных SpMV (sparse attention). Все методы Крылова, решатели МКЭ/спектральных задач параллелизуются через ScaLAPACK/PETSc.

  • Randomized SVD for ML — Связанная тема
  • Mixed-Precision Deep Learning — Связанная тема
  • Parallel Krylov Solvers — Связанная тема

Итоги

  • Алгоритм Кэннона: линейное ускорение S(p)=p при n >> sqrt(p); ScaLAPACK реализует блочно-циклическое распределение для обобщённых случаев
  • Методы Крылова масштабируются через параллельный SpMV + MPI_Allreduce для скалярных произведений; CA-GMRES уменьшает число Allreduce в K раз
  • Рандомизированный SVD: O(mnk) вместо O(mn^2); случайная проекция + малый SVD; гарантированная ошибка через теорию случайных матриц Халько-Мартинссона
  • GPU-ускорение: cuBLAS достигает 90% пика для GEMM; смешанная точность FP16/FP32 - стандарт обучения с 2018; тензорный параллелизм Megatron-LM для LLM

Вопросы для размышления

  • Алгоритм Кэннона требует квадратного числа процессоров p = q^2. Что происходит при некратном N и нечётном числе процессоров - как это решается в реальных HPC-библиотеках?
  • CA-GMRES сокращает число MPI_Allreduce в K раз, но требует K шагов без синхронизации. Как это влияет на численную устойчивость при большом K?
  • Рандомизированный SVD использует случайность для ускорения. Существуют ли детерминированные алгоритмы с аналогичной сложностью O(mnk) для усечённого SVD?

Связанные уроки

  • nm-23 — спектральные методы порождают задачи линейной алгебры для параллельного решения
  • nm-25-autodiff — параллельный autodiff требует тех же техник распределённой памяти
  • nm-21 — параллельный AMG - основная задача для ScaLAPACK
Параллельные вычисления в линейной алгебре