Презентация на тему "Методы построения параллельных программ"

Содержание

• 
  Слайд 1

  Лекция 2Методы построения параллельных программ

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

• 
  Слайд 2

  Предварительные замечания

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

• 
  Слайд 3

  Содержание лекции

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

• 
  Слайд 4

  Хороший параллельный алгоритм

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

• 
  Слайд 5

  Накладные расходы

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

• 
  Слайд 6

  Обмен данными

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

• 
  Слайд 7

  Синхронизация

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

• 
  Слайд 8

  Дублирование операций

  S=0; For(i=0;i

• 
  Слайд 9

  Вычисление всех факториаловдо 8! включительно

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

• 
  Слайд 10
  

  Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 1 2 4 3 8 5 9 11 6 7 12 10 10 из 26

• 
  Слайд 11

  Метод сдванивания

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

• 
  Слайд 12

  Стена Фокса

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

• 
  Слайд 13

  Метод геометрического параллелизма

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

• 
  Слайд 14

  Метод коллективного решения (укладка паркета)

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

• 
  Слайд 15
  

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

• 
  Слайд 16

  Вычисление определенного интеграла

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

• 
  Слайд 17

  Метод конвейерного параллелизма

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

• 
  Слайд 18
  

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

• 
  Слайд 19

  Определение суммы двух многоразрядных чисел

  r=0; for(i=0;i

• 
  Слайд 20

  «Параллельный» алгоритм

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

• 
  Слайд 21

  Спекулятивный алгоритм

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

• 
  Слайд 22
  

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

• 
  Слайд 23
  

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

• 
  Слайд 24

  Заключение

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

• 
  Слайд 25

  Вопросы для обсуждения

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

• 
  Слайд 26

  Контакты

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