Команда Spring АйО подготовила перевод статьи в которой автор разбирает, где параллельные стримы действительно масштабируются, а где создают накладные расходы, конкуренцию за ресурсы и иллюзию производительности. Коротко: сначала аналитика и измерения, потом — параллелизм.

К 2002 году методы, которые разработчики чипов использовали для достижения экспоненциального роста производительности, начали исчерпываться. Существенное повышение тактовой частоты стало непрактичным по ряду причин, включая энергопотребление и выделение теплоты, а попытки выполнять больше операций за такт (instruction-level parallelism) также приблизились к пределу эффективности.

Закон Мура предсказывает, что количество транзисторов на кристалле удваивается примерно каждые два года. Когда в 2002 году разработчики столкнулись с «частотной стеной», это произошло не потому, что закон Мура перестал действовать — количество транзисторов продолжало стабильно расти по экспоненте. Однако возможность использовать этот растущий транзисторный бюджет для создания более быстрых ядер была исчерпана, и инженеры начали направлять его на размещение большего числа ядер на одном кристалле.

Следующая диаграмма (взята из статьи Херба Саттера «Бесплатный обед закончился») иллюстрирует эту тенденцию на основе данных о процессорах Intel, представленных в логарифмическом масштабе. Верхняя (прямая) линия отражает экспоненциальный рост числа транзисторов, тогда как линии, соответствующие тактовой частоте, тепловыделению и параллелизму на уровне команд, демонстрируют явное выравнивание около 2002 года.

Большее количество ядер может повысить энергоэффективность (неиспользуемые ядра можно отключать независимо), но это не обязательно означает лучшую производительность программ — если только все ядра не загружены полезной работой. На самом деле современные процессоры предоставляют не столько ядер, сколько позволял бы закон Мура — в значительной степени потому, что современное программное обеспечение не способно эффективно использовать их без чрезмерных затрат.

От конкурентности к параллелизму

На протяжении большей части истории вычислительной техники цель конкурентности (Concurrency) оставалась неизменной — повышение производительности за счёт увеличения загрузки процессора, — однако методы её достижения (и критерии оценки эффективности) менялись. В эпоху одноядерных систем конкурентность в основном сводилась к асинхронности: возможности передать управление процессором, пока активность ждёт завершения операции ввода-вывода. Асинхронность улучшала как отзывчивость (интерфейс не «зависал» во время фоновой работы), так и пропускную способность (другие задачи могли использовать процессор, пока шла задержка на ввод-вывод). В некоторых моделях конкурентности (например, в акторах или CSP — Communicating Sequential Processes) модель напрямую определяла архитектуру программы, но в большинстве случаев (и к лучшему, и к худшему) конкурентность применялась точечно, ради повышения производительности.

С переходом к многоядерным системам основное применение конкурентности стало заключаться в разбиении нагрузки на независимые, крупные задачи — например, пользовательские запросы — с целью повышения пропускной способности за счёт параллельной обработки нескольких запросов. В этот период в стандартной библиотеке Java появились инструменты вроде пулов потоков, семафоров и объектов Future, хорошо подходящие для такой задачно-ориентированной конкурентности.

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

Комментарий от эксперта сообщества Spring АйО, Михаила Поливахи:

Это кстати причина, почему часто нейросети тренируют на GPU чипах, таких как H100 например - GPU чипы имеют огромное количество ядер, которые способны выполнять довольно простые (по сравнению с традиционными CPU) инструкции, но в огромных количествах. Это, собстве��но, и нужно в процессе обучения AI.

К сожалению, термины «конкурентность» и «параллелизм» не имеют строго устоявшихся определений и часто (ошибочно) используются как синонимы. Исторически конкурентность описывала свойство программы — степень её организации как взаимодействия нескольких вычислительных активностей, — тогда как параллелизм являлся свойством исполнения программы и отражал, насколько действия действительно происходят одновременно. (В этом смысле конкурентность — это потенциальный параллелизм.) Такое различие было полезно, когда настоящая параллельность оставалась теоретическим понятием, но со временем оно утратило актуальность.

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

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

Параллелизм

Хотя механизмы параллелизма зачастую достаточно просты, наибольшая трудность заключается в понимании, когда его следует применять. Параллелизм — это строго оптимизация: осознанный выбор использовать больше ресурсов для выполнения вычислений с надеждой получить результат быстрее. При этом всегда остаётся возможность выполнить ту же задачу последовательно. К сожалению, использование большего количества ресурсов не гарантирует, что результат будет получен быстрее — или даже так же быстро. И если параллелизм не приносит выг��ды (или приводит к отрицательному эффекту) при увеличении потребления ресурсов, его не стоит применять. Конечно, отдача от параллелизма сильно зависит от ситуации, поэтому универсального ответа не существует. Но у нас есть инструменты, позволяющие оценить, будет ли параллелизм эффективен в конкретной задаче: аналитика, измерения и требования к производительности.

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

Мера эффективности параллелизма, называемая ускорением (speedup), — это просто отношение времени выполнения параллельной версии к времени выполнения последовательной. Выбор в пользу параллелизма (при условии, что он даёт ускорение) — это осознанное предпочтение времени над использованием процессора и энергопотреблением. Параллельное выполнение всегда требует больше работы, чем последовательное, поскольку помимо самой задачи необходимо ещё её декомпозировать, создать и управлять задачами для подзадач, распределить выполнение и дождаться их завершения, а затем объединить результаты. Таким образом, параллельное выполнение всегда стартует с «отставанием» по сравнению с последовательным и надеется компенсировать этот стартовый дефицит за счёт масштабного выигрыша.

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

Использование параллелизма

Не все задачи одинаково хорошо поддаются параллелизации. Рассмотрим следующий пример: дана функция f, которую мы считаем ресурсоёмкой для вычисления. Определим функцию g следующим образом:

g(0) = f(0)  

g(n) = f( g(n-1) ), для n > 0

Можно было бы попытаться реализовать параллельный алгоритм для вычисления g и измерить его ускорение, но в данном случае это не требуется — достаточно взглянуть на саму задачу, чтобы понять: она принципиально последовательна. Это становится особенно очевидно, если немного переписать определение g(n):

g(n) = f( f( ... f(0) ... ) ), где f применяется n раз

В такой записи ясно видно, что вычисление g(n) невозможно начать, пока не будет завершено вычисление g(n-1). На диаграмме зависимостей для вычисления g(4), приведённой на следующем рисунке, видно, что каждое значение g(n) зависит от предыдущего g(n-1).

Может возникнуть соблазн предположить, что проблема заключается в рекурсивной природе определения g(n), но это не так. Рассмотрим немного другую задачу — вычисление функции h(n):

h(0) = f(0)  

h(n) = f(n) + h(n-1)

Если реализовать её очевидным способом, получится граф зависимостей, аналогичный приведённому на следующем рисунке, где каждое значение h(n) зависит от h(n-1).

Однако если переписать определение h(n) по-другому, сразу становится ясно, что эту задачу можно эффективно параллелизовать. Все слагаемые можно вычислить независимо, а затем сложить (что само по себе тоже допускает параллельное выполнение):

h(n) = f(0) + f(1) + ... + f(n)

В результате получается граф зависимостей данных, подобный приведённому на рисунке 4, в котором каждое значение f(i) может быть вычислено независимо от других.

Эти примеры показывают две важные вещи: во-первых, внешне похожие задачи могут сильно различаться по степени пригодности к параллелизации; во-вторых, «очевидная» реализация задачи, допускающей параллелизм, может вовсе этот параллелизм не использовать. Чтобы получить хоть какое-то ускорение, необходимы оба условия.

Разделяй и властвуй

Стандартный приём для реализации параллелизма — это рекурсивная декомпозиция, или стратегия «разделяй и властвуй». При таком подходе задача многократно делится на подзадачи до тех пор, пока они не станут достаточно мелкими, чтобы было эффективнее решить их последовательно; затем подзадачи решаются параллельно, а частичные результаты объединяются в общий итог.

Следующий листинг демонстрирует типичное решение в стиле divide-and-conquer на псевдокоде с использованием гипотетического примитива CONCURRENT для параллельного выполнения.

R solve(Problem<R> problem) {
    if (problem.isSmall())
        return problem.solveSequentially();
    R leftResult, rightResult;

    CONCURRENT {
        leftResult = solve(problem.leftHalf());
        rightResult = solve(problem.rightHalf());
    }

    return problem.combine(leftResult, rightResult);
}

Рекур��ивная декомпозиция привлекательна своей простотой (особенно при работе со структурами данных, уже имеющими рекурсивную природу, такими как деревья). Параллельный код, подобный приведённому в листинге выше, хорошо переносим между различными вычислительными средами: он эффективно работает как на одном ядре, так и на множестве, и при этом не требует сложной координации доступа к разделяемому изменяемому состоянию — потому что такого состояния просто нет. Разделение задачи на подзадачи и организация доступа каждой задачи только к данным своей подзадачи, как правило, не требуют координации между потоками.

Соображения производительности

Используя листинг кода выше в качестве модели, можно проанализировать условия, при которых параллелизм может дать преимущество. Алгоритм «разделяй и властвуй» добавляет два этапа — разбиение задачи и объединение частичных результатов — и каждый из них может быть более или менее благоприятным для параллельного выполнения. Ещё один важный фактор — эффективность самих примитивов параллелизма, таких как гипотетический механизм CONCURRENT из псевдокода в листинге выше. Кроме того, на производительность влияют свойства самого набора данных: его размер и локальность в памяти. Рассмотрим все эти условия по порядку.

Некоторые задачи, например функция g(n) из раздела «Использование параллелизма», вообще не допускают декомпозиции. Но даже если декомпозиция возможна, она может быть затратной. (Минимум, что требуется, — сформировать описание подзадачи.) Например, шаг разбиения в алгоритме быстрой сортировки требует выбора опорного элемента (pivot point), что стоит O(n) от размера задачи, так как необходимо просмотреть и, возможно, изменить все данные. Это значительно дороже, чем разбиение в задаче «найти сумму элементов массива», где операция разбиения — это O(1): «найти среднее значение между начальным и конечным индексами». И даже если декомпозиция эффективна, при сильном неравенстве размеров подзадач параллелизм может практически не использоваться.

Аналогично, при решении подзадач необходимо объединить их результаты. Если задача — «удалить дубликаты», шаг объединения требует слияния двух множеств, и при необходимости получить плоское представление результат — это снова O(n). С другой стороны, если задача — «найти сумму массива», то объединение — это всего лишь сложение двух чисел, то есть O(1).

Управление задачами, выполняемыми параллельно, само по себе может быть источником потерь эффективности — из-за задержек при передаче данных между потоками или из-за конкуренции за доступ к разделяемым структурам данных. Фреймворк fork-join, добавленный в Java SE 7 для работы с мелкими, ресурсоёмкими вычислениями, был разработан специально для минимизации таких потерь. Библиотека java.util.stream использует fork-join для реализации параллельного выполнения.

Наконец, необходимо учитывать сам набор данных. Если он слишком мал, трудно получить ускорение из-за издержек, связанных с запуском параллельных вычислений. Если же данные имеют плохую локальность в памяти (например, графы с большим количеством указателей вместо компактных массивов), то на современных системах, ограниченных пропускной способностью памяти, параллельное выполнение приведёт лишь к тому, что потоки будут простаивать в ожидании данных из кэша/RAM, а не выполнять вычисления быстрее.

Каждый из этих факторов может «съесть» предполагаемое ускорение — а в некоторых случаях не только свести его на нет, но даже привести к замедлению.

Закон Амдала

Закон Амдала описывает, как последовательная часть вычислений ограничивает возможное ускорение от параллелизации. Почти любая задача содержит долю работы, которую невозможно выполнить параллельно — её называют последовательной долей (serial fraction). Например, если вы копируете данные из одного массива в другой, сам процесс копирования может быть распараллелен, но выделение памяти под целевой массив — операция по своей природе последовательная — должно завершиться до начала копирования.

На следующем рисунке показаны последствия действия закона Амдала. Разные кривые иллюстрируют максимально возможное ускорение, допускаемое законом Амдала, в зависимости от количества доступных процессоров, при различных долях параллельности (это дополняющая величина к последовательной доле).

Если, к примеру, параллельная доля составляет 0,5 (то есть половина задачи должна выполняться последовательно), и у нас в распоряжении бесконечное число процессоров, закон Амдала говорит, что наилучшее возможное ускорение — 2x. Это логично: даже если за счёт параллелизации мы сведём стоимость параллельной части к нулю, у нас всё равно остаётся половина задачи, которую нужно решать последовательно.

Модель, заложенная в закон Амдала — что некоторая часть работы полностью последовательна, а остальная идеально параллелизуема — чрезмерно упрощена. Тем не менее, она остаётся полезной для понимания факторов, сдерживающих параллелизм. Умение выявлять и сокращать последовательную долю — ключевой элемент при создании более эффективных параллельных алгоритмов.

Закон Амдала можно интерпретировать и по-другому: если у вас машина с 32 ядрами, то каждая тактовая единица, потраченная на настройку параллельного вычисления, — это 31 единица, не использованная для решения самой задачи. А если вы всего лишь разделили задачу на две части, то каждый такт теряется уже на 30 ядрах. Только когда удаётся выделить достаточно работы, чтобы загрузить все процессоры, система начинает работать в полную силу — и если достичь этого состояния не удаётся достаточно быстро (или удерживать его достаточно долго), получить заметное ускорение будет крайне трудно.

Заключение

Параллелизм — это компромисс: использование большего количества вычислительных ресурсов в надежде получить ускорение. Хотя в теории задачу можно ускорить в N раз при использовании N ядер, на практике достичь этого удаётся далеко не всегда. На эффективность параллелизма влияют: сама задача, алгоритм её решения, механизмы среды выполнения, обеспечивающие декомпозицию задач и планирование, а также размер и локальность данных в памяти.

Присоединяйтесь к русскоязычному сообществу разработчиков на Spring Boot в телеграм — Spring АйО, чтобы быть в курсе последних новостей из мира разработки на Spring Boot и всего, что с ним связано.