Кратко и по делу — основные приёмы и почему они работают.
1) Представления: плотный vs разреженный
- Плотная матрица: хранить непрерывно (row-major или column-major). Хорошо для операций, где большинство элементов используются; максимально использует SIMD/BLAS и кэш.
- Разрежённая матрица: выбирать формат в зависимости от структуры:
- COO — простой, удобен для сборки; плох для операций умножения/доступа по строкам/столбцам.
- CSR (compressed sparse row) — эффективен для умножения на вектор/строки; хранит тройки (values, col_idx, row_ptr).
- CSC — как CSR, но для доступа по столбцам.
- Block-sparse / BSR — полезен, если ненулевые элементы кластеризованы в блоки; даёт лучшее использование кэша и SIMD.
- Выбор влияет на сложность операций и константы; например, умножение разрежённой матрицы на вектор — $O(\text{nnz})$, где $\text{nnz}$ — число ненулей.
2) Блочная организация (blocking / tiling)
- Идея: разбивать матрицы на блоки размера $b\times b$, где блок помещается в кэш. Блочная матричная мультипликация:
$$C_{IJ}+=A_{IK}{B}_{KJ}$$ где $I,J,K$ — индексы блоков.
- Выбор $b$ определяется размером L1/L2-кэша: снизить пропуски при повторном использовании данных. Для плотных матриц это часто даёт многократное ускорение, не меняя асимптотику $O(n^3)$.
- Для разрежённых матриц использовать BCSR или блочную CSR — уменьшает накладные расходы на индексы и улучшает локальность.
3) SIMD / векторизация и BLAS
- Использовать оптимизированные реализации BLAS (Level 1/2/3): BLAS-3 (gemm) наиболее эффективен — агрегирует операции и хорош для кэша/SIMD. Библиотеки: Intel MKL, OpenBLAS, BLIS, cuBLAS (GPU).
- SIMD/векторизация: обеспечить выравнивание (aligned allocator), непрерывность памяти, избегать условных ветвлений в горячем цикле. Компилятор/интринзики могут давать прирост в зависимости от длины векторного регистра.
- Параллелизация: BLAS-библиотеки обычно многопоточные. Для своих реализаций — использовать OpenMP/TBB и избегать ложного шаринга (false sharing), стараться работать с крупными блоками на поток.
- На GPU — использовать cuBLAS / cuSPARSE; крупные операции и плотные блоки дают максимум производительности.
4) Порядок обхода данных и кэш‑локальность
- Для row-major (C): итерация с внутренним циклом по столбцам в строке плохо (страйд большой); лучше внутренний цикл по столбцу, где индекс меняется последовательно по памяти:
- Если хранение row-major, эффективный доступ: A[i][k] с вложенным циклом по k.
- Для column-major (Fortran/BLAS) — наоборот.
- Избегать частых обращений с большим шагом (stride) — они приводят к кэш-промахам и TLB-промахам.
- Транспонирование: если умножаете A*B и доступ к B идёт по столбцам при row-major хранении, полезно заранее транспонировать B или работать блоками/транспонированными блоками.
- Префетчинг: компилятор/процессор подхватывает последовательный доступ; для сложных шаблонов можно давать подсказки prefetch.
5) Другие практические моменты
- Плотность данных vs пропускная способность памяти: для больших матриц часто узким местом является память, не CPU — оптимизировать количество обращений к памяти (реиспользование данных в кэше).
- Уменьшение аллокаций: выделять большие contiguous буферы, переиспользовать, избегать частых выделений/копирований.
- Перестановки/реоценка ненулей: для разрежённых матриц алгоритмы перевыстраивают (Cuthill–McKee, Reverse Cuthill–McKee) для уменьшения профиля ненулей и повышения локальности.
- Предобусловливание и факторизация: при решении систем с разрежёнными матрицами выбирать схемы разложения, минимизирующие заполнение (fill-in).
- NUMA: на многопроцессорных системах учитывать привязку памяти и потоков (local allocation).
Короткий чек‑лист для практики
- Если матрица плотная — используйте BLAS-3 (gemm), блочное хранение, выровненную contiguous память, оптимальную библиотеку (MKL/OpenBLAS/BLIS), подобрать размер блока под кэш.
- Если разрежённая — выбрать CSR/CSC/BSR в зависимости от операций; минимизировать индексы и перераспределять для лучшей локальности; использовать специализированные sparse-библиотеки (cuSPARSE, MKL sparse).
- Следить за порядком обхода (соответствие row/column major), избегать больших stride‑доступов; при многопоточности — избегать ложного шаринга и учитывать NUMA.
Это краткое руководство при оптимизации операций с большими матрицами.