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

Цели урока

• Понять алгоритм Кэннона и условия линейного ускорения параллельного умножения матриц
• Освоить методы Крылова в распределённой памяти: параллельный 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 петафлопс. Каждый шаг обучения - миллиарды матричных умножений. Алгоритм Кэннона распределяет их по сетке процессоров с линейным ускорением при правильном соотношении размера матрицы и числа процессоров.

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

Параллельные методы Крылова: 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 шагов без синхронизации.

Распределённый 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 для матричной факторизации рекомендательных систем.

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-инференса.

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

Параллельная линейная алгебра - фундамент современного 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