'

Учебный курс Введение в параллельные алгоритмы

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

Многопроцессорные системы с распределенной памятью с общей памятью Гибридные Модель выполнения программ Методы взаимодействия процессов Методы передачи данных Семафоры Ускорение и эффективность параллельных алгоритмов Пример алгоритма низкой эффективности Содержание лекции Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 2 из 47


Слайд 2

Транспьютерная материнская плата МТБ-8 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 3 из 47


Слайд 3

Транспьютер T-800 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 4 из 47


Слайд 4

Транспьютерная материнская плата МТБ-8 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 5 из 47


Слайд 5

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


Слайд 6

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


Слайд 7

Узел с общей памятью – два процессора Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 8 из 47


Слайд 8

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


Слайд 9

Узел PowerXplorer Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 10 из 47


Слайд 10

Гибридная система Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 11 из 47


Слайд 11

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


Слайд 12

Плата и 4 модуля Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 13 из 47


Слайд 13

Многопроцессорные системы с распределенной памятью Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 14 из 47


Слайд 14

Многопроцессорные системы с общей памятью Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 15 из 47


Слайд 15

При запуске указываем число требуемых процессоров Np и название программы На выделенных для расчета узлах запускается Np копий указанной программы Например, на двух узлах запущены три копии программы. Копия программы с номером 1 не имеет непосредственного доступа к оперативной памяти копий 0 и 2: Каждая копия программы получает две переменные Np rank из диапазона [0 … Np-1] Любые две копии программы могут непосредственно обмениваться данными с помощью функций передачи сообщений Модель программы на распределенной памяти Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 16 из 47


Слайд 16

Работа начинается с запуска одной программы При необходимости программа порождает новые процессы, эти процессы: Обладают собственными локальными переменными Имеют доступ к глобальным переменным int a_global; main нить1 нить2 main() { int b1_local; запуск нити1 Запуск нити(fun()) } запуск нити2 fun() { int b2_local; Запуск нити(…) } Модель программы на общей памяти Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 17 из 47


Слайд 17

Синхронный метод Send(адрес данных, размер, номер процессора) Recv(адрес данных, размер, номер процессора) Асинхронные методы Небуферизованный ASend(адрес данных, размер, номер процессора) ARecv(адрес данных, размер, номер процессора) ASync Буферизованный ABSend(адрес данных, размер, номер процессора) Методы передачи данных Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 18 из 47


Слайд 18

A=3 Send(&A) A=5 Синхронные Москва, 2011 г. B=4 Recv(&B) Print(B) Send Recv Print(B) A=5 B=4 A=3 Результат 3 Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 19 из 47


Слайд 19

A=3 АSend(&A) A=5 Асинхронные Москва, 2011 г. B=4 АRecv(&B) Print(B) Send ASend Recv ARecv Print(B) A=5 B=4 Результат 3 ? 4 ? 5 A=3 Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 20 из 47


Слайд 20

A=3 АSend(&A) Async() A=5 Асинхронные Москва, 2011 г. B=4 АRecv(&B) Print(B) ASync Send ASend Recv ARecv Print(B) A=5 B=4 Результат 3 ? 4 A=3 Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 21 из 47


Слайд 21

A=3 АSend(&A) Async() A=5 Асинхронные Москва, 2011 г. B=4 АRecv(&B) Async() Print(B) Результат 3 ASync Send ASend ASync Recv ARecv Print(B) A=5 A=3 B=4 Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 22 из 47


Слайд 22

A=3 АBSend(&A) A=5 Асинхронные буферизованные Москва, 2011 г. B=4 АRecv(&B) Async() Print(B) Результат 3 Send(&buf) ABSend ASync Recv ARecv Print(B) A=5 buf=A A=3 B=4 Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 23 из 47


Слайд 23

Свойства канала передачи данных Москва, 2011 г. Gbit Ethernet Число передаваемых байт Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 24 из 47 T(n)=n*Tпередачи байта+ Tлатентности


Слайд 24

Свойства канала передачи данных Москва, 2011 г. T(n)=n*Tпередачи байта+ Tлатентности Число передаваемых байт Infiniband Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 25 из 47


Слайд 25

Целочисленная неотрицательная переменная Две атомарные операции, не считая инициализации V(S) Увеличивает значение S на 1 P(S) Если S положительно, то уменьшает S на 1 Иначе ждет, пока S не станет больше 0 Семафор Языки програмирования. Редактор Ф.Женюи. Перевод с англ В.П.Кузнецова. Под ред. В.М.Курочкина. М:."Мир", 1972 Э. Дейкстра. Взаимодействие последовательных процессов. http://khpi-iip.mipk.kharkiv.edu/library/extent/dijkstra/ewd123/index.html Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 26 из 47


Слайд 26

ускорение параллельного алгоритма S(p)=T1/T(p) Ускорение и эффективность параллельных алгоритмов Москва, 2011 г. Ускорение параллельного алгоритма относительно наилучшего последовательного S*(p)=T1 * /T(p) E *(p)=S *(p)/p эффективность использования процессорной мощности E(p)=S(p)/p Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 27 из 47


Слайд 27

Да: Плохой последовательный алгоритм Влияние аппаратных особенностей вычислительной системы Может ли быть S(p)>p ? Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 28 из 47


Слайд 28

Да Если первый алгоритм позволяет использовать больше процессоров, чем второй. Самый эффективный алгоритм – использующий один (1) процессор. Его эффективность по определению равна 100%, но он не всегда самый быстрый. Может ли неэффективный алгоритм работать быстрее эффективного? Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 29 из 47


Слайд 29

Все элементарные операции (+ - * / ) выполняются за время ?с Все операции выполняются точно, результат не зависит от порядка их выполнения Число процессоров неограничено Определить сумму конечного ряда 30 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 30 из 47


Слайд 30

S=1; a=1; for(i=1;i<= n;i++) { a=a*x/i; S=S+a; } Последовательный алгоритм T1= 3n?с 31 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 31 из 47


Слайд 31

Параллельный алгоритм Вычислить для всех i =1,…,n : xi Вычислить для всех i =1,…,n : i! Вычислить для всех i =1,…,n : ai = Вычислить сумму всех членов ai 32 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 32 из 47


Слайд 32

Для вычисления xi воспользуемся методом бинарного умножения x 1 x2 2 x3 x4 3 x5 x6 x7 x8 4 x9 x10 x11 x12 x13 x14 x15 x16 xi 33 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 33 из 47


Слайд 33

Параллельное вычисление всех требуемых i! ? 34 ? Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 34 из 47


Слайд 34

4 1?2? 3?4? 5?6? 7?8?9?10? 11?12 ?13?14? 15?16=16! 3 1?2? 3?4? 5?6? 7?8 9?10? 11?12 ?13?14? 15?16 2 1?2? 3?4 5?6? 7?8 9?10? 11?12 13?14? 15?16 1 1?2 3?4 5?6 7?8 9?10 11?12 13?14 15?16 i! 35 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 35 из 47


Слайд 35

Для вычисления i! воспользуемся аналогичным методом 4 1?2? 3?4? 5?6? 7?8?9?10? 11?12 =12! 3 1?2? 3?4? 5?6? 7?8 9?10? 11?12 ?13?14? 15?16 2 1?2? 3?4 5?6? 7?8 9?10? 11?12 13?14? 15?16 1 1?2 3?4 5?6 7?8 9?10 11?12 13?14 15?16 12! 36 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 36 из 47


Слайд 36

Для вычисления i! воспользуемся аналогичным методом 4 1?2? 3?4? 5?6? 7?8?9?10? 11?12 ?13?14=14! 3 1?2? 3?4? 5?6? 7?8 9?10? 11?12? 13?14 2 1?2? 3?4 5?6? 7?8 9?10? 11?12 1 1?2 3?4 5?6 7?8 9?10 11?12 13?14 15?16 14! 37 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 37 из 47


Слайд 37

Новые операции Москва, 2009 г. Параллельные методы и алгоритмы: Методы построения параллельных программ © Якобовский М.В. Вычисление всех факториалов до 8! включительно 38 из 60 38


Слайд 38

Новые операции Москва, 2009 г. Параллельные методы и алгоритмы: Методы построения параллельных программ © Якобовский М.В. Вычисление всех факториалов до 8! включительно 39 из 60 39


Слайд 39

Новые операции Москва, 2009 г. Параллельные методы и алгоритмы: Методы построения параллельных программ © Якобовский М.В. Вычисление всех факториалов до 8! включительно 40 из 60 40


Слайд 40

Новые операции Москва, 2009 г. Параллельные методы и алгоритмы: Методы построения параллельных программ © Якобовский М.В. Вычисление всех факториалов до 8! включительно 41 из 60 41


Слайд 41

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


Слайд 42

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


Слайд 43

p=n Ускорение и эффективность при p=n 2 1.5 1.5 44 Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 44 из 47


Слайд 44

Определены классы рассматриваемых вычислительных систем Представлены модели параллельных программ Представлен ряд способов организации взаимодействия последовательных процессов Представлен алгоритм, обладающий низкой эффективностью, но высоким быстродействием Заключение Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 45 из 47


Слайд 45

Сколько нужно процессоров для вычисления суммы ряда за время 2 + q , где q – константа Какие преимущества и недостатки присущи синхронным и асинхронным методам обмена данными? Приведите примеры алгоритмов обладающих эффективностью больше 100%. Есть ли процессорные инструкции P(S) и V(S)? Вопросы для обсуждения Москва, 2011 г. Введение в параллельные алгоритмы: Основные понятия © Якобовский М.В. 46 из 47


Слайд 46

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


×

HTML:





Ссылка: