Без темы
<<  Урок № 5. Прямая пропорциональность Учебный курс Основы параллельных вычислений  >>
Учебный курс Введение в параллельные алгоритмы
Учебный курс Введение в параллельные алгоритмы
Содержание лекции
Содержание лекции
Транспьютерная материнская плата МТБ-8
Транспьютерная материнская плата МТБ-8
Транспьютер T-800
Транспьютер T-800
5 из 47
5 из 47
Транспьютерная материнская плата МТБ-8
Транспьютерная материнская плата МТБ-8
Транспьютер Т800 и коммутатор С004
Транспьютер Т800 и коммутатор С004
Электронный коммутатор
Электронный коммутатор
9 из 47
9 из 47
Узел с общей памятью – два процессора
Узел с общей памятью – два процессора
11 из 47
11 из 47
Узел PowerXplorer
Узел PowerXplorer
Гибридная система
Гибридная система
14 из 47
14 из 47
Плата и 4 модуля
Плата и 4 модуля
Многопроцессорные системы с распределенной памятью
Многопроцессорные системы с распределенной памятью
Многопроцессорные системы с общей памятью
Многопроцессорные системы с общей памятью
Модель программы на распределенной памяти
Модель программы на распределенной памяти
Модель программы на общей памяти
Модель программы на общей памяти
Методы передачи данных
Методы передачи данных
Синхронные
Синхронные
Асинхронные
Асинхронные
Асинхронные
Асинхронные
Асинхронные
Асинхронные
Асинхронные буферизованные
Асинхронные буферизованные
Свойства канала передачи данных
Свойства канала передачи данных
Свойства канала передачи данных
Свойства канала передачи данных
Семафор
Семафор
Ускорение и эффективность параллельных алгоритмов
Ускорение и эффективность параллельных алгоритмов
Может ли быть S(p)>p
Может ли быть S(p)>p
Может ли неэффективный алгоритм работать быстрее эффективного
Может ли неэффективный алгоритм работать быстрее эффективного
Все элементарные операции (+ - * / ) выполняются за время
Все элементарные операции (+ - * / ) выполняются за время
T1= 3n
T1= 3n
Вычислить для всех i =1,…,n : xi Вычислить для всех i =1,…,n : i
Вычислить для всех i =1,…,n : xi Вычислить для всех i =1,…,n : i
Для вычисления xi воспользуемся методом бинарного умножения x 1 x2 2
Для вычисления xi воспользуемся методом бинарного умножения x 1 x2 2
?
?
?
?
?
?
4 1?2? 3
4 1?2? 3
Для вычисления i
Для вычисления i
Для вычисления i
Для вычисления i
Новые операции
Новые операции
Новые операции
Новые операции
p=n
p=n
Заключение
Заключение
Вопросы для обсуждения
Вопросы для обсуждения
Контакты
Контакты

Презентация: «Учебный курс Введение в параллельные алгоритмы». Автор: Якобовский М.В.. Файл: «Учебный курс Введение в параллельные алгоритмы.ppt». Размер zip-архива: 5491 КБ.

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

содержание презентации «Учебный курс Введение в параллельные алгоритмы.ppt»
СлайдТекст
1 Учебный курс Введение в параллельные алгоритмы

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

Лекция 1 Основные понятия

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

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

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

Многопроцессорные системы с распределенной памятью с общей памятью Гибридные Модель выполнения программ Методы взаимодействия процессов Методы передачи данных Семафоры Ускорение и эффективность параллельных алгоритмов Пример алгоритма низкой эффективности

2 из 47

Москва, 2010 г.

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

3 Транспьютерная материнская плата МТБ-8

Транспьютерная материнская плата МТБ-8

3 из 47

Москва, 2010 г.

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

4 Транспьютер T-800

Транспьютер T-800

4 из 47

Москва, 2010 г.

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

5 5 из 47

5 из 47

Москва, 2010 г.

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

6 Транспьютерная материнская плата МТБ-8

Транспьютерная материнская плата МТБ-8

6 из 47

Москва, 2010 г.

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

7 Транспьютер Т800 и коммутатор С004

Транспьютер Т800 и коммутатор С004

7 из 47

Москва, 2010 г.

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

8 Электронный коммутатор

Электронный коммутатор

8 из 47

Москва, 2010 г.

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

9 9 из 47

9 из 47

Москва, 2010 г.

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

10 Узел с общей памятью – два процессора

Узел с общей памятью – два процессора

10 из 47

Москва, 2010 г.

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

11 11 из 47

11 из 47

Москва, 2010 г.

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

12 Узел PowerXplorer

Узел PowerXplorer

12 из 47

Москва, 2010 г.

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

13 Гибридная система

Гибридная система

13 из 47

Москва, 2010 г.

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

14 14 из 47

14 из 47

Москва, 2010 г.

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

15 Плата и 4 модуля

Плата и 4 модуля

15 из 47

Москва, 2010 г.

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

16 Многопроцессорные системы с распределенной памятью

Многопроцессорные системы с распределенной памятью

16 из 47

Москва, 2010 г.

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

17 Многопроцессорные системы с общей памятью

Многопроцессорные системы с общей памятью

17 из 47

Москва, 2010 г.

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

18 Модель программы на распределенной памяти

Модель программы на распределенной памяти

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

18 из 47

Москва, 2010 г.

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

19 Модель программы на общей памяти

Модель программы на общей памяти

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

19 из 47

Москва, 2010 г.

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

20 Методы передачи данных

Методы передачи данных

Синхронный метод Send(адрес данных, размер, номер процессора) Recv(адрес данных, размер, номер процессора) Асинхронные методы Небуферизованный ASend(адрес данных, размер, номер процессора) ARecv(адрес данных, размер, номер процессора) ASync Буферизованный ABSend(адрес данных, размер, номер процессора)

20 из 47

Москва, 2010 г.

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

21 Синхронные

Синхронные

A=3 Send(&A) A=5

B=4 Recv(&B) Print(B)

Результат 3

A=3

B=4

Send

Recv

Print(B)

A=5

21 из 47

Москва, 2010 г.

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

22 Асинхронные

Асинхронные

A=3 аsend(&a) A=5

B=4 аrecv(&b) print(b)

Результат 3 ? 4 ? 5

A=3

B=4

ARecv

Send

ASend

A=5

Print(B)

Recv

22 из 47

Москва, 2010 г.

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

23 Асинхронные

Асинхронные

A=3 аsend(&a) async() A=5

B=4 аrecv(&b) print(b)

Результат 3 ? 4

B=4

A=3

ARecv

Send

ASend

Print(B)

Recv

A=5

ASync

23 из 47

Москва, 2010 г.

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

24 Асинхронные

Асинхронные

A=3 аsend(&a) async() A=5

B=4 АRecv(&B) Async() Print(B) Результат 3

A=3

B=4

ARecv

ASend

Send

ASync

Recv

Print(B)

A=5

ASync

24 из 47

Москва, 2010 г.

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

25 Асинхронные буферизованные

Асинхронные буферизованные

A=3 аbsend(&a) A=5

B=4 АRecv(&B) Async() Print(B) Результат 3

A=3

buf=A

ABSend

B=4

ARecv

Send(&buf)

A=5

ASync

Recv

Print(B)

25 из 47

Москва, 2010 г.

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

26 Свойства канала передачи данных

Свойства канала передачи данных

T(n)=n*tбайта+ tлатентности

Gbit Ethernet

Число передаваемых байт

26 из 47

Москва, 2010 г.

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

27 Свойства канала передачи данных

Свойства канала передачи данных

T(n)=n*tбайта+ tлатентности

Infiniband

Число передаваемых байт

27 из 47

Москва, 2010 г.

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

28 Семафор

Семафор

Целочисленная неотрицательная переменная Две атомарные операции, не считая инициализации V(S) Увеличивает значение S на 1 P(S) Если S положительно, уменьшает S на 1 Иначе ждет, пока S не станет больше 0

Языки програмирования. Редактор Ф.Женюи. Перевод с англ В.П.Кузнецова. Под ред. В.М.Курочкина. М:."Мир", 1972 Э. Дейкстра. Взаимодействие последовательных процессов. http://khpi-iip.mipk.kharkiv.edu/library/extent/dijkstra/ewd123/index.html

28 из 47

Москва, 2010 г.

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

29 Ускорение и эффективность параллельных алгоритмов

Ускорение и эффективность параллельных алгоритмов

Ускорение параллельного алгоритма s(p)=t1/t(p)

Эффективность использования процессорной мощности e(p)=s(p)/p

Ускорение параллельного алгоритма относительно наилучшего последовательного S*(p)=T1 * /T(p) E *(p)=S *(p)/p

29 из 47

Москва, 2010 г.

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

30 Может ли быть S(p)>p

Может ли быть S(p)>p

Да: Плохой последовательный алгоритм Влияние аппаратных особенностей вычислительной системы

30 из 47

Москва, 2010 г.

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

31 Может ли неэффективный алгоритм работать быстрее эффективного

Может ли неэффективный алгоритм работать быстрее эффективного

Да Если первый алгоритм позволяет использовать больше процессоров, чем второй. Самый эффективный алгоритм – использующий один (1) процессор. Его эффективность по определению равна 100%, но он не всегда самый быстрый.

31 из 47

Москва, 2010 г.

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

32 Все элементарные операции (+ - * / ) выполняются за время

Все элементарные операции (+ - * / ) выполняются за время

с Все операции выполняются точно, результат не зависит от порядка их выполнения Число процессоров неограничено

Определить сумму конечного ряда

32

32 из 47

Москва, 2010 г.

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

33 T1= 3n

T1= 3n

Последовательный алгоритм

S=1; a=1; for(i=1;i<= n;i++) { a=a*x/i; S=S+a; }

33

33 из 47

Москва, 2010 г.

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

34 Вычислить для всех i =1,…,n : xi Вычислить для всех i =1,…,n : i

Вычислить для всех i =1,…,n : xi Вычислить для всех i =1,…,n : i

Вычислить для всех i =1,…,n : ai = Вычислить сумму всех членов ai

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

34

34 из 47

Москва, 2010 г.

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

35 Для вычисления xi воспользуемся методом бинарного умножения x 1 x2 2

Для вычисления xi воспользуемся методом бинарного умножения x 1 x2 2

x3 x4 3 x5 x6 x7 x8 4 x9 x10 x11 x12 x13 x14 x15 x16

xi

35

35 из 47

Москва, 2010 г.

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

36 ?

?

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

36

36 из 47

Москва, 2010 г.

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

37 ?

?

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

37

37 из 47

Москва, 2010 г.

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

38 ?

?

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

38

38 из 47

Москва, 2010 г.

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

39 4 1?2? 3

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!

39

39 из 47

Москва, 2010 г.

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

40 Для вычисления i

Для вычисления 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!

40

40 из 47

Москва, 2010 г.

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

41 Для вычисления i

Для вычисления 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!

41

41 из 47

Москва, 2010 г.

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

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

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

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

Шаг

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

F=1; for(i=2;i <= n;i++) F*=i;

42 из 60

42

Москва, 2009 г.

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

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

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

Шаг

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

5?6

7?8

2

3!

4!

56?7

56?78

3

5!

6!

7!

8!

Процессор 1

Процессор 2

Процессор 3

Процессор 4

Процессор 1

Процессор 2

Процессор 3

Процессор 4

1

8

9

10

2

3

11

12

4

5

6

7

43 из 60

43

Москва, 2009 г.

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

44 p=n

p=n

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

1.5

2

1.5

44

44 из 47

Москва, 2010 г.

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

45 Заключение

Заключение

Определены классы рассматриваемых вычислительных систем Представлены модели параллельных программ Представлен ряд способов организации взаимодействия последовательных процессов Представлен алгоритм, обладающий низкой эффективностью, но высоким быстродействием

45 из 47

Москва, 2010 г.

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

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

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

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

46 из 47

Москва, 2010 г.

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

47 Контакты

Контакты

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

47 из 47

Москва, 2010 г.

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

«Учебный курс Введение в параллельные алгоритмы»
http://900igr.net/prezentacija/geometrija/uchebnyj-kurs-vvedenie-v-parallelnye-algoritmy-190183.html
cсылка на страницу

Без темы

105 презентаций
Урок

Геометрия

40 тем
Слайды
900igr.net > Презентации по геометрии > Без темы > Учебный курс Введение в параллельные алгоритмы