Практические рекомендации по распараллеливанию с помощью OpenMP и измерению ускорения. Ошибки при многопоточном программировании

Сентябрь 7, 2022

Главная
Алгебра
Практические рекомендации по распараллеливанию с помощью OpenMP и измерению ускорения. Ошибки при многопоточном программировании

Содержание

2. OpenMP Практические рекомендации по распараллеливанию с помощью OpenMP и измерению ускорения. Ошибки при многопоточном программировании. Презентация
3. 1. Практические рекомендации по распараллеливанию с помощью OpenMP и измерению ускорения. 1.1. Время вычислений в параллельном
4. Потоки в современных Windows Процесс представляет выполняющийся экземпляр программы. Он имеет собственное адресное пространство, где содержаться
5. Классы потоков. Потоки OpenMP
6. Основные состояния потока. «Накладные расходы»
7. Неизбежные «накладные расходы» в многопоточной программе с несколькими параллельными регионами Создание потоков – самые большие «накладные
8. 1. 1. Время вычислений в параллельном регионе должно быть больше, чем время, затраченное на создание параллельного
9. 1.2. При входе в первый параллельный регион «накладные расходы» намного больше, чем при входах в следующие
10. Тестируемый код – проект time_parallel – ускорение как функция полного времени работы программы – последовательный код
11. Тестируемый код – проект time_parallel – ускорение как функция полного времени работы программы – параллельный код
12. Тестируемый код – проект time_parallel – ускорение как функция полного времени работы программы – параллельный код
13. Требования на выбор предельных значений переменных внешнего и внутреннего цикла 1. Внутренний цикл: treeData.N определяется из
14. Задание 1. Проект time_paral. Зависимость ускорения от M 1. Для запуска последовательного варианта аргументы в командной
15. Задание 2. Проект time_paral. Зависимость ускорения от M Демонстрация того, что все «накладные расходы» сосредоточены в
16. 2. Ошибки при многопоточном программировании 1. Конфликты «запись - запись» - два потока пишут в одну
17. Ошибки, которые находит ThreadChecker при программировании в OpenMP 1. Конфликты «запись - запись» - два потока
18. 3. Презентация материалов по OpenMP 3.1. Курс Гергеля 3.2. Материалы тренингов Intel
19. 3.1. Курс Гергеля Обзор методов многопоточного программирования для простейших алгоритмов умножение вектора на вектор матрицы на
20. 3.2. Материалы тренингов Intel Преобладающая особенность – все показывается на одной задаче Параллельный алгоритм Параллельные конструкции
21. 4. Распределение заданий между потоками По материалам тренинга Intel, проведенного для преподавателей вузов в апреле 2006
22. Цели и задачи Научиться технике распараллеливания последовательного кода на основе OpenMP Применять в цикле разработки инструменты
23. Содержание Стандартный цикл разработки Изучаемый пример: генерация простых чисел Как повысить эффективность вычислений
24. Определение параллелелизма Два или более процесса или потока выполняются одновременно Виды параллелелизма для архитектур, поддерживающих потоки
25. Закон Амдала Оценка «сверху» для ускорения параллельной программы по закону Амдала
26. Процессы и потоки
27. Потоки – «плюсы» и «минусы» «Плюсы» Позволяют повысить производительность и полнее использовать системные ресурсы Даже в
28. Генерация простых чисел bool TestForPrime(int val) { // let’s start checking from 3 int limit, factor
29. Задание 1. Выполнить запуски последовательной версии первоначального кода (проект Simple_number) Установить однопоточный режим работы (Visual Studio,
30. Методика разработки Анализ Определить участок кода с максимальной долей вычислений Проектирование (включить многопоточность) Определить, каким образом
31. Рабочий цикл
32. Провести анализ работы проекта Simple_number Входные данные: start = 3 end = 1000000 Анализ – «Sampling»
33. Анализ – «Sampling» («сэмплирование»)
34. Анализ – «Sampling» («сэмплирование»)
35. Анализ - Call Graph
36. Анализ Параллельная работа потоков будет эффективна в FindPrimes() Аргументы в пользу распараллеливания Мало внутренних взаимозависимостей Возможен
37. Задание 2 Выполните запуск с параметрами ‘1 5000000’ (границы диапазона поиска простых чисел) Цель запуска -
38. Метод проектирования Фостера Необходимо выполнить 4 шага: Разбить задачу на максимальное число подзадач Установить связи «данные
39. Проектирование многопоточной программы «Дробление» Разбить исходную задачу на подзадачи «Связи» Определить типы и количество связей между
40. Модели параллельного программирования Функциональная декомпозиция Параллельное выполнение разных подзадач Разделение на различные подзадачи, но обработка общих
41. Способы декомпозиции Функциональная декомпозиция Сфокусирована на методах обработки данных, выявляя структуру задачи
42. Аналогии для функциональной декомпозиции и декомпозиции по данным Независимые этапы вычислений Функциональная декомпозиция Задача потока связана
43. Проектирование Ожидаемый выигрыш Как бы его достичь минимальными усилиями? Долго ли это - распараллелить? Сразу получится
44. OpenMP «Вилочный» параллелелизм: «Мастер» - поток создает команду потоков Последовательная программа преображается в параллельную
45. Проектирование #pragma omp parallel for for( int i = start; i if( TestForPrime(i) ) globalPrimes[gPrimesFound++] =
46. Задание 3 Выполнить запуск версии кода с OpenMP Включите библиотеки OpenMP и установите многопоточный режим MultyThreaded
47. Проектирование А каков был ожидаемый выигрыш? А как его достичь ? А как долго ? А
48. Тестирование правильности работы программы по ее результатам Результаты неправильные Каждый запуск – свой результат…
49. Тестирование правильности работы Intel® Thread Checker может определить ошибки типа «гонки данных» или «конфликты запись-запись, чтение
50. Thread Checker – окно результатов после выполнения анализа
51. Thread Checker Двойной щелчок «мыши» - находим локализацию ошибки в коде
52. Thread Checker – локализация ошибки в коде
53. Задание 4 Примените Thread Checker для анализа правильности выполнения Создать Thread Checker activity Запуск приложения с
54. Тестирование правильности работы Сколько попыток еще предпринять? Как долго трудиться над этим распараллеливанием? Thread Checker обнаружил
55. Тестирование правильности работы #pragma omp parallel for for( int i = start; i if( TestForPrime(i) )
56. Задание 5 Модифицируйте версию кода с OpenMP Добавьте прагму критической секции в код Откомпилируйте код Проверьте
57. Correctness Работает-то правильно, да ускорение низкое…~1.33X Разве это предел, к которому мы стремились? Нет! По закону
58. Задачи повышения производительности Параллельный «оверхед» (оverhead) «Накладные расходы» на создание потоков, организацию «расписания» их работы …
59. Измерение производительности Thread Profiler определяет «узкие места» - участки кода многопоточной области, где работа потоков происходит
60. Thread Profiler for OpenMP Только для OpenMP приложений Окно результатов «Summary» - появляется сразу после завершения
61. Thread Profiler for OpenMP
62. Thread Profiler for OpenMP
63. Thread Profiler for OpenMP
64. Thread Profiler for OpenMP Окно «Regions»: регионы – область кода программы, либо полностью последовательного, либо полностью
65. Thread Profiler for OpenMP
66. Задание 6. Исследуйте параллельную работу программы Thread Profiler с теми же параметрами, что и базовое измерение
67. Диагностика Thread Profiler – большой дисбаланс – потоки «ждали друг друга» Поток 0 Поток 1 Поток
68. Определили дисбаланс загрузки Распределим работу более эффективно: не по ¼ от всего цикла сразу каждому потоку,
69. Борьба с дисбалансом – перераспределение заданий потокам Новое «распределение работы» по сравнению со старым будет следующим
71. Скачать презентацию

Слайд 2

OpenMP
Практические рекомендации по распараллеливанию с помощью OpenMP и измерению ускорения.
Ошибки

при многопоточном программировании.
Презентация материалов по OpenMP
Распределение заданий между потоками

Слайд 3

1. Практические рекомендации по распараллеливанию с помощью OpenMP и измерению ускорения.

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

Слайд 4

Потоки в современных Windows
Процесс представляет выполняющийся экземпляр программы. Он имеет собственное

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

Слайд 5

Классы потоков. Потоки OpenMP

Слайд 6

Основные состояния потока. «Накладные расходы»

Слайд 7

Неизбежные «накладные расходы» в многопоточной программе с несколькими параллельными регионами
Создание

потоков – самые большие «накладные расходы»
На «остановлен» - «на процессоре» - «накладные расходы» намного меньше, чем на создание (вход – выход в параллельную секцию)
На «ожидание» - «на процессоре» «накладные расходы» намного меньше, чем на «остановлен» - «на процессоре» (критическая секция – зато чаще встречается, чем вход в параллельную секцию)

Слайд 8

1. 1. Время вычислений в параллельном регионе должно быть больше, чем

время, затраченное на создание параллельного региона

Это время может быть определено из работы цикла вида
for (i = 1; i < treeData.N; i++)
{
#pragma omp parallel
{
}
}

Слайд 9

1.2. При входе в первый параллельный регион «накладные расходы» намного больше,

чем при входах в следующие параллельные регионы

Либо полное время параллельных вычислений должно быть больше кванта операционной системы (для систем разделения времени, в том числе Windows)
Либо перед тестируемым участком поставить директиву по созданию пустого параллельного региона
– большая часть «накладных расходов» будет «локализована» в ней
- условие выбора величины кванта – чтобы работа процессов «приносила больше пользы», чем «накладные расходы» на их инициирование)

Слайд 10

Тестируемый код – проект time_parallel – ускорение как функция полного времени

работы программы – последовательный код

start = rdtsc();
for (j=1; j <=M; j++)
for (i = 1; i < treeData.N; i++)
if (treeData.Path[i] > limit)
{
Weight_PathMin = treeData.max+limit;
if (Weight_PathMin > limit)
{
replace_number = treeData.Weight[i];
}
}
stop = rdtsc()-start;

Слайд 11

Тестируемый код – проект time_parallel – ускорение как функция полного времени

работы программы – параллельный код (участок в main)

start = rdtsc();
for (j = 1; j <=M; j++)
{ omp_set_num_threads (num_threads);
#pragma omp parallel private(id)
{ id = omp_get_thread_num();
Path_Min[id] = Search_minimum (id, treeData.max,
treeData.Path, treeData.N, num_threads);
}
MinimPath = treeData.max;
for (i = 0; i < num_threads; i++)
if(Path_Min[i] < MinimPath) MinimPath = Path_Min[i];
}
stop = rdtsc()-start;

Слайд 12

Тестируемый код – проект time_parallel – ускорение как функция полного времени

работы программы – параллельный код (функция, выполняемая двумя потоками, к ней - обращение из параллельной секции)

int Search_minimum(int myID, int minimum, int*mas,
const int n, const int num_threads )
{ int i, Initial, Final;
int ID; int N_Section = n/num_threads;
Initial = myID*N_Section; Final = (myID + 1)*N_Section;
for (i = Initial; i< Final; i++)
if (mas[i] <= minimum) minimum = mas[i];
return minimum;
}

Слайд 13

Требования на выбор предельных значений переменных внешнего и внутреннего цикла
1. Внутренний

цикл: treeData.N определяется из условия:
t(внутреннего цикла)>> t(входа в многопоточный регион)
2.1. Внешний цикл: при фиксированном treeData.N должно быть такое М, что
t(полное) ~ или > t(кванта)
2.2. Либо M любое, но перед тестируемым циклом стоит директива по созданию параллельного региона

Слайд 14

Задание 1. Проект time_paral. Зависимость ускорения от M
1. Для запуска последовательного

варианта аргументы в командной строке:
1) 5 10 10000 1 3
2) 5 10 10000 2 3
3) 5 10 10000 10 3
4) 5 10 10000 100 3
5) 5 10 10000 1000 3
6) 5 10 10000 100000 3
1. Для запуска параллельного варианта аргументы в командной строке:
1) 5 10 10000 1 5 2
2) 5 10 10000 2 5 2
3) 5 10 10000 10 5 2
4) 5 10 10000 100 5 2
5) 5 10 10000 1000 5 2
6) 5 10 10000 100000 5 2

Слайд 15

Задание 2. Проект time_paral. Зависимость ускорения от M
Демонстрация того, что все

«накладные расходы» сосредоточены в первом создаваемом многопоточном регионе (в этом варианте – вход в три одинаковых параллельных региона):
Запуск с аргументами командной строки
5 10 10000 1 11 2

Слайд 16

2. Ошибки при многопоточном программировании
1. Конфликты «запись - запись» - два

потока пишут в одну переменную
(«а ля» два рецензента правят один экземпляр статьи и друг друга одновременно – кто успеет быстрее «гонки данных»)
2. Тупики или «зависания» или «lock» (один поток захватил ресурс и не отдает другим – программа может висеть бесконечно)
Живой
Мертвый
3. Избыточное применение параллельных конструкций – меньше ускорение, хотя программа работает правильно

Слайд 17

Ошибки, которые находит ThreadChecker при программировании в OpenMP
1. Конфликты «запись -

запись» - два потока пишут в одну переменную
Значение этой переменной зависит от того, «кто успел быстрее»
Кроме того, большие «накладные расходы» - резкое увеличение времени работы

Слайд 18

3. Презентация материалов по OpenMP
3.1. Курс Гергеля
3.2. Материалы тренингов Intel

Слайд 19

3.1. Курс Гергеля
Обзор методов многопоточного программирования для простейших алгоритмов
умножение вектора

на вектор
матрицы на матрицу
решение систем линейных уравнений
сортировки
Обзор основных конструкций OpenMP
Особенность курса
в основном обзорный характер, «охват материала»
акцент – на рассмотрении алгоритмов

Слайд 20

3.2. Материалы тренингов Intel
Преобладающая особенность – все показывается на одной задаче
Параллельный

алгоритм
Параллельные конструкции OpenMP
Методика создания многопоточного приложения
Интерфейс и возможности отладчиков
Акцент на процесс создания и технологию параллельного программирования

Слайд 21

4. Распределение заданий между потоками
По материалам тренинга Intel, проведенного для преподавателей

вузов в апреле 2006 г.

Слайд 22

Цели и задачи
Научиться технике распараллеливания последовательного кода на основе OpenMP
Применять в

цикле разработки инструменты Intel
Оценивать максимально возможное ускорение многопоточной программы по закону Амдала

Слайд 23

Содержание
Стандартный цикл разработки
Изучаемый пример: генерация простых чисел
Как повысить эффективность вычислений

Слайд 24

Определение параллелелизма
Два или более процесса или потока выполняются одновременно
Виды параллелелизма

для архитектур, поддерживающих потоки
Множество процессов
Взаимодействие между процессами
(Inter-Process Communication (IPC))

Слайд 25

Закон Амдала
Оценка «сверху» для ускорения параллельной программы по закону Амдала

Слайд 26

Процессы и потоки

Слайд 27

Потоки – «плюсы» и «минусы»
«Плюсы»
Позволяют повысить производительность и полнее использовать системные

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

Слайд 28

Генерация простых чисел
bool TestForPrime(int val)
{ // let’s start checking

from 3
int limit, factor = 3;
limit = (long)(sqrtf((float)val)+0.5f);
while( (factor <= limit) && (val % factor) )
factor ++;
return (factor > limit);
}
void FindPrimes(int start, int end)
{
int range = end - start + 1;
for( int i = start; i <= end; i += 2 )
{
if( TestForPrime(i) )
globalPrimes[gPrimesFound++] = i;
ShowProgress(i, range);
}
}

Слайд 29

Задание 1.
Выполнить запуски последовательной версии первоначального кода (проект Simple_number)
Установить однопоточный режим

работы (Visual Studio, Project properties -> С++ -> code generation -> Single Threaded Debug DLL)
Выполнить компиляцию с помощью Intel C++
Выполнить несколько запусков с различными диапазонами поиска простых чисел (start, end)

Слайд 30

Методика разработки
Анализ
Определить участок кода с максимальной долей вычислений
Проектирование (включить многопоточность)
Определить, каким

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

Слайд 31

Рабочий цикл

Слайд 32

Провести анализ работы проекта Simple_number
Входные данные: start = 3 end =

1000000

Анализ – «Sampling» («сэмплирование»)

С помощью VTune Sampling необходимо определить «узкие места» приложения
(где сосредоточена максимальная «тяжесть» вычислений)

Цель: выделить области кода, выполнение которых занимает максимальное время

Слайд 33

Анализ – «Sampling» («сэмплирование»)

Слайд 34

Анализ – «Sampling» («сэмплирование»)

Слайд 35

Анализ - Call Graph

Слайд 36

Анализ
Параллельная работа потоков будет эффективна в
FindPrimes()
Аргументы в пользу распараллеливания
Мало внутренних

взаимозависимостей
Возможен параллелелизм по данным
Занимает более 95% всего времени работы приложения

Слайд 37

Задание 2
Выполните запуск с параметрами ‘1 5000000’ (границы диапазона поиска простых

чисел)
Цель запуска - получить значение времени, с которым будет сравниваться время работы многопоточного приложения
Мы прошли первый этап цикла разработки:
Анализ последовательного кода с помощью VTune
Выявление функций с максимальным временем работы – «узких мест»

Слайд 38

Метод проектирования Фостера
Необходимо выполнить 4 шага:
Разбить задачу на максимальное число подзадач
Установить

связи «данные - вычисления»
«Агломерация»:
составить задания, которые можно выполнять параллельно
«Распределение» - распределить задания между процессорами/потоками

Слайд 39

Проектирование многопоточной программы
«Дробление»
Разбить исходную задачу на подзадачи
«Связи»
Определить типы и количество связей

между подзадачами
«Агломерация»
Составить задания – сгруппировать «мелкие» подзадачи в «большие» группы – по принципу минимума связей между группами
«Распределение»
Распределить задания между процессорами/потоками

Многопоточная программа

Слайд 40

Модели параллельного программирования
Функциональная декомпозиция
Параллельное выполнение разных подзадач
Разделение на различные подзадачи, но

обработка общих данных каждой подзадачей
Выделение независимых подзадач для распределения между процессорами/потоками
Декомпозиция по данным
Выделение операций, общих для различных данных
Разбиение данных на блоки, которые можно обрабатывать независимо

Слайд 41

Способы декомпозиции
Функциональная декомпозиция
Сфокусирована на методах обработки данных, выявляя структуру задачи

Слайд 42

Аналогии для функциональной декомпозиции и декомпозиции по данным
Независимые этапы вычислений
Функциональная декомпозиция
Задача

потока связана со «стадией вычислений»
Аналогия с конвейером сборки автомобиля – каждый рабочий(поток) параллельно с другими собирает все детали одного (своего) типа – затем общая сборка автомобиля
Декомпозиция по данным
Потоковый процесс выполняет все стадии для своего блока данных
Каждый рабочий собирает свой автомобиль

Слайд 43

Проектирование
Ожидаемый выигрыш
Как бы его достичь минимальными усилиями?
Долго ли это -

распараллелить?
Сразу получится – или «путем итераций»?

Параллелелизм – с помощью OpenMP !

Ускорение(2P) = 100/(96/2+4) = ~1.92X

Слайд 44

OpenMP
«Вилочный» параллелелизм:
«Мастер» - поток создает команду потоков
Последовательная программа преображается

в параллельную

Слайд 45

Проектирование
#pragma omp parallel for
for( int i = start; i <=

end; i+= 2 ){
if( TestForPrime(i) )
globalPrimes[gPrimesFound++] = i;
ShowProgress(i, range);
}

Слайд 46

Задание 3
Выполнить запуск версии кода с OpenMP
Включите библиотеки OpenMP и установите

многопоточный режим MultyThreaded Debug DLL
Выполните компиляцию
Запуск с параметрами ‘1 5000000’ для сравнения
Определите ускорение

Слайд 47

Проектирование
А каков был ожидаемый выигрыш?
А как его достичь ?
А как долго

?
А сколько попыток ?
А возможно ли ?

Ускорение 1.40X (меньше 1.92X)

Слайд 48

Тестирование правильности работы программы по ее результатам
Результаты неправильные
Каждый запуск – свой

результат…

Слайд 49

Тестирование правильности работы
Intel® Thread Checker может определить ошибки типа «гонки данных»

или «конфликты запись-запись, чтение - запись»

Слайд 50

Thread Checker – окно результатов после выполнения анализа

Слайд 51

Thread Checker
Двойной щелчок «мыши» - находим локализацию ошибки в коде

Слайд 52

Thread Checker – локализация ошибки в коде

Слайд 53

Задание 4
Примените Thread Checker для анализа правильности выполнения
Создать Thread Checker activity
Запуск

приложения с параметрами 3 20
Есть ошибки ?

Слайд 54

Тестирование правильности работы
Сколько попыток еще предпринять?
Как долго трудиться над этим распараллеливанием?
Thread

Checker обнаружил ошибку, значит, еще трудиться и трудиться…

Слайд 55

Тестирование правильности работы
#pragma omp parallel for
for( int i = start;

i <= end; i+= 2 ){
if( TestForPrime(i) )
#pragma omp critical
globalPrimes[gPrimesFound++] = i;
//ShowProgress(i, range);
}

Слайд 56

Задание 5
Модифицируйте версию кода с OpenMP
Добавьте прагму критической секции в код
Откомпилируйте

код
Проверьте Thread Checker
Если будут ошибки, исправьте их, и снова выполните проверку Thread Checker
Запуск ‘1 5000000’ для сравнения
Проверьте Thread Checker
Ускорение ?

Слайд 57

Correctness
Работает-то правильно, да ускорение низкое…~1.33X
Разве это предел, к которому мы стремились?
Нет!

По закону Амдала мы можем достичь ускорения 1.9X

Слайд 58

Задачи повышения производительности
Параллельный «оверхед» (оverhead)
«Накладные расходы» на создание потоков, организацию

«расписания» их работы …
Синхронизация
Применение без особой необходимости глобальных переменных, которые автоматически являются объектами синхронизации для всех потоков –
если один поток изменил значение глобальной переменной, значит, работа остальных будет приостановлена до тех пор, пока каждый поток не «установит у себя» новое значение глобальной переменной
Дисбаланс загрузки
Недостаточно эффективное распределение работы между потоками «кому сколько работать» - один свою работу сделал и ждет, а другие работают....
Гранулярность
Распределение «квантов» работы для потоков в пределах одного параллельного региона (все потоки выполняют свой «квант» - затем «хватают» следующий)– должно решать проблему дисбаланса загрузки

Слайд 59

Измерение производительности
Thread Profiler определяет «узкие места» - участки кода многопоточной области,

где работа потоков происходит «с низким КПД»

+DLL’s (инструментирование)

Бинарное
инструментирование

Primes.c

Primes.exe
(инструментированный)

Сборщик
данных при
выполнении
кода

Bistro.tp/guide.gvs
(файл результатов
анализа)

Компиляция +
инструментирование
кода

Primes.exe

/Qopenmp_profile

Слайд 60

Thread Profiler for OpenMP
Только для OpenMP приложений
Окно результатов

«Summary» - появляется сразу после завершения
анализа Thread Profiler
Стрелками показана расшифровка цветовой диагностики

Слайд 61

Thread Profiler for OpenMP

Слайд 62

Thread Profiler for OpenMP

Слайд 63

Thread Profiler for OpenMP

Слайд 64

Thread Profiler for OpenMP
Окно «Regions»: регионы – область кода программы,

либо полностью последовательного, либо полностью параллельного (параллельный регион)
показывает время работы каждого участка (например, дисбаланс, барьер – «цветовые участки») для каждой области (региона) кода

Слайд 65

Thread Profiler for OpenMP

Слайд 66

Задание 6.
Исследуйте параллельную работу программы Thread Profiler с теми же параметрами,

что и базовое измерение
Число потоков установите, равное 4

Слайд 67

Диагностика Thread Profiler – большой дисбаланс – потоки «ждали друг друга»
Поток

Поток 1

Поток 2

Поток 3

Слайд 68

Определили дисбаланс загрузки
Распределим работу более эффективно: не по ¼ от всего

цикла сразу каждому потоку, «пока не встретимся», а каждому по несколько итераций цикла, «пока не встретимся», затем – новые несколько итераций

void FindPrimes(int start, int end)
{
// start is always odd
int range = end - start + 1;
#pragma omp parallel for schedule(static, 8)
for( int i = start; i <= end; i += 2 )
{
if( TestForPrime(i) )
#pragma omp critical
globalPrimes[gPrimesFound++] = i;
//ShowProgress(i, range); }

Слайд 69

Борьба с дисбалансом – перераспределение заданий потокам
Новое «распределение работы» по сравнению

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

Практические рекомендации по распараллеливанию с помощью OpenMP и измерению ускорения. Ошибки при многопоточном программировании

Содержание

OpenMPПрактические рекомендации по распараллеливанию с помощью OpenMP и измерению ускорения. Ошибки

1. Практические рекомендации по распараллеливанию с помощью OpenMP и измерению ускорения.

Потоки в современных WindowsПроцесс представляет выполняющийся экземпляр программы. Он имеет собственное

Классы потоков. Потоки OpenMP

Основные состояния потока. «Накладные расходы»

Неизбежные «накладные расходы» в многопоточной программе с несколькими параллельными регионами Создание

1. 1. Время вычислений в параллельном регионе должно быть больше, чем

1.2. При входе в первый параллельный регион «накладные расходы» намного больше,

Тестируемый код – проект time_parallel – ускорение как функция полного времени

Тестируемый код – проект time_parallel – ускорение как функция полного времени

Тестируемый код – проект time_parallel – ускорение как функция полного времени

Требования на выбор предельных значений переменных внешнего и внутреннего цикла 1. Внутренний

Задание 1. Проект time_paral. Зависимость ускорения от M1. Для запуска последовательного

Задание 2. Проект time_paral. Зависимость ускорения от M Демонстрация того, что все

2. Ошибки при многопоточном программировании 1. Конфликты «запись - запись» - два

Ошибки, которые находит ThreadChecker при программировании в OpenMP1. Конфликты «запись -

3. Презентация материалов по OpenMP 3.1. Курс Гергеля3.2. Материалы тренингов Intel

3.1. Курс Гергеля Обзор методов многопоточного программирования для простейших алгоритмов умножение вектора

3.2. Материалы тренингов IntelПреобладающая особенность – все показывается на одной задачеПараллельный

4. Распределение заданий между потокамиПо материалам тренинга Intel, проведенного для преподавателей

Цели и задачиНаучиться технике распараллеливания последовательного кода на основе OpenMPПрименять в

СодержаниеСтандартный цикл разработкиИзучаемый пример: генерация простых чиселКак повысить эффективность вычислений

Определение параллелелизмаДва или более процесса или потока выполняются одновременно Виды параллелелизма

Закон АмдалаОценка «сверху» для ускорения параллельной программы по закону Амдала

Процессы и потоки

Потоки – «плюсы» и «минусы»«Плюсы»Позволяют повысить производительность и полнее использовать системные

Генерация простых чисел bool TestForPrime(int val) { // let’s start checking

Задание 1.Выполнить запуски последовательной версии первоначального кода (проект Simple_number)Установить однопоточный режим

Методика разработкиАнализОпределить участок кода с максимальной долей вычисленийПроектирование (включить многопоточность)Определить, каким

Рабочий цикл

Провести анализ работы проекта Simple_numberВходные данные: start = 3 end =

Анализ – «Sampling» («сэмплирование»)

Анализ – «Sampling» («сэмплирование»)

Анализ - Call Graph

АнализПараллельная работа потоков будет эффективна вFindPrimes()Аргументы в пользу распараллеливания Мало внутренних

Задание 2Выполните запуск с параметрами ‘1 5000000’ (границы диапазона поиска простых

Метод проектирования ФостераНеобходимо выполнить 4 шага:Разбить задачу на максимальное число подзадачУстановить

Проектирование многопоточной программы«Дробление»Разбить исходную задачу на подзадачи«Связи»Определить типы и количество связей

Модели параллельного программированияФункциональная декомпозицияПараллельное выполнение разных подзадачРазделение на различные подзадачи, но

Способы декомпозицииФункциональная декомпозицияСфокусирована на методах обработки данных, выявляя структуру задачи

Аналогии для функциональной декомпозиции и декомпозиции по даннымНезависимые этапы вычисленийФункциональная декомпозицияЗадача

Проектирование Ожидаемый выигрышКак бы его достичь минимальными усилиями?Долго ли это -

OpenMP«Вилочный» параллелелизм: «Мастер» - поток создает команду потоков Последовательная программа преображается

Проектирование#pragma omp parallel for for( int i = start; i <=

Задание 3Выполнить запуск версии кода с OpenMPВключите библиотеки OpenMP и установите

Проектирование А каков был ожидаемый выигрыш?А как его достичь ?А как долго

Тестирование правильности работы программы по ее результатамРезультаты неправильныеКаждый запуск – свой

Тестирование правильности работыIntel® Thread Checker может определить ошибки типа «гонки данных»

Thread Checker – окно результатов после выполнения анализа

Thread CheckerДвойной щелчок «мыши» - находим локализацию ошибки в коде

Thread Checker – локализация ошибки в коде

Задание 4Примените Thread Checker для анализа правильности выполненияСоздать Thread Checker activityЗапуск

Тестирование правильности работыСколько попыток еще предпринять?Как долго трудиться над этим распараллеливанием?Thread

Тестирование правильности работы#pragma omp parallel for for( int i = start;

Задание 5Модифицируйте версию кода с OpenMPДобавьте прагму критической секции в кодОткомпилируйте

CorrectnessРаботает-то правильно, да ускорение низкое…~1.33XРазве это предел, к которому мы стремились?Нет!

Задачи повышения производительности Параллельный «оверхед» (оverhead)«Накладные расходы» на создание потоков, организацию

Измерение производительности Thread Profiler определяет «узкие места» - участки кода многопоточной области,

Thread Profiler for OpenMP Только для OpenMP приложений Окно результатов

Thread Profiler for OpenMP

Thread Profiler for OpenMP

Thread Profiler for OpenMP

Thread Profiler for OpenMP Окно «Regions»: регионы – область кода программы,

Thread Profiler for OpenMP

Задание 6.Исследуйте параллельную работу программы Thread Profiler с теми же параметрами,

Диагностика Thread Profiler – большой дисбаланс – потоки «ждали друг друга»Поток

Определили дисбаланс загрузкиРаспределим работу более эффективно: не по ¼ от всего

Борьба с дисбалансом – перераспределение заданий потокамНовое «распределение работы» по сравнению

Похожие презентации

OpenMP
Практические рекомендации по распараллеливанию с помощью OpenMP и измерению ускорения.
Ошибки

Потоки в современных Windows
Процесс представляет выполняющийся экземпляр программы. Он имеет собственное

Неизбежные «накладные расходы» в многопоточной программе с несколькими параллельными регионами
Создание

Требования на выбор предельных значений переменных внешнего и внутреннего цикла
1. Внутренний

Задание 1. Проект time_paral. Зависимость ускорения от M
1. Для запуска последовательного

Задание 2. Проект time_paral. Зависимость ускорения от M
Демонстрация того, что все

2. Ошибки при многопоточном программировании
1. Конфликты «запись - запись» - два

Ошибки, которые находит ThreadChecker при программировании в OpenMP
1. Конфликты «запись -

3. Презентация материалов по OpenMP
3.1. Курс Гергеля
3.2. Материалы тренингов Intel

3.1. Курс Гергеля
Обзор методов многопоточного программирования для простейших алгоритмов
умножение вектора

3.2. Материалы тренингов Intel
Преобладающая особенность – все показывается на одной задаче
Параллельный

4. Распределение заданий между потоками
По материалам тренинга Intel, проведенного для преподавателей

Цели и задачи
Научиться технике распараллеливания последовательного кода на основе OpenMP
Применять в

Содержание
Стандартный цикл разработки
Изучаемый пример: генерация простых чисел
Как повысить эффективность вычислений

Определение параллелелизма
Два или более процесса или потока выполняются одновременно
Виды параллелелизма

Закон Амдала
Оценка «сверху» для ускорения параллельной программы по закону Амдала

Потоки – «плюсы» и «минусы»
«Плюсы»
Позволяют повысить производительность и полнее использовать системные

Генерация простых чисел
bool TestForPrime(int val)
{ // let’s start checking

Задание 1.
Выполнить запуски последовательной версии первоначального кода (проект Simple_number)
Установить однопоточный режим

Методика разработки
Анализ
Определить участок кода с максимальной долей вычислений
Проектирование (включить многопоточность)
Определить, каким

Провести анализ работы проекта Simple_number
Входные данные: start = 3 end =

Анализ
Параллельная работа потоков будет эффективна в
FindPrimes()
Аргументы в пользу распараллеливания
Мало внутренних

Задание 2
Выполните запуск с параметрами ‘1 5000000’ (границы диапазона поиска простых

Метод проектирования Фостера
Необходимо выполнить 4 шага:
Разбить задачу на максимальное число подзадач
Установить

Проектирование многопоточной программы
«Дробление»
Разбить исходную задачу на подзадачи
«Связи»
Определить типы и количество связей

Модели параллельного программирования
Функциональная декомпозиция
Параллельное выполнение разных подзадач
Разделение на различные подзадачи, но

Способы декомпозиции
Функциональная декомпозиция
Сфокусирована на методах обработки данных, выявляя структуру задачи

Аналогии для функциональной декомпозиции и декомпозиции по данным
Независимые этапы вычислений
Функциональная декомпозиция
Задача

Проектирование
Ожидаемый выигрыш
Как бы его достичь минимальными усилиями?
Долго ли это -

OpenMP
«Вилочный» параллелелизм:
«Мастер» - поток создает команду потоков
Последовательная программа преображается

Проектирование
#pragma omp parallel for
for( int i = start; i <=

Задание 3
Выполнить запуск версии кода с OpenMP
Включите библиотеки OpenMP и установите

Проектирование
А каков был ожидаемый выигрыш?
А как его достичь ?
А как долго

Тестирование правильности работы программы по ее результатам
Результаты неправильные
Каждый запуск – свой

Тестирование правильности работы
Intel® Thread Checker может определить ошибки типа «гонки данных»

Thread Checker
Двойной щелчок «мыши» - находим локализацию ошибки в коде

Задание 4
Примените Thread Checker для анализа правильности выполнения
Создать Thread Checker activity
Запуск

Тестирование правильности работы
Сколько попыток еще предпринять?
Как долго трудиться над этим распараллеливанием?
Thread

Тестирование правильности работы
#pragma omp parallel for
for( int i = start;

Задание 5
Модифицируйте версию кода с OpenMP
Добавьте прагму критической секции в код
Откомпилируйте

Correctness
Работает-то правильно, да ускорение низкое…~1.33X
Разве это предел, к которому мы стремились?
Нет!

Задачи повышения производительности
Параллельный «оверхед» (оverhead)
«Накладные расходы» на создание потоков, организацию

Измерение производительности
Thread Profiler определяет «узкие места» - участки кода многопоточной области,

Thread Profiler for OpenMP
Только для OpenMP приложений
Окно результатов

Thread Profiler for OpenMP
Окно «Regions»: регионы – область кода программы,

Задание 6.
Исследуйте параллельную работу программы Thread Profiler с теми же параметрами,

Диагностика Thread Profiler – большой дисбаланс – потоки «ждали друг друга»
Поток

Определили дисбаланс загрузки
Распределим работу более эффективно: не по ¼ от всего

Борьба с дисбалансом – перераспределение заданий потокам
Новое «распределение работы» по сравнению