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

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

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

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

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

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

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

S=0; For(i=0;i

Шаг Процессор 1Процессор 2Процессор 3Процессор Вычисление всех факториалов до 8! включительно Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. F=1; for(i=2;i

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

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

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

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

master Метод коллективного решения (укладка паркета) Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 14 из 26

Метод коллективного решения (укладка паркета) Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. Число порций Обработка порции Обмен данными r – размер порции 15 из 26

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

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

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

r=0; for(i=0;i

Последовательное распространение разряда переноса на четырёх процессорах «Параллельный» алгоритм Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 20 из 26

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

r1=0; r2=1; for(i=0;i

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

Рассмотрены методы построения параллельных алгоритмов Рассмотрена проблема балансировки загрузки процессоров Представлен масштабируемый параллельный метод сложения многоразрядных чисел, основанный на неэффективном последовательном алгоритме Заключение Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 24 из 26

В чем заключается проблема балансировки загрузки? В чем заключаются методы геометрического параллелизма, конвейерного параллелизма и коллективного решения? Чем определяются максимальные ускорения, достигаемые при применении этих методов? В чем отличие методов статической и динамической балансировки загрузки? Вопросы для обсуждения Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 25 из 26

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