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

Содержание слайда: Практические рекомендации по распараллеливанию с помощью OpenMP и измерению ускорения. Ошибки при многопоточном программировании. Распределение заданий между потоками ЛЕКЦИЯ №4

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

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

Содержание слайда: Потоки в современных Windows Процесс представляет выполняющийся экземпляр программы. Он имеет собственное адресное пространство, где содержаться его код и данные. Процесс должен содержать минимум как один поток, так как именно он, а не процесс, является единицей планирования (данная операционная система относится к системам разделения времени, т.е. каждой единице предоставляется квант процессорного времени). Процесс может создавать несколько потоков, выполняемых в его адресном пространстве.

Содержание слайда: Классы потоков. Потоки OpenMP

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

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

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

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

Содержание слайда: Тестируемый код – проект 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;

Содержание слайда: Тестируемый код – проект 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;

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

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

Содержание слайда: Задание 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

Содержание слайда: Задание 2. Проект time_paral. Зависимость ускорения от M Демонстрация того, что все «накладные расходы» сосредоточены в первом создаваемом многопоточном регионе (в этом варианте – вход в три одинаковых параллельных региона): Запуск с аргументами командной строки 5 10 10000 1 11 2

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

Содержание слайда: Ошибки, которые находит ThreadChecker при программировании в OpenMP

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

Содержание слайда: 3.1. Курс Гергеля Обзор методов многопоточного программирования для простейших алгоритмов умножение вектора на вектор матрицы на матрицу решение систем линейных уравнений сортировки Обзор основных конструкций OpenMP Особенность курса в основном обзорный характер, «охват материала» акцент – на рассмотрении алгоритмов

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

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

Содержание слайда: Цели и задачи Научиться технике распараллеливания последовательного кода на основе OpenMP Применять в цикле разработки инструменты Intel Оценивать максимально возможное ускорение многопоточной программы по закону Амдала

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

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

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

Содержание слайда: Процессы и потоки В современных операционных системах процесс представляет выполняющийся экземпляр программы Процесс – единица работы, заявка на потребление системных ресурсов Процесс – исполнение последовательности действий В начале выполнения процесс представляет собой один поток Потоки могут создавать новые потоки в пределах одного процесса

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

Содержание слайда: Генерация простых чисел 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); } }

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

Содержание слайда: Методика разработки Анализ Определить участок кода с максимальной долей вычислений Проектирование (включить многопоточность) Определить, каким образом может быть использована многопоточность Тестирование правильности работы Выявить источники ошибок, связанных с потоками Измерение производительности Достигнуть максимальной производительности работы многопоточного приложения

Содержание слайда: Рабочий цикл

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

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

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

Содержание слайда: Анализ - Call Graph

Содержание слайда: Анализ Параллельная работа потоков будет эффективна в FindPrimes() Аргументы в пользу распараллеливания Мало внутренних взаимозависимостей Возможен параллелелизм по данным Занимает более 95% всего времени работы приложения

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

Содержание слайда: Метод проектирования Фостера Необходимо выполнить 4 шага: Разбить задачу на максимальное число подзадач Установить связи «данные - вычисления» «Агломерация»: составить задания, которые можно выполнять параллельно «Распределение» - распределить задания между процессорами/потоками

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

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

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

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

Содержание слайда: Проектирование Ожидаемый выигрыш Как бы его достичь минимальными усилиями? Долго ли это - распараллелить? Сразу получится – или «путем итераций»?

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

Содержание слайда: Проектирование #pragma omp parallel for for( int i = start; i <= end; i+= 2 ){ if( TestForPrime(i) ) globalPrimes[gPrimesFound++] = i; ShowProgress(i, range); }

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

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

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

Содержание слайда: Тестирование правильности работы Intel® Thread Checker может определить ошибки типа «гонки данных» или «конфликты запись-запись, чтение - запись»

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда: Задание 4 Примените Thread Checker для анализа правильности выполнения Создать Thread Checker activity Запуск приложения с параметрами 3 20 Есть ошибки ?

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

Содержание слайда: Тестирование правильности работы #pragma omp parallel for for( int i = start; i <= end; i+= 2 ){ if( TestForPrime(i) ) #pragma omp critical globalPrimes[gPrimesFound++] = i; //ShowProgress(i, range); }

Содержание слайда: Задание 5 Модифицируйте версию кода с OpenMP Добавьте прагму критической секции в код Откомпилируйте код Проверьте Thread Checker Если будут ошибки, исправьте их, и снова выполните проверку Thread Checker Запуск ‘1 5000000’ для сравнения Проверьте Thread Checker Ускорение ?

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

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

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

Содержание слайда: Thread Profiler for OpenMP

Содержание слайда: Thread Profiler for OpenMP

Содержание слайда: Thread Profiler for OpenMP

Содержание слайда: Thread Profiler for OpenMP

Содержание слайда: Thread Profiler for OpenMP

Содержание слайда: Thread Profiler for OpenMP

Содержание слайда: Задание 6. Исследуйте параллельную работу программы Thread Profiler с теми же параметрами, что и базовое измерение Число потоков установите, равное 4

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

Содержание слайда: Определили дисбаланс загрузки Распределим работу более эффективно: не по ¼ от всего цикла сразу каждому потоку, «пока не встретимся», а каждому по несколько итераций цикла, «пока не встретимся», затем – новые несколько итераций

Содержание слайда: Борьба с дисбалансом – перераспределение заданий потокам Новое «распределение работы» по сравнению со старым будет следующим образом выглядеть в графическом представлении:

Содержание слайда: Задание 7 Для уменьшения дисбаланса установить schedule (static, 8) «клаузу» OpenMP для parallel for pragma Запуск Ускорение?