Гергель В.П., проф., д.т.н.,
кафедра МО ЭВМ ВМК ННГУ
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Нижегородский государственный университетим. Н.И. ЛобачевскогоЗимняя школа по параллельному программированиюПрактикум по технологиям параллельного программирования (на примере учебно-исследовательской задачи) презентация
Содержание
- 1. Нижегородский государственный университетим. Н.И. ЛобачевскогоЗимняя школа по параллельному программированиюПрактикум по технологиям параллельного программирования (на примере учебно-исследовательской задачи)
- 2. Практикум по технологиям параллельного программирования Учебная задача
- 3. Практикум по технологиям параллельного программирования Последовательные методы решения Метод конечных разностей
- 4. Практикум по технологиям параллельного программирования Итерационные схемы
- 5. Практикум по технологиям параллельного программирования Алгоритм 1.1
- 6. Практикум по технологиям параллельного программирования Пример расчетов
- 7. Практикум по технологиям параллельного программирования Организация параллельных
- 8. Практикум по технологиям параллельного программирования Системы с
- 9. Практикум по технологиям параллельного программирования Технология OpenMP
- 10. Практикум по технологиям параллельного программирования Алгоритм 1.2
- 11. Практикум по технологиям параллельного программирования Результаты экспериментов
- 12. Практикум по технологиям параллельного программирования Оценка подхода
- 13. Практикум по технологиям параллельного программирования Проблема: блокировки при взаимоисключении
- 14. Практикум по технологиям параллельного программирования Алгоритм 1.3
- 15. Практикум по технологиям параллельного программирования Результаты экспериментов
- 16. Практикум по технологиям параллельного программирования Оценка подхода
- 17. Практикум по технологиям параллельного программирования Проблема: Неоднозначность
- 18. Практикум по технологиям параллельного программирования Состязание потоков Выход: захват и блокировка используемых строк
- 19. Практикум по технологиям параллельного программирования Проблема: взаимоблокировка Тупик
- 20. Практикум по технологиям параллельного программирования Разрешение тупиков
- 21. Практикум по технологиям параллельного программирования Метод Гаусса-Якоби
- 22. Практикум по технологиям параллельного программирования Алгоритм 1.4
- 23. Практикум по технологиям параллельного программирования Результаты экспериментов
- 24. Практикум по технологиям параллельного программирования Оценка подхода
- 25. Практикум по технологиям параллельного программирования Схема чередования обработки строк
- 26. Практикум по технологиям параллельного программирования Оценка подхода
- 27. Практикум по технологиям параллельного программирования Волновые схемы
- 28. Практикум по технологиям параллельного программирования Волновые схемы параллельных вычислений
- 29. Практикум по технологиям параллельного программирования Алгоритм 1.5
- 30. Практикум по технологиям параллельного программирования Алгоритм 1.5'
- 31. Практикум по технологиям параллельного программирования Результаты экспериментов
- 32. Практикум по технологиям параллельного программирования Оценка подхода
- 33. Практикум по технологиям параллельного программирования Блочное представление данных
- 34. Практикум по технологиям параллельного программирования Алгоритм 1.6
- 35. Практикум по технологиям параллельного программирования Результаты экспериментов
- 36. Практикум по технологиям параллельного программирования Оценка подхода
- 37. Практикум по технологиям параллельного программирования Балансировка вычислительной нагрузки Очередь заданий
- 38. Практикум по технологиям параллельного программирования Организация параллельных
- 39. Практикум по технологиям параллельного программирования Ленточная схема разделения данных
- 40. Практикум по технологиям параллельного программирования Схема алгоритма
- 41. Практикум по технологиям параллельного программирования Схема обмена
- 42. Практикум по технологиям параллельного программирования Параллельное выполнение операций передачи данных
- 43. Практикум по технологиям параллельного программирования Коллективные операции
- 44. Практикум по технологиям параллельного программирования Результаты экспериментов
- 45. Практикум по технологиям параллельного программирования Оценка подхода (-) Результаты расчетов отличаются от результатов последовательных вычислений
- 46. Практикум по технологиям параллельного программирования Волновые вычисления при ленточной схеме разделения данных
- 47. Практикум по технологиям параллельного программирования Блочная схема разделения данных…
- 48. Практикум по технологиям параллельного программирования Блочная схема разделения данных
- 49. Практикум по технологиям параллельного программирования Вычислительный конвейер (множественная волна)
- 50. Практикум по технологиям параллельного программирования Операции передачи данных
- 51. Практикум по технологиям параллельного программирования Лабораторный практикум…
- 52. Практикум по технологиям параллельного программирования Лабораторный практикум…
- 53. Практикум по технологиям параллельного программирования Лабораторный практикум…
- 54. Практикум по технологиям параллельного программирования Лабораторный практикум…
- 55. Практикум по технологиям параллельного программирования Лабораторный практикум…
- 56. Практикум по технологиям параллельного программирования Лабораторный практикум…
- 57. Практикум по технологиям параллельного программирования Лабораторный практикум
- 58. Практикум по технологиям параллельного программирования Литература 1. Технологии
- 59. Практикум по технологиям параллельного программирования Контакты Нижегородский
- 60. Практикум по технологиям параллельного программирования Вопросы, Замечания, Дополнения,…
Практикум по технологиям параллельного программирования Учебная задача В качестве учебного примера рассматривается проблема численного решения задачи Дирихле для уравнения Пуассона
Слайд 1Нижегородский государственный университет им. Н.И. Лобачевского Зимняя школа по параллельному программированию Практикум по технологиям
параллельного программирования
(на примере учебно-исследовательской задачи)
Слайд 2Практикум по технологиям параллельного программирования
Учебная задача
В качестве учебного примера рассматривается
проблема численного решения задачи Дирихле для уравнения Пуассона
Слайд 3Практикум по технологиям параллельного программирования
Последовательные методы решения
Метод конечных разностей
Слайд 4Практикум по технологиям параллельного программирования
Итерационные схемы
Метод Гаусса-Зейделя
Трудоемкость
T = kmN2
N - число узлов по каждой координате
m - число операций на узел
k - количество итераций
N - число узлов по каждой координате
m - число операций на узел
k - количество итераций
Слайд 7Практикум по технологиям параллельного программирования
Организация параллельных вычислений
Системы с общей памятью (мультипроцессоры)
Системы
с распределенной памятью (мультикомпьютеры)
Слайд 8Практикум по технологиям параллельного программирования
Системы с общей памятью
Возможные подходы
новые алгоритмические языки
(OCCAM,…),
существующие алгоритмические языки, расширенные набором операторов для параллельных вычислений (HPF,…),
использование внеязыковых средств (директивы, комментарии, ...) или библиотек
существующие алгоритмические языки, расширенные набором операторов для параллельных вычислений (HPF,…),
использование внеязыковых средств (директивы, комментарии, ...) или библиотек
Слайд 9Практикум по технологиям параллельного программирования
Технология OpenMP
Вилочный (fork-join) –пульсирующий - параллелизм -
выделение в программе параллельных областей
Слайд 12Практикум по технологиям параллельного программирования
Оценка подхода
(+) Алгоритм обеспечивает решение задачи
(+) Может
быть задействовано до N2 процессов
(-) Чрезмерная синхронизация
(-) Слабая загрузка процессоров
⇒ Низкая эффективность
(-) Чрезмерная синхронизация
(-) Слабая загрузка процессоров
⇒ Низкая эффективность
Слайд 13Практикум по технологиям параллельного программирования
Проблема: блокировки при взаимоисключении
Слайд 16Практикум по технологиям параллельного программирования
Оценка подхода
(+) Существенное снижение обращений к общей
переменной
(-) Снижение показателя максимально возможного параллелизма до N
⇒ Лучшие показатели ускорения
(-) Снижение показателя максимально возможного параллелизма до N
⇒ Лучшие показатели ускорения
Слайд 17Практикум по технологиям параллельного программирования
Проблема: Неоднозначность вычислений
!!! Результаты различаются от запуска
к запуску – метод хаотической релаксации (chaotic relaxation)
Причина: состязание потоков (race condition)
Причина: состязание потоков (race condition)
Слайд 18Практикум по технологиям параллельного программирования
Состязание потоков
Выход: захват и блокировка используемых строк
Слайд 20Практикум по технологиям параллельного программирования
Разрешение тупиков
Решение: соблюдение строгой последовательности блокировки строк
!!!
Однозначность вычислений не обеспечивается
Слайд 21Практикум по технологиям параллельного программирования
Метод Гаусса-Якоби
Разделение места хранения результатов на предыдущей
и текущей итерации
Слайд 24Практикум по технологиям параллельного программирования
Оценка подхода
(+) Однозначность вычислений
(-) Использование дополнительной памяти
(-)
Меньшая скорость сходимости
⇒ Возможность повышения эффективности расчетов
⇒ Возможность повышения эффективности расчетов
Слайд 26Практикум по технологиям параллельного программирования
Оценка подхода
(+/-) Однозначность вычислений, но не совпадение
результатов последовательных расчетов
(-) Меньшая скорость сходимости
⇒ Возможность повышения эффективности расчетов
(-) Меньшая скорость сходимости
⇒ Возможность повышения эффективности расчетов
Слайд 27Практикум по технологиям параллельного программирования
Волновые схемы параллельных вычислений…
Выполнение только тех вычислительных
действий, которые выполняет последовательный метод и, как результат, получение совпадающих результатов приводит к порождению волновой схемы расчетов (wavefront or hyperplane methods)
Слайд 28Практикум по технологиям параллельного программирования
Волновые схемы параллельных вычислений
Слайд 32Практикум по технологиям параллельного программирования
Оценка подхода
(-) Неэффективность использования кэша
⇒ Возможность повышения
эффективности расчетов
Слайд 36Практикум по технологиям параллельного программирования
Оценка подхода
(+) Возможность тонкой подстройки под имеющийся
кэш
(-) Возможность простоев процессоров
⇒ Возможность повышения эффективности расчетов
(-) Возможность простоев процессоров
⇒ Возможность повышения эффективности расчетов
Слайд 37Практикум по технологиям параллельного программирования
Балансировка вычислительной нагрузки
Очередь заданий
Слайд 38Практикум по технологиям параллельного программирования
Организация параллельных вычислений для систем с распределенной
памятью
Разделение данных
Обмен сообщениями
Слайд 41Практикум по технологиям параллельного программирования
Схема обмена данными между процессорами
!!! Последовательное выполнение
операций передачи данных
Слайд 42Практикум по технологиям параллельного программирования
Параллельное выполнение операций передачи данных
Слайд 45Практикум по технологиям параллельного программирования
Оценка подхода
(-) Результаты расчетов отличаются от результатов
последовательных вычислений
Слайд 46Практикум по технологиям параллельного программирования
Волновые вычисления при ленточной схеме разделения данных
Слайд 49Практикум по технологиям параллельного программирования
Вычислительный конвейер (множественная волна)
Слайд 51Практикум по технологиям параллельного программирования
Лабораторный практикум…
Практикум состоит из 2-х частей:
Практикум для
разработки параллельных программ с использованием технологии OpenMP для вычислительных систем с общей памятью,
Практикум для разработки параллельных программ с использованием технологии MPI для вычислительных систем с распределенной памятью при использовании ленточной и блочной схемы распределения данных.
В качестве задания повышенной сложности может быть выполнена разработка параллельной программы с совместным использованием технологий MPI и OpenMP.
Практикум для разработки параллельных программ с использованием технологии MPI для вычислительных систем с распределенной памятью при использовании ленточной и блочной схемы распределения данных.
В качестве задания повышенной сложности может быть выполнена разработка параллельной программы с совместным использованием технологий MPI и OpenMP.
Слайд 52Практикум по технологиям параллельного программирования
Лабораторный практикум…
Выполнение заданий практикума рекомендуется проводить группами
из 2 человек. Первоначально все обучаемые, выбравшие то или иное задание, выполняют разработку базового варианта работы. Далее после обсуждения результатов разработки каждая группа выбирает индивидуальный вариант постановки задания для продолжения работ.
Слайд 53Практикум по технологиям параллельного программирования
Лабораторный практикум…
Практическое занятие 1: Разработка параллельных программ
с использованием OpenMP
Необходимый теоретический материал
Разделы 2 и 3 лекционного материала
Задание 1: Организация параллельных вычислений при использовании ленточной схемы разделения данных
Разделение вариантов может осуществляться по реализуемым методам и схемам организации вычислений:
- Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби,
- Схема вычислений: прямая схема, чередование полос, шахматная схема, диагональная волна
Общее количество вариантов заданий – 5 (для метода Гаусса-Якоби оправдано использование только прямой схемы вычислений).
Необходимый теоретический материал
Разделы 2 и 3 лекционного материала
Задание 1: Организация параллельных вычислений при использовании ленточной схемы разделения данных
Разделение вариантов может осуществляться по реализуемым методам и схемам организации вычислений:
- Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби,
- Схема вычислений: прямая схема, чередование полос, шахматная схема, диагональная волна
Общее количество вариантов заданий – 5 (для метода Гаусса-Якоби оправдано использование только прямой схемы вычислений).
Слайд 54Практикум по технологиям параллельного программирования
Лабораторный практикум…
Задание 2: Организация параллельных вычислений при
использовании блочной схемы разделения данных
Разделение вариантов может осуществляться по реализуемым методам, схемам организации вычислений и способам формирования блоков:
- Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби,
- Схема вычислений: неволновая схема, множественная волна,
- Способ формирования блоков: блоки фиксированного размера, блоки задаваемого размера.
Общее количество вариантов заданий – 6 (задания, предполагающие использование блоков задаваемого размера, отличаются более высокой трудоемкостью для выполнения).
Разделение вариантов может осуществляться по реализуемым методам, схемам организации вычислений и способам формирования блоков:
- Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби,
- Схема вычислений: неволновая схема, множественная волна,
- Способ формирования блоков: блоки фиксированного размера, блоки задаваемого размера.
Общее количество вариантов заданий – 6 (задания, предполагающие использование блоков задаваемого размера, отличаются более высокой трудоемкостью для выполнения).
Слайд 55Практикум по технологиям параллельного программирования
Лабораторный практикум…
Участники школы выполняют одно из представленных
заданий по выбору. По завершении разработки программ участники выполняют несколько вычислительных экспериментов по оценке эффективности параллельных вычислений. По результатам работ проводится общая дискуссия.
Слайд 56Практикум по технологиям параллельного программирования
Лабораторный практикум…
Практическое занятие 2: Разработка параллельных программ
с использованием MPI
Необходимый теоретический материал
Разделы 2 и 4 лекционного материала.
Задание 1: Организация параллельных вычислений при использовании ленточной схемы разделения данных
Разделение вариантов может осуществляться по реализуемым методам, используемым режимам передачи данных, схемам организации вычислений:
- Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби,
- Режим передачи данных: стандартный, асинхронный, буферизуемый,
- Схема вычислений: неволновая схема, прямая волна, диагональная волна.
Общее количество вариантов заданий –18.
Необходимый теоретический материал
Разделы 2 и 4 лекционного материала.
Задание 1: Организация параллельных вычислений при использовании ленточной схемы разделения данных
Разделение вариантов может осуществляться по реализуемым методам, используемым режимам передачи данных, схемам организации вычислений:
- Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби,
- Режим передачи данных: стандартный, асинхронный, буферизуемый,
- Схема вычислений: неволновая схема, прямая волна, диагональная волна.
Общее количество вариантов заданий –18.
Слайд 57Практикум по технологиям параллельного программирования
Лабораторный практикум
Задание 2: Организация параллельных вычислений при
использовании блочной схемы разделения данных
Разделение вариантов может осуществляться по реализуемым методам, используемым режимам передачи данных, схемам организации вычислений:
- Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби,
- Режим передачи данных: стандартный, асинхронный, буферизуемый,
- Схема вычислений: неволновая схема, множественная волна
Общее количество вариантов заданий –9.
Разделение вариантов может осуществляться по реализуемым методам, используемым режимам передачи данных, схемам организации вычислений:
- Метод: Метод Гаусса-Зейделя, метод Гаусса-Якоби,
- Режим передачи данных: стандартный, асинхронный, буферизуемый,
- Схема вычислений: неволновая схема, множественная волна
Общее количество вариантов заданий –9.
Слайд 58Практикум по технологиям параллельного программирования
Литература
1. Технологии параллельного программирования. / Материалы Зимней школы
по параллельному программированию. – Н.Новгород: Нижегородский университет, Интел, 2004.
2. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. - Н.Новгород, ННГУ, 2001.
3. Информационные материалы по MPI (http://www.mpi-forum.org)
4. Информационные материалы по OpenMP (http://www.openmp.org)
2. Гергель В.П., Стронгин Р.Г. Основы параллельных вычислений для многопроцессорных вычислительных систем. - Н.Новгород, ННГУ, 2001.
3. Информационные материалы по MPI (http://www.mpi-forum.org)
4. Информационные материалы по OpenMP (http://www.openmp.org)
Слайд 59Практикум по технологиям параллельного программирования
Контакты
Нижегородский государственный университет
Факультет вычислительной математики и кибернетики
Кафедра
математического обеспечения ЭВМ
gergel@unn.ac.ru
www.unn.ac.ru
www.software.unn.ac.ru
www.software.unn.ac.ru/mo_evm
www.itlab.unn.ru
gergel@unn.ac.ru
www.unn.ac.ru
www.software.unn.ac.ru
www.software.unn.ac.ru/mo_evm
www.itlab.unn.ru
