Коротко, по пунктам — подходы, синхронизация и главные ограничители.
Подходы к распараллеливанию
- Разбиение по строкам/столбцам (1D): каждой задаче — набор строк (или столбцов) матриц. Просто, но при большом числе процессов часто плохой баланс и высокая коммуникация.
- Блочное (2D) разбиение: матрицы делят на блоки $b\times b$ и распределяют по сетке процессов $p_r\times p_c$ (часто $p_r=p_c=\sqrt{p}$). Хорошее соотношение вычислений/коммуникации; базовые алгоритмы — SUMMA, Cannon, Fox.
- Коммуникация в 2D (SUMMA) на процесс примерно $O\left(\frac{n^2}{\sqrt{p}}\right)$.
- 3D / 2.5D алгоритмы: репликация данных по дополнительному измерению снижает объём коммуникации за счёт увеличения локальной памяти.
- Потоковая (пипелайнинг, стриминг): для конвейерной передачи блоков между узлами/поточками (полезно при ограниченной памяти или при overlap коммуникации и вычислений).
- Task-граф / динамическое распределение: разбиение на задачки (блоки) и выполнение через runtime (OpenMP tasks, MPI+tasks, DAGSched) с динамическим балансом и work stealing.
- На одном узле — использование оптимального BLAS (GEMM) с блочной реализацией, векторизацией, многопоточностью.
Ключевые числовые свойства
- Количество FLOP при стандартном умножении $n\times n$: примерно $2n^3$.
- Локальная память на процесс при равномерном распределении: $O\left(\frac{n^2}{p}\right)$.
- Для блочного умножения блока размера $b$: каждая умножение блоков даёт $2b^3$ FLOP и перемещает порядка $3b^2$ элементов, поэтому арифметическая плотность (приближённо) $AI\approx \frac{2b^3}{3b^2}=\frac{2}{3}b$.
- Ограничение производительности (roofline): $P\le \min (P_{\max },B\cdot AI)$, где $P_{\max }$ — пиковые FLOP, $B$ — пропускная способность памяти/сети.
Проблемы синхронизации и консистентности
- Барьеры и шаги по k в алгоритмах SUMMA/Cannon — глобальные/локальные синхронизации между этапами; частые барьеры тормозят.
- Конкурентный доступ к одним и тем же блокам C: если несколько потоков/процессов обновляют один блок, нужны атомарные операции/примитивы (редукция), либо заранее разделять накопление (локальные буферы + reduce).
- Блокировки/мьютексы и атомики: приводят к накладным расходам; лучше избегать через распределение ответственности за блоки.
- False sharing и кэшовая когерентность в shared-memory: мелкие блоки и неправильное выравнивание ухудшают производительность.
- Согласованность NUMA: неправильное размещение памяти — большой штраф (надо привязывать потоки к ядрам и распределять память по узлам).
- Асинхронная коммуникация: overlap computation/communication требует аккуратного управления зависимостями и буферами.
Ограничители производительности (что реально станет бутылочным горлышком)
- Память и кэш: при малой арифметической плотности (малый $b$) алгоритм будет memory-bound; пропускная способность памяти $B_{mem}$ ограничивает скорость.
- Сеть (для распределённых): задержка (latency) и пропускная способность (bandwidth). При сильном масштабировании коммуникация может доминировать.
- Гранулярность задач: слишком мелкие блоки — рост накладных расходов и синхронизаций; слишком крупные — плохой баланс нагрузки.
- Баланс нагрузки: неравномерное распределение работы или данных (особенно при неровных p) снижает параллельную эффективность.
- Алгоритмические пределы (Amdahl): последовательная часть приложения ограничивает ускорение.
- Аппаратные: нехватка регистров, неэффективная векторизация, TLB-промахи, contention на шинах/через контроллеры памяти.
- Реализация BLAS/GEMM: локальная оптимизация критична — используй высокопроизводительный BLAS (производительность локальных блоков часто определяет всю программу).
Практические рекомендации (кратко)
- Использовать 2D блок-циклическое распределение + оптимизированный локальный GEMM.
- Подобрать $b$ так, чтобы блоки хорошо помещались в кеш и обеспечивали высокий $AI$.
- Перекрывать коммуникацию и вычисления (асинхронные collectives, nonblocking MPI).
- Минимизировать синхронизацию: использовать локальные накопители и затем редукции, избегать глобальных барьеров.
- Учесть NUMA, привязку потоков, выравнивание данных, избегать false sharing.
- Для сильного масштабирования рассмотреть 2.5D/3D алгоритмы или алгоритмы с уменьшенной коммуникацией.
Если нужно — могу привести сравнительную схему (SUMMA vs Cannon vs 3D) и формулы коммуникационных затрат/памяти для каждого.