Интернет Университет Суперкомпьютерных технологий Лекция 4 Методы построения параллельных программ (продолжение) Учебный курс Введение в параллельные алгоритмы.

Презентация:



Advertisements
Похожие презентации
Интернет Университет Суперкомпьютерных технологий Лекция 3 Методы построения параллельных программ (продолжение) Учебный курс Введение в параллельные алгоритмы.
Advertisements

Интернет Университет Суперкомпьютерных технологий Лекция 3 Методы построения параллельных программ (продолжение) Учебный курс Введение в параллельные алгоритмы.
Методы построения параллельных программ
Интернет Университет Суперкомпьютерных технологий Лекция 3 Методы построения параллельных программ Учебный курс Введение в параллельные алгоритмы Якобовский.
Интернет Университет Суперкомпьютерных технологий Якобовский Михаил Владимирович проф., д.ф.-м.н. Институт прикладной математики им. М.В.Келдыша РАН, Москва.
Интернет Университет Суперкомпьютерных технологий Якобовский Михаил Владимирович проф., д.ф.-м.н. Институт прикладной математики им. М.В.Келдыша РАН, Москва.
1 МФТИ Потери производительности Параллельные алгоритмы Якобовский Михаил Владимирович д.ф.-м.н. Институт математического моделирования РАН, Москва.
Интернет Университет Суперкомпьютерных технологий Лекция 3 Сортировка данных с точки зрения МВС (начало) Учебный курс Введение в параллельные алгоритмы.
Интернет Университет Суперкомпьютерных технологий Лекция 1 Основные понятия Учебный курс Введение в параллельные алгоритмы Якобовский М.В., д.ф.-м.н. Институт.
Типовые расчёты Растворы
Урок повторения по теме: «Сила». Задание 1 Задание 2.
Ребусы Свириденковой Лизы Ученицы 6 класса «А». 10.

Школьная форма Презентация для родительского собрания.
Michael Jackson
Интернет Университет Суперкомпьютерных технологий Лекция 2 Основные понятия Учебный курс Введение в параллельные алгоритмы Якобовский М.В., проф., д.ф.-м.н.
Масштаб 1 : 5000 Приложение 1 к решению Совета депутатов города Новосибирска от
Масштаб 1 : 5000 Приложение 1 к решению Совета депутатов города Новосибирска от _____________ ______.
Маршрутный лист «Числа до 100» ? ? ?
Масштаб 1 : 5000 Приложение 1 к решению Совета депутатов города Новосибирска от _____________ ______.
Транксрипт:

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

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

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

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

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

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

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

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 8 Метод конвейерного параллелизма for(t=0; t

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

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 10 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 11 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 12 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 13 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 14 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 15 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 16 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 17 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3

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

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 19 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3

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

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 21 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 22 Объём хранимых данных процессор 0 процессор 1 процессор 2 процессор 3

Москва, 2012 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 23 Учет стартовых и финальных затрат процессор 0 процессор 1 процессор 2 процессор 3

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

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

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

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

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

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

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

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

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

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

Москва, 2012 г. Постановка задачи диффузной балансировки Дано: Количество точек – N Количество процессоров – p Процессор i обработал n i точек за время t i Требуется: Найти количества точек n i, которое следует обработать процессорам на следующем шаге Определить сколько точек каждый из процессоров должен передать соседним процессорам 34 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.

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

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

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

r=0; for(i=0;i

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

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

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

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

Общая схема вычислений дополнительные затраты Москва, 2012 г. K = ; шаг_вывода = ; for(шаг=0;шаг

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

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