Хабрахабр

[Перевод] Удивительная производительность параллельных алгоритмов C++17. Миф или Реальность?

Добрый вечер!

От нашего курса «Разработчик C++» предлагаем вам небольшое и интересное исследование про параллельные алгоритмы.

Поехали.

В этой статье, я хочу рассмотреть STL алгоритм, который естественным образом раскрывает идею независимых вычислений. С появлением параллельных алгоритмов в C++17, вы с легкостью можете обновить свой “вычислительный” код и получить выгоду от параллельного выполнения. А может больше? Можно ли ожидать 10-кратного ускорения при наличии 10-ядерного процессора? Поговорим об этом. Или меньше?

Введение в параллельные алгоритмы

C++17 предлагает параметр политики выполнения для большинства алгоритмов:

  • sequenced_policy — тип политики выполнения, используется в качестве уникального типа для устранения перегрузки параллельного алгоритма и требования того, что распараллеливание выполнения параллельного алгоритма — невозможно: соответствующий глобальный объект — std::execution::seq;
  • parallel_policy — тип политики выполнения, используемый в качестве уникального типа для устранения перегрузки параллельного алгоритма и указания на то, что распараллеливание выполнения параллельного алгоритма — возможно: соответствующий глобальный объект — std::execution::par;
  • parallel_unsequenced_policy — тип политики выполнения, используемый в качестве уникального типа для устранения перегрузки параллельного алгоритма и указания на то, что распараллеливание и векторизация выполнения параллельного алгоритма — возможны: соответствующий глобальный объект — std::execution::par_unseq;

Кратко:

  • используйте std::execution::seq для последовательного выполнения алгоритма;
  • используйте std::execution::par для параллельного выполнения алгоритма (обычно с помощью какой-либо реализации Thread Pool (пула потоков));
  • используйте std::execution::par_unseq для параллельного выполнения алгоритма с возможностью использования векторных команд (например, SSE, AVX).

В качестве быстрого примера вызовем std::sort параллельно:

std::sort(std::execution::par, myVec.begin(), myVec.end()); // ^^^^^^^^^^^^^^^^^^^ // политика выполнения

Обратите внимание, как просто добавить параметр параллельного выполнения в алгоритм! Но удастся ли добиться значительного улучшения производительности? Увеличит ли это скорость? Или есть случаи замедления?

Параллельный std::transform

В этой статье, я хочу обратить внимание на алгоритм std::transform, который потенциально может быть основой для других параллельных методов (наравне с std::transform_reduce, for_each, scan, sort...).

Наш тестовый код будет строиться по следующему шаблону:

std::transform(execution_policy, // par, seq, par_unseq inVec.begin(), inVec.end(), outVec.begin(), ElementOperation);

Предположим, что у функции ElementOperation нет никаких методов синхронизации, в таком случае у кода есть потенциал параллельного выполнения или даже векторизации. Каждое вычисление элемента независимо, порядок не имеет значения, поэтому реализация может порождать несколько потоков (возможно в пуле потоков) для независимой обработки элементов.

Я бы хотел поэкспериментировать со следующими вещами:

  • размер векторного поля — большое или маленькое;
  • простое преобразование, которое тратит бОльшую часть времени на доступ к памяти;
  • больше арифметических (ALU) операций;
  • ALU в более реалистичном сценарии.

Как видите, я хочу не только протестировать количество элементов, которые “хороши” для использования параллельного алгоритма, но и ALU-операции, которые занимают процессор.
Прочие алгоритмы, такие как сортировка, накопление (в виде std::reduce) также предлагают параллельное выполнение, но и требуют больше работы для вычисления результатов. Поэтому будем считать их кандидатами для другой статьи.

Примечание об бенчмарках

8 — поскольку это единственная реализация в популярной реализации компилятора/STL на текущий момент (Ноябрь, 2018) (GCC в пути!). Для своих тестов я использую Visual Studio 2017, 15. Более того, я сосредоточился только на execution::par, так как execution::par_unseq недоступна в MSVC (работает аналогично execution::par).

Есть два компьютера:

  • i7 8700 — ПК, Windows 10, i7 8700 — тактовая частота 3.2 GHz, 6 ядер/12 потоков (Hyperthreading);
  • i7 4720 — Ноутбук, Windows 10, i7 4720, тактовая частота 2.6GHz, 4 ядра/8 потоков (Hyperthreading).

Код скомпилирован в x64, Release more, автовекторизация включена по-умолчанию, также я включил расширенный набор команд (SSE2) и OpenMP (2.0).

Код находится в моем github’е: github/fenbf/ParSTLTests/TransformTests/TransformTests.cpp

0) я использую параллельность только для циклов: Для OpenMP (2.

#pragma omp parallel for
for (int i = 0; ...)

Запускаю код 5 раз и смотрю на минимальные результаты.

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

А вот свежий доклад Билла О’Нила с CppCon 2018 (Билл реализовал Parallel STL в MSVC). Более подробно о MSVC реализации можно прочитать в этом посте.

Ну что ж, начнем с простых примеров!

Простое преобразование

Это может быть копирование или умножение элементов. Рассмотрим случай, когда вы применяете очень простую операцию к входному вектору.

Например:

std::transform(std::execution::par, vec.begin(), vec.end(), out.begin(), [](double v)
);

В моем компьютере 6 или 4 ядра… могу ли я ожидать 4..6-кратного ускорение последовательного выполнения? Вот мои результаты (время в миллисекундах):

Операция

Размер вектора

i7 4720 (4 ядра)

i7 8700 (6 ядер)

execution::seq

10k

0.002763

0.001924

execution::par

10k

0.009869

0.008983

openmp parallel for

10k

0.003158

0.002246

execution::seq

100k

0.051318

0.028872

execution::par

100k

0.043028

0.025664

openmp parallel for

100k

0.022501

0.009624

execution::seq

1000k

1.69508

0.52419

execution::par

1000k

1.65561

0.359619

openmp parallel for

1000k

1.50678

0.344863

На более быстрой машине можем увидеть, что понадобится около 1 миллиона элементов, чтобы заметить улучшение производительности. С другой стороны, на моем ноутбуке все параллельные реализации были медленнее.

Таким образом, заметить какое-либо значительное улучшение производительности при помощи таких трансформаций сложно, даже при увеличении количества элементов.

Почему же?

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

Чтение и запись переменной в памяти занимает около 2-3 тактов, если она кэшируется, и несколько сотен тактов, если не кэшируется.
https://www.agner.org/optimize/optimizing_cpp.pdf

Можно грубо заметить, что если ваш алгоритм зависит от памяти, то не стоит ожидать улучшения производительности с параллельным вычислением.

Больше вычислений

Поскольку пропускная способность памяти крайне важна и может влиять на скорость вещей… давайте увеличим количество вычислений, влияющих на каждый элемент.

Мысль в том, что лучше использовать циклы процессора, а не тратить время на ожидание памяти.

Для начала, я использую тригонометрические функции, например, sqrt(sin*cos) (это условные вычисления в неоптимальной форме, просто чтобы занять процессор).

Такое количество вычислений может покрыть задержку на доступ к памяти. Мы используем sqrt, sin и cos, которые могу занять ~20 на sqrt и ~100 на тригонометрическую функцию.

Более подробно о задержках команд написано в прекрасной статье Perf Guide от Агнера Фога.

Вот бенчмарк-код:

std::transform(std::execution::par, vec.begin(), vec.end(), out.begin(), [](double v) { return std::sqrt(std::sin(v)*std::cos(v)); }
);

И что же теперь? Можем ли мы рассчитывать на улучшение производительности по сравнении с предыдущей попыткой?

Вот некоторые результаты (время в миллисекундах):

Операция

Размер вектора

i7 4720 (4 ядра)

i7 8700 (6 ядер)

execution::seq

10k

0.105005

0.070577

execution::par

10k

0.055661

0.03176

openmp parallel for

10k

0.096321

0.024702

execution::seq

100k

1.08755

0.707048

execution::par

100k

0.259354

0.17195

openmp parallel for

100k

0.898465

0.189915

execution::seq

1000k

10.5159

7.16254

execution::par

1000k

2.44472

1.10099

openmp parallel for

1000k

4.78681

1.89017

Наконец-то мы видим неплохие числа 🙂

Для 1000 элементов (здесь не показанных), время параллельного и последовательного вычисления было схожи, поэтому для более 1000 элементов мы видим улучшение в параллельном варианте.

Для 100 тысяч элементов результат на более быстром компьютере почти в 9 раз лучше последовательной версии (аналогично для OpenMP версии).

Чего и стоило ожидать. В наибольшем варианте из миллиона элементов — результат быстрее в 5 или 8 раз.
Для таких вычислений я добился “линейного” ускорения, зависящего от количества ядер процессора.

Френель и трёхмерные векторы

Это популярный метод для генерации реалистичного освещения в трехмерных играх. В разделе выше я использовал “выдуманные” вычисления, но что насчет настоящего кода?
Давайте, решим уравнения Френеля, описывающие отражение и искривление света от гладкой, плоской поверхности.


Фото из Wikimedia

В качестве хорошего образца я нашел это описание и реализацию.

Об использовании библиотеки GLM

Я часто ей пользуюсь в своих OpenGl проектах. Вместо создания собственной реализации, я использовал библиотеку glm.

Ссылка на пакет. К библиотеке легко получить доступ через Conan Package Manager, поэтому им я тоже буду пользоваться.

Файл Conan:

[requires]
glm/0.9.9.1@g-truc/stable [generators]
visual_studio

и командная строка для установки библиотеки (она генерирует props-файлы, которые я могу использовать в проекте Visual Studio):

conan install . -s build_type=Release -if build_release_x64 -s arch=x86_64

Библиотека состоит из заголовка, поэтому вы можете просто скачать ее вручную, если хотите.

Фактический код и бенчмарк

Я адаптировал код для glm из scratchapixel.com:

// реализация адаптирована из https://www.scratchapixel.com
float fresnel(const glm::vec4 &I, const glm::vec4 &N, const float ior)
{ float cosi = std::clamp(glm::dot(I, N), -1.0f, 1.0f); float etai = 1, etat = ior; if (cosi > 0) { std::swap(etai, etat); } // Вычислить sini с помощью закона Снеллиуса float sint = etai / etat * sqrtf(std::max(0.f, 1 - cosi * cosi)); // Полное внутреннее отражение if (sint >= 1) return 1.0f; float cost = sqrtf(std::max(0.f, 1 - sint * sint)); cosi = fabsf(cosi); float Rs = ((etat * cosi) - (etai * cost)) / ((etat * cosi) + (etai * cost)); float Rp = ((etai * cosi) - (etat * cost)) / ((etai * cosi) + (etat * cost)); return (Rs * Rs + Rp * Rp) / 2.0f;
}

Код использует несколько математических инструкций, скалярное произведение, умножение, деление, так что процессору есть, чем заняться. Вместо вектора double мы используем вектор из 4х элементов, чтобы увеличить количество используемой памяти.

Бенчмарк:

std::transform(std::execution::par, vec.begin(), vec.end(), vecNormals.begin(), // векторы ввода vecFresnelTerms.begin(), // вывод [](const glm::vec4& v, const glm::vec4& n) { return fresnel(v, n, 1.0f); } );

И вот результаты (время в миллисекундах):

Операция

Размер вектора

i7 4720 (4 ядра)

i7 8700 (6 ядер)

execution::seq

1k

0.032764

0.016361

execution::par

1k

0.031186

0.028551

openmp parallel for

1k

0.005526

0.007699

execution::seq

10k

0.246722

0.169383

execution::par

10k

0.090794

0.067048

openmp parallel for

10k

0.049739

0.029835

execution::seq

100k

2.49722

1.69768

execution::par

100k

0.530157

0.283268

openmp parallel for

100k

0.495024

0.291609

execution::seq

1000k

25.0828

16.9457

execution::par

1000k

5.15235

2.33768

openmp parallel for

1000k

5.11801

2.95908

С “настоящими” вычислениями видим, что параллельные алгоритмы обеспечивают хорошую производительность. Для таких операций на двух моих машинах с Windows я добился ускорения с почти линейной зависимостью от количества ядер.

Для всех тестов я также показал результаты из OpenMP и двух реализаций: MSVC и OpenMP работают аналогично.

Вывод

Замена стандартных алгоритмов на версию std::execution::par может показаться очень заманчивой, но делать это стоит не всегда! В этой статье я разобрал три случая применения параллельного вычисления и параллельных алгоритмов. Поэтому рассматривайте каждое изменение отдельно. Каждая операция, используемая вами внутри алгоритма может работать иначе и быть более зависимой от процессора или памяти.

О чем стоит помнить:

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

Особое спасибо JFT за помощь со статьей!

Также обратите внимание на мои другие источники о параллельных алгоритмах:

Обратите внимание на другую статью, связанную с Параллельными Алгоритмами: How to Boost Performance with Intel Parallel STL and C++17 Parallel Algorithms

THE END

Ждём и комментарии, и вопросы, которые можно оставить тут или у нашего преподавателя на дне открытых дверей.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть