Кратко и по существу — ключевые проектные решения, их обоснование и формулы.
1) Модель задачи и цели
- Умножение $C=AB$, матрицы размеров $N\times N$ (аналогично для прямоугольных). Требования: масштабируемость, минимальная коммуникация, устойчивость к сбоям, баланс нагрузки, возможность работы вне памяти одного узла.
2) Разбиение данных (data partitioning)
- 2D блочное разбиение (рекомендуемо): разбить матрицы на блоки размера $b\times b$. Число блоков по размеру: $n_b=\lceil N/b\rceil$. Процессоры организовать в сетку $p_r\times p_c$ (обычно $p_r\approx p_c\approx \sqrt{p}$). Каждый процессор хранит примерно $\frac{N^2}{p}$ элементов.
- Плюсы: хорошая балансировка, низкая коммуникация по сравнению с 1D.
- Block-cyclic распределение: блоки распределяются по процессорам циклически; уменьшает локальные пиковые нагрузки и улучшает баланс при неоднородных вычислениях.
- 1D (строчно- или столбцово-разбиение): проще, но коммуникация и баланс хуже при большом $p$.
- 2.5D (репликация по третьему измерению): реплицировать одни из матриц в $d$ слоях, снижает коммуникацию при увеличении памяти на узлах. Память на узел увеличивается примерно в $d$ раз, коммуникация на узел становится порядка $\Theta \left(\frac{N^2}{\sqrt{pd}}\right)$.
3) Алгоритмы/схемы коммуникации
- SUMMA (Scalable Universal Matrix Multiplication Algorithm): итеративно для каждого шага $k$ выполняет широковещательные передачи по строкам/столбцам и умножение местных блоков. Прост и гибок; хорош при блочном хранении.
- Cannon: эффективен для квадратной сетки и равных блоков, минимизирует передачу, но требует циклической перестановки и строгой топологии.
- 2.5D алгоритм: уменьшает объём коммуникации ценой репликации.
- MapReduce / Spark подход: разбить по ключам (i,k) и (k,j) и агрегировать по (i,j). Удобен в облаке и для отказоустойчивости, но часто генерирует большой shuffle и медленнее, чем MPI для HPC.
- MPI (использовать non-blocking collectives: MPI_Ibcast, MPI_Iallgather): низкая латентность, оптимальные collectives и overlap коммуникации/вычисления — лучший выбор для HPC.
- PGAS/распределённая общая память (UPC, Chapel): удобнее программировать, хороши для асинхронных схем, но зависят от реализации.
4) Коммуникационная модель и оценка затрат
- Используем alpha-beta модель: передача сообщения размера $m$ слов стоит приблизительно $\alpha +\beta m$, где $\alpha$ — латентность, $\beta$ — стоимость передачи слова.
- Вычислительная нагрузка на узел: $\Theta \left(\frac{N^3}{p}\right)$.
- Нижняя граница коммуникации для матричного умножения (2D): $\Omega \left(\frac{N^2}{\sqrt{p}}\right)$ слов на процессор.
- Временная оценка: $T\approx T_{\text{comp}}+\#\text{messages}\cdot \alpha +\text{words}\cdot \beta$.
- Цель: минимизировать $\#\text{messages}$ и суммарные переданные слова, балансируя блок $b$ для оптимального соотношения вычислений/коммуникации и кэш-эффекта.
5) Синхронизация и параллельная стратегия
- Bulk-Synchronous Parallel (BSP) с шагами по $k$ (как в SUMMA) — простая корректная схема; но приводит к глобальным барьерам/скоплениям.
- Пайпелинг / overlap: использовать non-blocking коммуникации и вычисления над локальными блоками, чтобы скрыть латентность.
- Асинхронные DAG-исполнители (task-based runtimes: PaRSEC, Legion, Dask, Spark с persist): строят граф задач (умножение блоков, редукция), позволяют динамически распараллеливать и уменьшать синхронные барьеры; хороши для гибкой балансировки и частичного восстановления.
6) Устойчивость к сбоям (fault tolerance)
- Для MPI-кластера:
- Частые чекпоинты: сохранять промежуточные блоки/панели на распределённое хранилище. Восстановление дорого — перезапуск задач с последней контрольной точки.
- Message logging / ULFM (User-Level Failure Mitigation) — перезапустить communicator и перезаписать упавшие процессы.
- Algorithm-Based Fault Tolerance (ABFT): хранить контрольные суммы блоков (строчные/столбцовые) и восстанавливать утраченные блоки локально без полной перезаписи; особенно эффективно для линейной алгебры.
- Репликация (как в 2.5D): хранить дублирующие копии некоторых панелей, что ускоряет восстановление.
- Для MapReduce/Spark:
- Линейность/lineage (Spark) или HDFS-репликация: автоматическое восстановление потерянных разделов по lineage или копиям; проще, но медленнее для операций с большими shuffle.
- Рекомендация: комбинировать легкую репликацию критичных блоков + перманентное чекпоинтирование на распределённый диск + ABFT для быстрого локального восстановления.
7) Балансировка нагрузки
- Block-cyclic распределение для борьбы с неравномерной нагрузкой и значениями блоков, требующими разного времени умножения.
- Динамическое планирование задач (task-stealing) в task-runtime: полезно при гетерогенных узлах.
- Подбор размера блока $b$: должен удовлетворять компромиссу:
- $b$ достаточно большой, чтобы эффективность ядра и снижение числа сообщений,
- но достаточно мал, чтобы данные помещались в локальную память/кэш и обеспечить гибкость балансировки.
- В случае неоднородных узлов — весовые распределения блоков пропорционально производительности памяти/CPU.
8) Работа с данными, выход за пределы памяти (out-of-core)
- Стриминг блоков с диска/SSD: загружать панели $A_{:,k}$, $B_{k,:}$ последовательно; использовать предзагрузку (prefetch) и асинхронный I/O.
- Параллельный файловый слой (PVFS, Lustre, HDFS) с локальным кэшированием блоков.
- Минимизировать случайный доступ; планировать последовательный доступ к блокам.
9) Практические рекомендации / выбор стека
- HPC-кластер, требование максимальной производительности: MPI + SUMMA или 2.5D + block-cyclic, non-blocking collectives, ABFT/чекпоинты + параллельный файловый слой.
- Облако / удобство и отказоустойчивость: Spark (или Dask) с блочным разбиением, persist RDD/DS, репликация HDFS; но ожидайте больше shuffle и худшую производительность.
- Для гибридных решений: task-based runtime (PaRSEC, StarPU) для динамического распределения и overlap, + MPI collectives на уровне узлов.
10) Итоговые эмпирические формулы (для выбора параметров)
- Вычисление на узел: $T_{\text{comp}}\approx \gamma \cdot \frac{N^3}{p}$ (где $\gamma$ — время на одну FLOP).
- Коммуникация (2D): слова на узел $\Theta \left(\frac{N^2}{\sqrt{p}}\right)$.
- При репликации в $d$ слоёв (2.5D): слова ≈ $\Theta \left(\frac{N^2}{\sqrt{pd}}\right)$, память на узел ≈ $\Theta \left(\frac{d{N}^2}{p}\right)$.
- Баланс блоков: число блоков на измерение $n_b=\lceil N/b\rceil$; выбирайте $b$ чтобы $b^2$ ~ размер локальной памяти / (константа для временных буферов).
Если нужно — дам конкретную архитектуру (число слоёв, размер блока $b$, топологию $p_r\times p_c$) под ваши конкретные $N$, объём памяти на узел и число узлов.