Интернет Университет Суперкомпьютерных технологий Лекция 3 Методы построения параллельных программ Учебный курс Введение в параллельные алгоритмы Якобовский Михаил Владимирович проф., д.ф.-м.н. Институт прикладной математики им. М.В.Келдыша РАН, Москва 1

… если для нас представляют интерес реально работающие системы, то требуется убедиться, (и убедить всех сомневающихся) в корректности наших построений … системе часто придется работать в невоспроизводимых обстоятельствах, и мы едва ли можем ожидать сколько-нибудь серьезной помощи от тестов Dijkstra E.W Предварительные замечания Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 2 из 41

Время выполнения параллельного алгоритма Методы построения параллельных алгоритмов –Статическая балансировка метод сдваивания геометрический параллелизм конвейерный параллелизм –Динамическая балансировка коллективное решение диффузная балансировка загрузки Содержание лекции Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 3 из 41

Обладает запасом внутреннего параллелизма –Есть возможность одновременного выполнения множества операций Допускает возможность равномерного распределения вычислительных операций между процессорами Обладает низким уровнем накладных расходов Хороший параллельный алгоритм Москва, 2012 г. большим большим числом Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 4 из 41

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. К вопросу о накладных расходах - доля операций выполняемых последовательно - дополнительные расходы времени 5 из 41

Закон Амдаля Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. - доля операций выполняемых последовательно 6 из 41

Операции, отсутствующие в наилучшем последовательном алгоритме: –Синхронизация –Обмен данными –Дублирование операций –Новые операции Накладные расходы Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 7 из 41

Потери времени на передачу данных между процессами Процессор 1 Процессор 2 Обмен данными Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 8 из 41

Потери времени на ожидание долго выполняющихся процессов Процессор 1 Процессор 2 Процессор 3 Синхронизация Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 9 из 41

S=0; For(i=0;i

Шаг Процессор 1Процессор 2Процессор 3Процессор Новые операции Москва, 2012 г. Шаг Процессор 1Процессор 2Процессор 3Процессор 4 12! !4! !6!7!8! Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 11 из 41

Операции, отсутствующие в наилучшем последовательном алгоритме: –Синхронизация –Обмен данными –Дублирование операций –Новые операции Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. - дополнительные расходы времени 12 из 41

Статическая балансировка загрузки –метод сдваивания –геометрический параллелизм Динамическая балансировка загрузки –Метод коллективного решения Принципы организации параллельных вычислений Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 13 из 41

Выполнение редукционных и им подобных операций –Определение суммы элементов массива –Определение минимального элемента массива –Широковещательная рассылка данных –… Метод сдваивания Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 14 из 41

Метод сдваивания Москва, 2012 г. Каскадная схема Модифицированная каскадная схема В.П.Гергель Основы параллельных вычислений, лекция 4, слайд 23 В.П.Гергель Основы параллельных вычислений, лекция 4, слайд 23 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 15 из 41

Циклическая обработка локально связанных данных –Обработка изображений –Обработка данных, заданных на решетках или произвольных графах –Моделирование физических процессов (течений жидкости и газов, теплопереноса, упругости, …) –… Метод геометрического параллелизма Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 16 из 41

Пример модельной задачи: Стена Фокса Москва, 2012 г. n – ширина стены к – высота стены Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 17 из 41

Метод геометрического параллелизма Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 18 из 41

А почему? Москва, 2012 г. for(шаг=0;шаг

? Москва, 2012 г =< >= =< >= =< >= =< >= =< >= for(шаг=0;шаг

? Москва, 2012 г =< >= =< >= =< >= =< >= =< >= for(шаг=0;шаг

? Москва, 2012 г =< =< >= =< >= =< >= =< >= >= for(шаг=0;шаг

? Москва, 2012 г =< =< >= =< >= =< >= =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 23 из 41

! Москва, 2012 г =< =< >= =< >= =< >= =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 24 из 41

! Москва, 2012 г =< =< >= =< >= =< >= =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 25 из 41

! Москва, 2012 г =< =< >= =< >= =< >= =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 26 из 41

! Москва, 2012 г =< =< >= =< >= =< >= =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 27 из 41

! Москва, 2012 г =< =< >= =< >= =< >= =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 28 из 41

! Москва, 2012 г =< =< >= =< >= =< >= =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 29 из 41

! Москва, 2012 г =< =< >= =< >= =< >= =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 30 из 41

! Москва, 2012 г =< =< >= =< >= =< >= =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 31 из 41

! Москва, 2012 г =< =< >= =< >= =< >= =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 32 из 41

! Москва, 2012 г =< =< >= =< >= =< >= =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 33 из 41

! Москва, 2012 г =< >= =< =< >= >= =< =< >= >= Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 34 из 41

! Москва, 2012 г. for(шаг=0;шаг0) Recv(rank-1, место готово? ) if(rank

Решение множества независимых друг от друга задач: –Табулирование функций –Решение задач методами Монте-Карло –Численное интегрирование гладких многомерных функций –… Метод коллективного решения Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 36 из 41

master Метод коллективного решения Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 37 из 41

Пример модельной задачи: Укладка паркета Москва, 2012 г. Число порций Обработка порции Обмен данными r – размер порции Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 38 из 41

Как правильно? Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. r – размер порции или Зависит ли время передачи данных от размера порции (задания)? 39 из 41

Send(a i ); Send(a i+1 ); Recv(s); Вычисление определенного интеграла Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. aiai a i+1 40 из 41

Отмечена важность использования простых с логической точки зрения алгоритмов Рассмотрены основные причины потерь времени при выполнении параллельных алгоритмов Рассмотрен метод геометрического параллелизма, относящийся к классу методов статической балансировки загрузки процессоров Рассмотрен метод коллективного решения, относящийся к классу методов динамической балансировки загрузки процессоров Заключение Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 41 из 41

Якобовский М.В. проф., д.ф.-м.н., зав. сектором «Программного обеспечения вычислительных систем и сетей» Института прикладной математики им. М.В.Келдыша Российской академии наук mail: web: Контакты Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 42 из 41