Источники конфликтов и задержек
- Ограничение памяти / пропускной способности:
- Операционная нагрузка умножения матриц $2n^3$ FLOP против объёма передачи данных. По roofline: производительность $P\le \min (P_{peak},\text{AI}\cdot BW)$, где $\text{AI}$ — арифметическая интенсивность, $BW$ — пропускная способность памяти.
- Теоретический нижний предел перемещений данных (Hong–Kung): $\Omega \left(\frac{n^3}{\sqrt{M}}\right)$ при размере быстрого буфера $M$.
- Кэш-конфликты и отсутствие локальности:
- Конфликтные промахи из-за ассоциативности и размера линий; несоответствующее размещение строк/столбцов (row-major vs column-major) приводит к плохой пространственной/временной локальности.
- Кэш-полосы и вытеснение при работе с большими блоками (thrashing).
- Коэрентность и межъядерные конфликты:
- Трафик протокола когерентности (invalidate/upgrade) при параллельной записи — особенно при ложном совместном использовании (false sharing).
- Нестационарное распределение страниц (NUMA) — задержки при доступе к чужой памяти.
- TLB и страничные прерывания:
- Много промахов TLB при больших матрицах; overhead при обслуживании страниц.
- Тонкие аппаратные пределы:
- Ограничение количества одновременных незавершённых обращений (MSHR), ограниченная очередь загрузки/записи, store buffers.
- Pipeline stalls из‑за зависимостей данных, ненулевой latency для FMA, branch mispredicts (нечасто в GEMM) и недостаточная векторизация/использование регистров.
- Синхронизация и балансировка нагрузки:
- Затраты на барьеры, атомарные операции, неравномерное распределение работы между потоками.
Аппаратные оптимизации (что может сделать HW/микроархитектура)
- Увеличить пропускную способность памяти и количество MSHR; улучшить HW prefetcher для стрид-паттернов, предсказание блоков при GEMM.
- Бóльшие, более ассоциативные кэши или иерархия с малой латентностью для микрокернела; поддержка non‑inclusive / way‑partitioning для уменьшения вытеснений.
- Поддержка крупнопроцессорных инструкций: шире SIMD, FMA, более регистров — повышает ILP и уменьшает обращений к памяти.
- Поддержка huge pages / superpages и увеличенный TLB; аппаратная поддержка атомиков и барьеров с низкой задержкой.
- QoS/partitioning (CAT) для выделения доли кэша потокам/процессам и уменьшения взаимных вытеснений.
- Наличие программируемого scratchpad (software-managed local store) для блокирования/упаковки данных.
Программные оптимизации (практические приёмы)
- Блочная (tiling) и многоуровневая блокировка:
- Подбор размеров блоков для уровней кэша: для блока размера $b$ в памяти элементов размера $s$ байт требуемое место примерно $3b^{2}s\le C$ (для хранения блоков $A$, $B$, $C$ в кэше). Т.е. выбирать $b$ так, чтобы блоки L1/L2/L3 уместились:
$3b^{2}s\le C_{\text{target}}$.
- Использовать трёхуровневую стратегию: крупные блоки для L3, средние для L2, маленькие для L1 + микрокернел для регистров.
- Пэкинг (packing):
- Перепаковывать блоки $A$ и $B$ в плотные буферы с правильной выравниванием для непрерывного чтения и лучшей предсказуемости prefetcher'а.
- Векторизация и микрокернелы:
- Сконструировать маленький высокооптимизированный микрокернел (GEMM micro-kernel) использующий SIMD и FMA, минимизирующий загрузки/выгрузки регистров.
- Плоское развёртывание циклов (unrolling) внутри микрокернела, чтобы скрывать latency.
- Предвыборка и non-temporal stores:
- Software prefetch с подобранным расстоянием; для больших итоговых блоков использовать non-temporal stores чтобы избежать загрязнения кэша.

- Избегание false sharing:
- Паддинг структур/строк/буферов до размера линии кэша $L$ байт, либо распределение по-thread частичных результатов и финальное редуцирование.
- NUMA и привязка потоков:
- Привязка потоков к ядрам и аллокация памяти в локальной области (first touch); распределение работы так, чтобы минимизировать межузловые обращения.
- Снижение синхронизации:
- Минимизировать глобальные барьеры; использовать локальные накопители и иерархические редукции; распределять работу равномерно (static scheduling по блокам).
- TLB и страницы:
- Использовать huge pages, если доступно, чтобы уменьшить TLB misses.
- Использовать проверенные библиотеки:
- BLIS/OpenBLAS/Intel MKL/Libxsmm — имеют tuned blocking, packing, векторизацию и управление потоками.
Методическая оценка и подбор параметров
- Оценить, на что ограничение: вычисления или память, по roofline: вычислительная граница $P_{peak}$ и память $BW$. Вычислить $\text{AI}=\frac{2n^3}{\text{bytes\_transferred}}$ и сравнить с $P_{peak}/BW$.
- Подобрать блоки так, чтобы увеличить $\text{AI}$ и уменьшить пропускную зависимость. Экспериментально подобрать $b$ и параметры микрокернела (часто $b$ от десятков до сотен, зависит от $C_{L1},C_{L2}$).
Краткая сводка
- Основные узкие места: память/кэш, коэрентность, TLB, латентности запросов и синхронизация.
- Аппаратно: увеличить BW, MSHR, улучшить prefetch и SIMD/регистры, QoS/partitioning.
- Программно: многослойная блокировка + packing, высокооптимизированный микрокернел (SIMD/FMA), prefetch, avoid false sharing, NUMA‑aware allocation и использование tuned BLAS.