Нижегородский государственный университет им. Н.И. Лобачевского Зимняя школа по параллельному программированию Практикум по технологиям параллельного программирования (на примере учебно-исследовательской задачи) Гергель В.П., проф., д.т.н., кафедра МО ЭВМ ВМК ННГУ

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Учебная задача В качестве учебного примера рассматривается проблема численного решения задачи Дирихле для уравнения Пуассона

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Последовательные методы решения Метод конечных разностей

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Итерационные схемы Метод Гаусса-Зейделя Трудоемкость T = kmN 2 N - число узлов по каждой координате m - число операций на узел k - количество итераций

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Алгоритм 1.1

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Пример расчетов N = 100 eps= 0.1 k = 210

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Организация параллельных вычислений Системы с общей памятью (мультипроцессоры) Системы с распределенной памятью (мультикомпьютеры)

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Системы с общей памятью Возможные подходы –новые алгоритмические языки (OCCAM,…), –существующие алгоритмические языки, расширенные набором операторов для параллельных вычислений (HPF,…), –использование внеязыковых средств (директивы, комментарии,...) или библиотек

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Технология OpenMP Вилочный (fork-join) –пульсирующий - параллелизм - выделение в программе параллельных областей

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Алгоритм 1.2

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Результаты экспериментов

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Оценка подхода (+) Алгоритм обеспечивает решение задачи (+) Может быть задействовано до N 2 процессов (-) Чрезмерная синхронизация (-) Слабая загрузка процессоров Низкая эффективность

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Проблема: блокировки при взаимоисключении

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Алгоритм 1.3

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Результаты экспериментов

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Оценка подхода (+) Существенное снижение обращений к общей переменной (-) Снижение показателя максимально возможного параллелизма до N Лучшие показатели ускорения

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Проблема: Неоднозначность вычислений !!! Результаты различаются от запуска к запуску – метод хаотической релаксации (chaotic relaxation) Причина: состязание потоков (race condition)

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Состязание потоков Выход: захват и блокировка используемых строк

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Проблема: взаимоблокировка Тупик

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Разрешение тупиков Решение: соблюдение строгой последовательности блокировки строк !!! Однозначность вычислений не обеспечивается

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Метод Гаусса-Якоби Разделение места хранения результатов на предыдущей и текущей итерации

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Алгоритм 1.4

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Результаты экспериментов

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Оценка подхода (+) Однозначность вычислений (-) Использование дополнительной памяти (-) Меньшая скорость сходимости Возможность повышения эффективности расчетов

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Схема чередования обработки строк

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Оценка подхода (+/-) Однозначность вычислений, но не совпадение результатов последовательных расчетов (-) Меньшая скорость сходимости Возможность повышения эффективности расчетов

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Волновые схемы параллельных вычислений… Выполнение только тех вычислительных действий, которые выполняет последовательный метод и, как результат, получение совпадающих результатов приводит к порождению волновой схемы расчетов (wavefront or hyperplane methods)

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Волновые схемы параллельных вычислений

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Алгоритм 1.5

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Алгоритм 1.5'

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Результаты экспериментов

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Оценка подхода (-) Неэффективность использования кэша Возможность повышения эффективности расчетов

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Блочное представление данных

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Алгоритм 1.6

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Результаты экспериментов

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Оценка подхода (+) Возможность тонкой подстройки под имеющийся кэш (-) Возможность простоев процессоров Возможность повышения эффективности расчетов

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Балансировка вычислительной нагрузки Очередь заданий

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Организация параллельных вычислений для систем с распределенной памятью Разделение данных Обмен сообщениями

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Ленточная схема разделения данных

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Схема алгоритма

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Схема обмена данными между процессорами !!! Последовательное выполнение операций передачи данных

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Параллельное выполнение операций передачи данных

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Коллективные операции

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Результаты экспериментов

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Оценка подхода (-) Результаты расчетов отличаются от результатов последовательных вычислений

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Волновые вычисления при ленточной схеме разделения данных

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Блочная схема разделения данных…

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Блочная схема разделения данных

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Вычислительный конвейер (множественная волна)

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Операции передачи данных

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Лабораторный практикум… Практикум состоит из 2-х частей: Практикум для разработки параллельных программ с использованием технологии OpenMP для вычислительных систем с общей памятью, Практикум для разработки параллельных программ с использованием технологии MPI для вычислительных систем с распределенной памятью при использовании ленточной и блочной схемы распределения данных. В качестве задания повышенной сложности может быть выполнена разработка параллельной программы с совместным использованием технологий MPI и OpenMP.

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Лабораторный практикум… Выполнение заданий практикума рекомендуется проводить группами из 2 человек. Первоначально все обучаемые, выбравшие то или иное задание, выполняют разработку базового варианта работы. Далее после обсуждения результатов разработки каждая группа выбирает индивидуальный вариант постановки задания для продолжения работ.

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Лабораторный практикум… Практическое занятие 1: Разработка параллельных программ с использованием OpenMP Необходимый теоретический материал Разделы 2 и 3 лекционного материала Задание 1: Организация параллельных вычислений при использовании ленточной схемы разделения данных Разделение вариантов может осуществляться по реализуемым методам и схемам организации вычислений: - Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби, - Схема вычислений: прямая схема, чередование полос, шахматная схема, диагональная волна Общее количество вариантов заданий – 5 (для метода Гаусса-Якоби оправдано использование только прямой схемы вычислений).

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Лабораторный практикум… Задание 2: Организация параллельных вычислений при использовании блочной схемы разделения данных Разделение вариантов может осуществляться по реализуемым методам, схемам организации вычислений и способам формирования блоков: - Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби, - Схема вычислений: неволновая схема, множественная волна, - Способ формирования блоков: блоки фиксированного размера, блоки задаваемого размера. Общее количество вариантов заданий – 6 (задания, предполагающие использование блоков задаваемого размера, отличаются более высокой трудоемкостью для выполнения).

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Лабораторный практикум… Участники школы выполняют одно из представленных заданий по выбору. По завершении разработки программ участники выполняют несколько вычислительных экспериментов по оценке эффективности параллельных вычислений. По результатам работ проводится общая дискуссия.

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Лабораторный практикум… Практическое занятие 2: Разработка параллельных программ с использованием MPI Необходимый теоретический материал Разделы 2 и 4 лекционного материала. Задание 1: Организация параллельных вычислений при использовании ленточной схемы разделения данных Разделение вариантов может осуществляться по реализуемым методам, используемым режимам передачи данных, схемам организации вычислений: - Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби, - Режим передачи данных: стандартный, асинхронный, буферизуемый, - Схема вычислений: неволновая схема, прямая волна, диагональная волна. Общее количество вариантов заданий –18.

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Лабораторный практикум Задание 2: Организация параллельных вычислений при использовании блочной схемы разделения данных Разделение вариантов может осуществляться по реализуемым методам, используемым режимам передачи данных, схемам организации вычислений: - Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби, - Режим передачи данных: стандартный, асинхронный, буферизуемый, - Схема вычислений: неволновая схема, множественная волна Общее количество вариантов заданий –9.

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Литература 1. Технологии параллельного программирования. / Материалы Зимней школы по параллельному программированию. – Н.Новгород: Нижегородский университет, Интел, Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. - Н.Новгород, ННГУ, Информационные материалы по MPI ( 4. Информационные материалы по OpenMP (

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Контакты Нижегородский государственный университет Факультет вычислительной математики и кибернетики Кафедра математического обеспечения ЭВМ

ННГУ, Н.Новгород, Зимняя школа Практикум по технологиям параллельного программирования Вопросы, Замечания, Дополнения,…