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

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

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

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

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

6 S=0; For(i=0;i

7 Новые операции

8 r=0; for(i=0;i

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

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

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

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

13 Спекулятивное вычисление двух сумм Избыточный алгоритм П 3П 2П 1П Шаг Шаг Шаг 3

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

15 Спекулятивное вычисление двух сумм Избыточный алгоритм П 3П 2П 1П Шаг Шаг Шаг 3

16 Все элементарные операции (+ - * / ) выполняются за время с Все операции выполняются точно, результат не зависит от порядка их выполнения Число процессоров неограничено Определить сумму конечного ряда 16

17 S=1; a=1; for(i=1;i

18 Параллельный алгоритм Вычислить для всех i =1,…,n : x i Вычислить для всех i =1,…,n : i! Вычислить для всех i =1,…,n : a i = Вычислить сумму всех членов a i 18

19 Для вычисления x i воспользуемся методом бинарного умножения x 1x 2 2x 3 x 4 3x 5 x 6 x 7 x 8 4 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 xixi 19

20 Параллельное вычисление i! ? 20 ?

21 Параллельное вычисление i! ? 21 ?

22 Параллельное вычисление i! ? 22 ?

=16! i! 23

24 Для вычисления i! воспользуемся аналогичным методом =12! ! 24

25 Для вычисления i! воспользуемся аналогичным методом =14! ! 25

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

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

28 p=n Ускорение и эффективность при p=n

29 Литература… Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ- Петербург, Грегори Р. Эндрюс - Основы многопоточного, параллельного и распределенного программирования. "Вильямс ", 2003 Роберт Седжвик - Фундаментальные алгоритмы на C. Части Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах Языки программирования. Редактор Ф.Женюи. Перевод с англ. В.П.Кузнецова. Под ред. В.М.Курочкина. М:."Мир", 1972 Э. Дейкстра. Взаимодействие последовательных процессов. Дональд Э. Кнут Искусство программирования 29

30 Литература… Учебные курсы Интернет Университета Информационных технологий Гергель В.П. Теория и практика параллельных вычислений. Лекции в форме видео-конференций Гергель В.П. Основы параллельных вычислений. Немнюгин С.А. Основы параллельного программирования с использованием MPI. Крюков В.А., Бахтин В.А. Параллельное программирование с OpenMP. Дополнительные учебные курсы: Воеводин В.В. Вычислительная математика и структура алгоритмов

31 Литература Ресурсы Internet

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