'

Шаблоны структурного параллельного программирования

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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]; }


Слайд 8

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]; }


Слайд 9

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];


Слайд 10

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]; }


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

21 Шаблоны структурного параллельного программирования Созыкин А.В. Пример Reduce. Векторное произведение Векторное произведение: ?????= ??=0 ???1 ??[??]???[??] Последовательная реализация: float dot_prod = 0; for (int i = 0; i < n; i++) dot_prod += a[i] * b[i];


Слайд 21

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 никак не сигнализирует от этом


Слайд 22

23 Шаблоны структурного параллельного программирования Созыкин А.В. Векторное произведение. Cilk plus Гиперобъект: cilk::reducer<op_add<float>> 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])


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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<typename Tag> void operator()( const blocked_range<int>& r, Tag ) { T temp = sum; for( int i=r.begin(); i<r.end(); ++i ) { temp = temp + z[i]; if( Tag::is_final_scan() ) y[i] = temp; } sum = temp; } Body( Body& b, split ) : z(b.z), y(b.y), sum(0) {} void reverse_join( Body& a ) { sum = a.sum + sum;} void assign( Body& b ) {sum = b.sum;} }; float DoParallelScan( T y[], const T z[], int n ) { Body body(y,z); parallel_scan( blocked_range<int>(0,n), body ); return body.get_sum(); }


Слайд 31

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


Слайд 32

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


Слайд 33

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


Слайд 34

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


Слайд 35

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


Слайд 36

37 Шаблоны структурного параллельного программирования Созыкин А.В. Fork-Join в OpenMP OpenMP включает две конструкции для реализации Fork-Join: Task (появился в OpenMP 3) Section (считается устаревшим) Обе конструкции должны находится внутри параллельного региона


Слайд 37

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


Слайд 38

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();


Слайд 39

40 Шаблоны структурного параллельного программирования Созыкин А.В. Fork-Join в Cilk Plus Запуск лямбда-выражения: cilk_spawn [&]{ for( int i=0; i<n; ++i ) a[i] = 0; } (); cilk_sync(); Область действия cilk_spawn – до конца функции, где он был вызван: В конце функции стоит неявный cilk_sync() После завершения функции параллелизм обязательно завершится (Join)


Слайд 40

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)


Слайд 41

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


Слайд 42

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();


Слайд 43

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


Слайд 44

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


Слайд 45

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


Слайд 46

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


Слайд 47

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


Слайд 48

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


×

HTML:





Ссылка: