Шаблоны структурного параллельного программирования Созыкин Андрей Владимирович к.т.н. Заведующий кафедрой высокопроизводительных компьютерных технологий Институт математики и компьютерных наук

2 Шаблоны структурного параллельного программирования Созыкин А.В. Структурное параллельное программирование Авторы Michael McCool, Arch Robison, James Reinders Шаблоны для эффективных вычислений Russia

3 Шаблоны структурного параллельного программирования Созыкин А.В. Структурное параллельное программирование Шаблоны структурного параллельного программирования Лучшие практики для решения специфических задач Шаблоны используются для структурирования кода: Улучшается масштабируемость Упрощается сопровождение Большая часть шаблонов детерминированная Шаблоны задают общую терминологию для описания параллельных алгоритмов Шаблоны описывают алгоритмы Реализация шаблонов может быть разной

4 Шаблоны структурного параллельного программирования Созыкин А.В. Параллельные шаблоны Structured Parallel Programming with Patterns. SC13 Tutorial

5 Шаблоны структурного параллельного программирования Созыкин А.В. Шаблон Map Самый простой и популярный параллельный шаблон Применение элементной функции к множеству значений параллельно Каждая операция независима от других

6 Шаблоны структурного параллельного программирования Созыкин А.В. Шаблон Map Ограничения на элементную функцию: Не иметь побочных эффектов Не должна выполнять произвольную запись Возможны произвольные чтения Если ограничения не выполняются, результат недетерминированный

7 Шаблоны структурного параллельного программирования Созыкин А.В. Пример Map. SAXPY Scaled Vector Addition (SAXPY): y = a × x + y x, y – векторы, a - скаляр Часто встречается в линейной алгебре Название из библиотеки BLAS (Basic Linear Algebra Subprograms),

8 Шаблоны структурного параллельного программирования Созыкин А.В. Последовательный SAXPY void saxpy_serial( int n, // количество элементов float a, // скалярный множитель const float x[], // первый исходный вектор float y[]) // второй исходный и результирующий // вектор { for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i]; }

9 Шаблоны структурного параллельного программирования Созыкин А.В. Параллельный SAXPY. OpenMP void saxpy_openmp( int n, // количество элементов float a, // скалярный множитель const float x[], // первый исходный вектор float y[]) // второй исходный и результирующий // вектор { #pragma omp parallel for for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i]; }

10 Шаблоны структурного параллельного программирования Созыкин А.В. OpenMP. Потоки и векторизация Многопоточная программа #pragma omp parallel for for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i]; Векторизованная программа #pragma omp simd for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i]; Векторизованная многопоточная программа #pragma omp parallel for simd for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i];

11 Шаблоны структурного параллельного программирования Созыкин А.В. Параллельный SAXPY. Cilk Plus void saxpy_cilkplus( int n, // количество элементов float a, // скалярный множитель const float x[], // первый исходный вектор float y[]) // второй исходный и результирующий // вектор { cilk_for (int i = 0; i < n; i++) y[i] = a * x[i] + y[i]; }

12 Шаблоны структурного параллельного программирования Созыкин А.В. Cilk Plus Array Notation void saxpy_cilkplus( int n, // количество элементов float a, // скалярный множитель const float x[], // первый исходный вектор float y[]) // второй исходный и результирующий // вектор { y[0:n] = a * x[0:n] + y[0:n]; } Явная векторизация a * x[0:n] – scalar promotion

13 Шаблоны структурного параллельного программирования Созыкин А.В. Параллельный SAXPY. TBB void saxpy_tbb( int n, // количество элементов float a, // скалярный множитель const float x[], // первый исходный вектор float y[]) // второй исходный и результирующий // вектор { tbb::parallel_for( tbb::blocked_range (0, n), [&](tbb::blocked_range r) { for (int i = r.begin(); i != r.end(); ++i) y[i] = a * x[i] + y[i]; } ); }

14 Шаблоны структурного параллельного программирования Созыкин А.В. TBB и векторизация TBB использует потоки для распараллеливания Векторизация не поддерживается TBB напрямую Компилятор может автоматически векторизовать код TBB

15 Шаблоны структурного параллельного программирования Созыкин А.В. Шаблон Stencil Расширение шаблона Map Элементная функция зависит от нескольких «соседних» значений Примеры: масочная фильтрация изображений, уравнения в частных производных и т.п.

16 Шаблоны структурного параллельного программирования Созыкин А.В. Шаблон Stencil. Масочная фильтрация Размытие { 1/9, 1/9, 1/9, 1/9, 1/9, 1/9, 1/9, 1/9, 1/9 }; Выделение границ { 0, -1, 0, -1, 4, -1, 0, -1, 0 }; Увеличение четкости { 0, -1, 0, -1, 5, -1, 0, -1, 0 }; "Lady Agnew of Lochnaw," by John Singer Sargent

17 Шаблоны структурного параллельного программирования Созыкин А.В. Оптимизация Map и Stencil

18 Шаблоны структурного параллельного программирования Созыкин А.В. Оптимизация Map и Stencil для кэш Объем данных большой Строка не помещается в кэш полностью Разбиение на блоки по столбцам Ширина столбца кратна строке кэша Нет ложного разделения Нужные данные всегда в кэше Реализация: Cilk plus – автоматически при векторной нотации TBB: affinity_partitioner

19 Шаблоны структурного параллельного программирования Созыкин А.В. Шаблон Reduce Редукция (свертка) элементов коллекции в один элемент Требования к операции для редукции: Ассоциативная (обязательно) Коммутативная (почти всегда необходимо для распараллеливания)

20 Шаблоны структурного параллельного программирования Созыкин А.В. Шаблон Reduce Редукция (свертка) элементов коллекции в один элемент Требования к операции для редукции: Ассоциативная (обязательно) Коммутативная (почти всегда необходимо для распараллеливания)

21 Шаблоны структурного параллельного программирования Созыкин А.В. Пример Reduce. Векторное произведение

22 Шаблоны структурного параллельного программирования Созыкин А.В. Векторное произведение. OpenMP float dot_prod = 0; #pragma omp parallel for reduction(=:dot_prod) for (int i = 0; i < n; i++) dot_prod += a[i] * b[i]; OpenMP для каждого потока создает отдельную локальную копию переменной dot_prod После завершения потоков значения локальных копий dot_prod складываются и записываются в глобальную переменную Если не указать reduction, будут условия гонок OpenMP никак не сигнализирует от этом

23 Шаблоны структурного параллельного программирования Созыкин А.В. Векторное произведение. Cilk plus Гиперобъект: cilk::reducer > sum = 0; cilk_for (int i = 0; i < n; i++) *sum += a[i] * b[i]; dot_product = sum.getValue(); Array notation: dot_product = __sec_reduce_add(a[0:n] * b[0:n])

24 Шаблоны структурного параллельного программирования Созыкин А.В. Векторное произведение. TBB dot_product = tbb::parallel_reduce( tbb::blocked_range (0,n), 0.f, [=](tbb::blocked_range r, float in) { return std::inner_product(a + r.begin(), a + r.end(), b + r.begin(), in); }, std::plus () ); } in – Начальное значение для блока редукции, должно быть обязательно включено!

25 Шаблоны структурного параллельного программирования Созыкин А.В. Реализация редукции в TBB Начальное значение Свертка блоков Сцепление блоков (результат не детерминирован)

26 Шаблоны структурного параллельного программирования Созыкин А.В. Оптимизации Reduce Векторизация Reduce Блочный Reduce (для кэша или кластера)

27 Шаблоны структурного параллельного программирования Созыкин А.В. Шаблон Scan Scan – множество всех частичных редукций для коллекции Пример: префиксная сумма Сумма всех предыдущих элементов массива Применение: лексикографическое сравнение строк, быстрая сортировка (quicksort), поразрядная сортировка (radix sort), решение трехдиагональных линейных систем и др. Guy E. Blelloch. Prefix Sums and Their Applications. CMU-CS , November 1990.

28 Шаблоны структурного параллельного программирования Созыкин А.В. Пример Scan. Префиксная сумма Последовательная реализация: a[0] = b[0]; for (int i = 1; i < n; i++) a[i] += a[i - 1] + b[i]; Зависимость по данным! Можно ли это распараллелить?

29 Шаблоны структурного параллельного программирования Созыкин А.В. Трех шаговый параллельный Scan

30 Шаблоны структурного параллельного программирования Созыкин А.В. Параллельная реализация scan OpenMP и Cilk Plus не содержат встроенный scan Можно реализовать с помощью fork-join Объемный код, пример в книге «Structured Parallel Programing» TBB содержит parallel_scan

31 Шаблоны структурного параллельного программирования Созыкин А.В. Параллельная реализация scan в TBB using namespace tbb; class Body { T sum; T* const y; const T* const z; public: Body( T y_[], const T z_[] ) : sum(0), z(z_), y(y_) {} T get_sum() const {return sum;} template void operator()( const blocked_range & r, Tag ) { T temp = sum; for( int i=r.begin(); i

32 Шаблоны структурного параллельного программирования Созыкин А.В. Шаблоны реорганизации данных Scatter Условия гонок при Scatter Возможные результаты Scatter Gather Pack Unpack

33 Шаблоны структурного параллельного программирования Созыкин А.В. Шаблоны реорганизации данных Split Unsplit Bin Expand

34 Шаблоны структурного параллельного программирования Созыкин А.В. Схемы хранения данных Массив структур Структура массивов Zip Unzip

35 Шаблоны структурного параллельного программирования Созыкин А.В. Шаблон Fork-Join Поток разделяется на несколько, которые через некоторое время объединяются Возможен вложенный Fork-Join Задачи должны быть независимыми Используется в алгоритмах «Разделяй и властвуй»: сортировка слиянием алгоритм Карацубы быстрого умножения многочленов алгоритм Cooley–Tukey быстрого преобразования Фурье

36 Шаблоны структурного параллельного программирования Созыкин А.В. Алгоритм Cooley–Tukey Алгоритм быстрого вычисления дискретного преобразования Фурье Сложность O(N log N) Задача рекурсивно делится на равные части При N = 2 вычисляется преобразование Фурье по упрощенной схеме «Бабочка» Результаты частичных преобразований объединяются также по схеме «Бабочка»

37 Шаблоны структурного параллельного программирования Созыкин А.В. Fork-Join в OpenMP OpenMP включает две конструкции для реализации Fork- Join: Task (появился в OpenMP 3) Section (считается устаревшим) Обе конструкции должны находится внутри параллельного региона #pragma omp task function1(); function2(); #pragma omp taskwait #pragma omp sections { #pragma omp section function1(); #pragma omp section function2(); }

38 Шаблоны структурного параллельного программирования Созыкин А.В. Fork-Join в Cilk Plus Cilk Plus содержит специальную конструкции для реализации Fork-Join: cilk_spawn – запуск задачи (Fork) cilk_sync() – объединение всех задач (Join) cilk_spawn f(); g(); cilk_sync();

39 Шаблоны структурного параллельного программирования Созыкин А.В. Fork-Join в Cilk Plus Cilk Plus содержит специальную конструкции для реализации Fork-Join: cilk_spawn – запуск задачи (Fork) cilk_sync() – объединение всех задач (Join) cilk_spawn f(); g(); cilk_sync(); Плохой стиль: cilk_spawn f(); cilk_spawn g(); cilk_sync();

40 Шаблоны структурного параллельного программирования Созыкин А.В. Fork-Join в Cilk Plus Запуск лямбда-выражения: cilk_spawn [&]{ for( int i=0; i

41 Шаблоны структурного параллельного программирования Созыкин А.В. Fork-Join в TBB TBB содержит две конструкции для Fork-Join: parallel_invoke( functor1, functor2,...) – для небольшого количества задач (до 10) task_group – любое количество задач functor: Объект-функция Имеет метод void operator ()() const Параметры передаются через конструктор Обычно создается лямбда-выражением parallel_invoke: parallel_invoke(f, g); Ожидает завершения выполнения задач (неявный Join)

42 Шаблоны структурного параллельного программирования Созыкин А.В. Task group в TBB task_group tgroup; tgroup.run( f ); tgroup.run( g ); h(); tgroup.wait(); // tgroup.run_and_wait(h);

43 Шаблоны структурного параллельного программирования Созыкин А.В. Task group в TBB task_group tgroup; tgroup.run( f ); tgroup.run( g ); h(); tgroup.wait(); // tgroup.run_and_wait(h); Создание функтора через лямбда-выражение task_group tgroup; for (int i = 0; i < n; i++) tgroup.run([=,&a]f(a[i]);); // i передаем по значению // a – по ссылке tgroup.wait();

44 Шаблоны структурного параллельного программирования Созыкин А.В. Рекурсивный параллелизм Structured Parallel Programming with Patterns. SC13 Tutorial

45 Шаблоны структурного параллельного программирования Созыкин А.В. Типы параллелизма Обязательный Каждая подзадача должна запускаться в отдельном потоке (процессе, машине и т.п.) Ограничения по масштабируемости и переносимости Потенциальный: Задачи могут запускаться параллельно Решение о параллельном запуске принимает среда исполнения Желательный вариант: Использование потенциального параллелизма Разделение задачи на как можно большее количество потенциально параллельно исполняемых задач без привязки к конкретному оборудования Увеличение масштабируемости и переносимости

46 Шаблоны структурного параллельного программирования Созыкин А.В. Типы параллелизма Cilk Plus и TBB: потенциальный параллелизм Пул потоков, которые выполняют задачи (cilk_for или cilk_spawn) Если свободного потока нет, задачи выполняются последовательно OpenMP: обязательный параллелизм #pragma omp parallel обязательно создает заданное количество потоков вложенный параллелизм возможен, но выключен по умолчанию

47 Шаблоны структурного параллельного программирования Созыкин А.В. Семантика и реализация Шаблоны описывают семантику алгоритма Реализация одного и того же шаблона в разных моделях может отличаться Шаблон Map в CilkPlus: Ключевое слово cilk_for Реализация: Fork-Join

48 Шаблоны структурного параллельного программирования Созыкин А.В. Итоги Шаблоны структурного параллельного программирования Лучшие практики для решения специфических задач Параллельная программа составляется на основе комбинации шаблонов Практически все описанные шаблоны детерминированные Использование шаблонов позволяет создавать эффективные и масштабируемые параллельные программы Рекомендуется использовать потенциальный, а не обязательный параллелизм

49 Шаблоны структурного параллельного программирования Созыкин А.В. Вопросы? Контакты: Созыкин Андрей Владимирович, заведующий кафедрой высокопроизводительных компьютерных технологий ИМКН УрФУ