Презентация на тему: Параллельные алгоритмы

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

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

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

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

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

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

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

S=0; For(i=0;i

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

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

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

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

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

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

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

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

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

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

r=0; for(i=0;i

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

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

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

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

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

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

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