Кратко: делайте разбиение и расписание так, чтобы минимизировать объём сетевого трафика (количество передаваемых ненулевых элементов и промежуточных частичных произведений), уравновесить по вычислительной нагрузке (флопсы ≈ количество скалярных умножений) и максимально перекрывать коммуникацию с локальной работой. Ниже — конкретная стратегия и варианты с оценками и практическими приёмами.
Задача: $C=AB$, где $A$ — $m\times k$, $B$ — $k\times n$, обозначим $\text{nnz}(X)$ — число ненулей в матрице $X$. Оценка количества скалярных умножений:
$$\text{flops}\approx \sum _{t=1}^k\text{nnz}(A_{:,t})\cdot \text{nnz}(B_{t,:}).$$
Варианты разбиения (плюсы/минусы, когда применять)
1) 1D (по строкам или столбцам)
- Разбиение по строкам: каждому процессу достаётся набор строк $A_{I,:}$ и он должен вычислить строки $C_{I,:}$. Для этого нужен весь $B$ (или соответствующие части).
- Плюсы: простота; локальные вычисления концентрированы.
- Минусы: если $B$ большой, требуется репликация/широковещание $B$ — большой сетевой трафик; плохая балансировка при нерегулярной разреженности.
- Когда подходит: если одна матрица (обычно $B$) значительно меньше по nnz и может быть эффективно реплицирована.
Коммуникация (оценка): передача $B$ к каждому из $P$ узлов ≈ $\text{nnz}(B)\cdot (P-1)/P$ один раз; при итеративных алгоритмах — повторный трафик.
2) 2D блоковое разбиение (например p×q процессоров)
- Разбиваем $A,B,C$ на блоки $A_{i\ell },B_{\ell j},C_{ij}$. Алгоритм SUMMA-подобный: для каждой $\ell$ поочерёдно передаём нужные блоки по строкам/столбцам и локально обновляем $C_{ij}$.
- Плюсы: уменьшает объём коммуникации на узел по сравнению с 1D; более гибкая балансировка; коммуникация локализована в коммуникатор-строках/столбцах.
- Минусы: нужно планировать порядок шагов; может появиться передача пустых/очень разрежённых блоков; балансировка зависит от разреженности внутри блоков.
- Примерная оценка (адаптация dense-оценки): при равномерном распределении nnz коммуникация на узел порядка $\approx \frac{\text{nnz}(A)+\text{nnz}(B)}{\sqrt{P}}$, но для разрежённых матриц точный объём равен сумме nnz в блоках, которые действительно передаются.
3) 3D / репликация по третьему измерению
- Реплицируем данные по третьему измерению (распределяем вычисления по $r$ и реплицируем блоки): уменьшает объём коммуникации на узел в обмен на увеличение использования памяти (и начальной репликации).
- Плюсы: сильное снижение сетевого трафика при доступной памяти.
- Минусы: повышенная память; сложнее синхронизация и агрегирование результатов.
- Использовать, если память на узле позволяет и сеть — узкое место.
4) MapReduce-подобный подход (map: join по индексу $t$, reduce: суммирование по парам $(i,j)$)
- Map генерирует промежуточные пары $((i,j),a_{it}\cdot b_{tj})$ для каждой совпадающей $t$.
- Shuffle = все промежуточные пары: объём ≈ количество произведений (flops) — часто катастрофически велик.
- Комбинаторы (combiners) на мап-узлах критически важны: предварительная агрегация по ключам $(i,j)$ уменьшает shuffle.
- Подходит для очень больших кластеров с хорошими механизмами комбинирования и когда структура данных/алгоритма позволяет сильно сократить промежуточные ключи.
Балансировка нагрузки (рекомендации)
- Балансировать по ожидаемым флопсам, а не по числу строк/столбцов: для строки $i$ оценка работы ~ ${\sum }_{t:a_{it}\ne 0}\text{nnz}(B_{t,:})$. Аналогично для столбцов.
- Использовать предварительный анализ или семплинг: быстро подсчитать $\text{nnz}$-профили столбцов/строк и построить разбиение по весам.
- Для сложных схем применять гиперграф-партиционирование (Metis/PaToH/KaHIP) для минимизации числа пересечений (edge cut) и выравнивания нагрузки.
- При блочном разбиении динамическое переназначение «горячих» блоков (stealing) может помочь при неравномерности.
Снижение сетевых накладных расходов (практические приёмы)
- Репликация «малой» матрицы: если $\text{nnz}(B)$ мало и $\text{nnz}(B)\ll \frac{\text{nnz}(A)+\text{nnz}(B)}{\sqrt{P}}$, лучше разослать $B$ полностью (1D).
- Компрессия индексов и значений: дельта-кодирование индексов, использование run-length, бинарные/блоковые форматы для пропуска пустых участков.
- Передавать только ненулевые блоки; упаковывать блоки и отправлять батчами чтобы снизить накладные расходы на сетевые вызовы.
- Использовать RDMA/паразитную маршрутизацию и асинхронные non-blocking передачи, перекрывая коммуникацию с вычислением.
- Сжимать промежуточные данные (lossless) перед shuffle, если CPU позволяет.
- Использовать combiners/локальную агрегацию до shuffle в MapReduce-подходах.
Алгоритмические соображения для спарс-SPEM (SpGEMM)
- Локальные алгоритмы умножения: Gustavson (hash-таблица для аккумулирования результата строки) хорош при средней плотности; heap-основанные при специфических распределениях.
- Планировать размер блоков: слишком мелкие — увеличат overhead; слишком крупные — увеличат объем передаваемых пустых данных.
- Для очень разрежённых случаев часто выгоден outer-product (итерирование по $t$: умножать столбец/строку целиком), если можно эффективно передавать или реплицировать данные по $t$.
Пример рекомендуемого практического подхода (с учётом ограниченной пропускной способности сети)
1. Соберите статистику: $\text{nnz}$ по строкам/столбцам и приближённую оценку flops по индексам $t$.
2. Если одна матрица существенно меньше — реплицируйте её и делайте 1D по другой матрице.
3. Иначе выбирайте 2D блоковую стратегию (SUMMA-подобную), с:
- партиционированием блоков по весам nnz (не по равным числам строк),
- передачей только непустых блоков,
- батчингом и компрессией при отправке,
- асинхронной коммуникацией и перекрытием с вычислением.
4. Если память позволяет и сеть действительно узкий горлышко — использовать 3D (умеренная репликация) для уменьшения объёма передачи.
5. На MapReduce-платформах: реализуйте map-side combiners, минимизируйте ключи через локальную агрегацию, используйте эффективную партиционировку по $i$ или $(i,j)$, избегайте генерации всех отдельных произведений, если можно их локально суммировать.
Короткие формулы оценки коммуникации (ориентиры)
- 1D (репликация $B$): первоначальный трафик ≈ $\text{nnz}(B)\cdot (P-1)/P$.
- 2D равномерно: трафик на процесс ≈ $\mathcal{O}\left(\frac{\text{nnz}(A)+\text{nnz}(B)}{\sqrt{P}}\right)$ (адаптация dense-оценки; для sparse — сумма nnz реально передаваемых блоков).
- MapReduce shuffle ≈ число промежуточных пар ≈ $\text{flops}$ (без combiner’ов) — часто нежелательно.
Краткие практические советы
- Балансируйте по flops; используйте гиперграф-партиционирование при сильной нерегулярности.
- Передавайте и реплицируйте только «малые» или часто используемые срезы.
- Комбинируйте локальную агрегацию (combiners), компрессию и батчинг.
- Перекрывайте коммуникацию с вычислением и по возможности используйте асинхронную передачу / RDMA.
- Тестируйте на реальных паттернах разреженности и подбирайте блоки/число реплик эмпирически.
Если хотите, могу предложить конкретную конфигурацию (число блоков/реплик/оценку трафика) для ваших размеров $m,k,n$, $\text{nnz}(A)$, $\text{nnz}(B)$ и числа узлов/полосы сети — пришлите эти параметры.