# Оптимизация параллельных систем: от топологии кэша до модели Roofline

Источник: https://www.youtube.com/watch?v=Mhdny2JNhmc
Канал: Stanford Online
Опубликовано: 17.09.2024

---

Шестая лекция стэнфордского курса CS149 посвящена глубокому анализу оптимизации производительности параллельных систем. Лектор подробно разбирает, почему современная разработка сталкивается с жесткими ограничениями пропускной способности памяти, и как инженерам приходится переходить от простого балансирования нагрузки к минимизации коммуникационных издержек. Центральной темой повествования становится концепция арифметической интенсивности программ и визуальная диагностическая модель Roofline.

## 🔌 Архитектура межъядерных связей: от колец до кроссбаров
[[JUMP:01:37]]

В рамках курса CS149 до сих пор предполагалось, что все процессоры подключены к некоторой системе с общей памятью. Однако физическая реализация единого адресного пространства на аппаратном уровне крайне сложна. Когда несколько ядер создают локальные копии данных в своих кэшах и пытаются одновременно выполнить запись по одному адресу, возникает серьезная проблема поддержания когерентности, о деталях которой разработчикам необходимо постоянно помнить.

Современные многоядерные чипы используют сложные внутренние топологии сетей. Например, в архитектурах Intel процессоры и сегменты кэша L3 соединены кольцевой шиной (ring). Любой запрос на чтение или запись отправляется по этому кольцу, причем каждое ядро имеет две точки контакта с шиной для оптимизации маршрутизации по часовой стрелке, что минимизирует задержки и предотвращает взаимные блокировки.

Альтернативный подход демонстрирует исторический процессор UltraSPARC, разработанный компанией Sun (впоследствии поглощенной Oracle). Этот 8-ядерный многопоточный чип использовал полносвязный коммутатор — кроссбар (crossbar switch, CCX), где каждое ядро физически соединено со всеми остальными. Подобная топология требует огромного количества соединений, пропорционального квадрату числа ядер $N^2$, из-за чего на кремниевом кристалле площадь межсоединений сравнима с площадью самих вычислительных ядер. Ситуация усложняется на двухсокетных материнских платах, где обращение к памяти соседнего процессора через внешние дорожки платы занимает значительно больше времени, формируя неоднородный доступ к памяти (NUMA).



## ✉️ Парадигма Message Passing: явный обмен вместо общих иллюзий
[[JUMP:07:44]]

Для упрощения рассуждений о коммуникациях полезно рассмотреть модель передачи сообщений (message passing), которая повсеместно применяется в распределенных веб-системах. В отличие от общей памяти, здесь нет единого адресного пространства: у каждого потока или узла интернета есть своя изолированная память. Адрес X в пространстве первого потока не имеет никакого отношения к адресу X во втором.

Единственный способ обменяться данными в такой системе — явно отправить сообщение с уникальным идентификатором (ID) и принять его на другой стороне. Лектор привело наглядную аналогию:

> Общая память похожа на доску объявлений, где любой может оставить или прочитать запись без спроса. Передача сообщений больше напоминает отправку бумажной почты в конверте, где отправитель должен упаковать данные и указать точный адрес получателя.

Конкретные механизмы под капотом могут различаться (TCP/IP, UDP или специализированные сетевые протоколы), но концептуальная суть неизменна — данные копируются из одного изолированного пространства в другое.

## 👻 Сеточный решатель и феномен «призрачных строк»
[[JUMP:11:29]]

Чтобы проиллюстрировать работу модели передачи сообщений, лектор предлагает разобрать красно-черный сеточный решатель из первого домашнего задания, но в условиях работы на кластере без общей памяти. Теперь вместо одного большого массива данные распределяются по отдельным узлам, и каждый поток владеет лишь своей частью сетки. Потоки не могут напрямую прочитать значения из соседней памяти.

Для расчета граничных элементов потоку необходимы значения с соседнего узла. Чтобы решить эту проблему, на каждом узле выделяется избыточный буфер памяти — так называемые «призрачные строки» или «призрачные ячейки» (ghost rows / ghost cells), популярные в научных вычислениях. Код каждого воркера выделяет массив, размер которого на две строки больше объема его непосредственной ответственности.



Интересной особенностью такой реализации является полное отсутствие явных блокировок (locks) и барьеров (barriers), которые применялись в среде с общей памятью. Синхронизация встроена в сам шаблон коммуникации. Потоки отправляют свои локальные разности (diff) нулевому потоку, который производит финальный расчет сходимости и рассылает булев флаг завершения работы. Поскольку общих данных нет, взаимное исключение не требуется, а ожидание сообщений автоматически выполняет роль барьера. Индексация массива при этом становится относительной для каждого локального фрагмента.

## 🛑 Блокирующие вызовы и капкан взаимной блокировки
[[JUMP:24:18]]

При использовании стандартных блокирующих функций `send` и `receive` отправка завершается только тогда, когда принимающая сторона подтверждает получение и копирует данные в свои переменные. Если в распределенной системе или на уровне чипа происходят сбои, надежность и повторные попытки отправки обычно делегируются аппаратному или системному уровню. Лектор иронизирует, что если в 16-ядерном процессоре сообщение не может дойти до кэша L3 из-за физической ошибки, инженерам остается только выбросить этот компьютер.

Однако в представленном базовом коде скрывается фатальная алгоритмическая ошибка — классический deadlock. Поскольку все потоки одновременно вызывают блокирующий `send` своим соседям до того, как объявят `receive`, выполнение полностью останавливается: каждый воркер бесконечно ждет, пока сосед примет его пакет.

Исправить эту уязвимость в рамках блокирующего ввода-вывода можно следующими методами:

* Разделение потоков по четности строк (parities): четные строки сначала отправляют данные назад, а нечетные — сначала принимают их спереди.
* Переход к асинхронным коммуникациям: функции `send` и `receive` возвращают управление немедленно, предоставляя программе специальный дескриптор или трекинг-номер (handle) для последующей проверки статуса.

Асинхронный подход снижает риск мертвых блокировок, но усложняет контроль конкурентности. Если изменить данные в исходной переменной до того, как библиотека реально скопирует их в сеть, адресат получит некорректную информацию. Это похоже на смену содержимого посылки, которую вы уже выставили на крыльцо для курьера UPS. Потокам приходится либо организовывать циклы активного ожидания (busy wait), либо использовать механизмы обратного вызова (callbacks).

## 📐 Отношение геометрии к производительности: снижение истинной коммуникации
[[JUMP:45:42]]

Всю сетевую и межъядерную активность лектор предлагает разделять на два фундаментальных типа:

* Истинная (inherent) коммуникация — обусловлена самой природой алгоритма, без нее невозможно получить правильный математический результат.
* Артефактная (artifactual) коммуникация — возникает из-за специфики физического устройства компьютера (размера кэш-линий, фиксированных пакетов сети и т.д.).

Математический анализ разбиения сетки размером $N \times N$ на $P$ процессоров показывает разительные отличия в эффективности разных схем распределения нагрузки. При нарезке сетки на горизонтальные полосы (interleaved или chunked assignment) каждый процессор выполняет $N^2 / P$ работы, но объем необходимых коммуникаций составляет $2N$ для сплошных кусков или резко возрастает до $2N^2$ при чередовании строк. В результате показатель арифметической интенсивности (объем вычислений на единицу переданных данных) падает, делая систему критически зависимой от пропускной способности памяти.



Кардинально улучшить ситуацию позволяет тайлинг (плиточное или блочное распределение). Если разбить сетку на квадратные блоки, то отношение площади (вычислений) к периметру (коммуникациям) становится максимальным. В этом случае объем передаваемых данных для каждого воркера сокращается до $4N / \sqrt{P}$. Арифметическая интенсивность возрастает с $N/P$ до $N/\sqrt{P}$. На 16-ядерной машине это дает четырехкратный выигрыш, позволяя ядрам работать на полную мощность при значительно меньших требованиях к пропускной способности шины. На шутливое предложение студента использовать круглые области из-за идеального геометрического соотношения лектор возражает, что сложность расчетов на стыках кругов нивелирует всю выгоду.

## 🧠 Борьба с артефактами: кэш-блокинг и слияние циклов
[[JUMP:52:35]]

Артефактная коммуникация наглядно проявляется при анализе работы процессора с кэш-линиями. Допустим, размер кэш-линии составляет 4 элемента, а весь кэш вмещает 24 элемента (6 линий). При последовательном горизонтальном обходе широкой матрицы процессор быстро вытесняет старые строки из кэша. Возвращаясь к началу следующей строки, он обнаруживает, что нужные верхние соседи уже стерты, и снова генерирует дорогостоящие промахи кэша (cache misses) на каждой ячейке.

Чтобы побороть это, применяется метод кэш-блокинга (cache blocking) — изменение порядка обхода данных, например, зигзагообразным паттерном. Это позволяет возвращаться к элементам до того, как они покинут локальную память, поднимая интенсивность с 4 выходов на 3 линии до 6 выходов на 2 линии. По мнению лектора, кэш-блокинг — это важнейшая техника для любой современной работы с тензорами и матрицами, определяющая скорость выполнения операций.

Другой пример неэффективности — слепое последовательное применение библиотечных функций векторного анализа (например, в стиле NumPy). Код вида `A = B + C; D = A * E` заставляет систему выполнять промежуточные записи и чтения из памяти с низкой арифметической интенсивностью, равной всего 1/3. Слияние циклов (loop fusion) в одну общую инструкцию позволяет удерживать промежуточные результаты в регистрах процессора, поднимая арифметическую интенсивность до 3/5. Подобные трансформации сегодня автоматически выполняют JIT-компиляторы фреймворков глубокого обучения, таких как TensorFlow и PyTorch.

## ⏳ Контенция и метафора студенческих очередей
[[JUMP:1:03:33]]

Помимо объемов данных, критическое значение имеет время их запроса. Контенция (contention) представляет собой конфликт за доступ к общему ресурсу. Лектор иллюстрирует это явление метафорой своих консультационных часов (office hours): если все студенты приходят строго к началу приема, образуется огромная неэффективная очередь, и опоздавшие тратят массу времени на бесплодное ожидание. Система записи по времени (appointments) взамен живой очереди решает эту проблему, гарантируя обслуживание за фиксированные 10 минут.

В компьютерных системах контенция возникает, когда множество ядер одновременно запрашивают шину памяти. Даже при хороших средних показателях локальности одновременный шквал запросов парализует конвейеры инструкций, делая память визуально гораздо более медленной.

Для борьбы с этим эффектом инженеры используют два ключевых паттерна:

* Репликация данных и разделение очередей задач.
* Рандомизация времени отправки запросов (по аналогии со случайным распределением выезда автомобилей на загруженное шоссе для демпфирования пиковых нагрузок).

## 📊 Модель Roofline: визуальный компас оптимизатора
[[JUMP:1:08:45]]

Когда разработчик недоволен производительностью кода, ему необходимы объективные метрики. Профайлеры вроде Intel VTune помогают определить характер узких мест, однако для комплексной оценки применяется двухмерный график Roofline («линия крыши»).



Параметры осей графика устроены следующим образом:

* Ось X (абсцисс) отображает операционную (арифметическую) интенсивность, измеряемую в количестве флопсов на байт (flops per byte). Левая зона соответствует слабой интенсивности (много обращений к памяти), правая — высокой вычислительной нагрузке.
* Ось Y (ординат) показывает реальную производительность системы в гигафлопсах (gigaflops).

График имеет характерную форму крыши дома, четко разграничивая два режима работы:

1.  **Memory-bound (ограничение памятью)** — наклонный скат крыши слева. Процессор не может получать данные достаточно быстро, его вычислительные блоки простаивают, а производительность жестко лимитируется пропускной способностью шины (ее значение задает угол наклона).
2.  **Compute-bound (ограничение вычислениями)** — плоский горизонтальный потолок справа. Арифметические блоки загружены на 100%, и система упирается в максимальную тактовую частоту и параллельные ресурсы ядер.

При переходе на новый чип с увеличенной вычислительной мощностью (например, в 4 раза выше) горизонтальный потолок взлетает вверх, однако наклон ската памяти остается прежним. Это означает, что приложению требуется в 4 раза большая арифметическая интенсивность, чтобы просто не свалиться в зону простоя из-за нехватки данных. Лектор подытоживает, что вся суть оптимизации сводится к смещению точки программы вправо и вверх по графику с помощью блокинга и слияния циклов ради достижения максимального аппаратного плато.