математики им. М.В.Келдыша РАН, Москва..
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Учебный курс Введение в параллельные алгоритмы презентация
Содержание
- 1. Учебный курс Введение в параллельные алгоритмы
- 2. Многопроцессорные системы с распределенной памятью
- 3. Транспьютерная материнская плата МТБ-8 Москва, 2011 г.
- 4. Транспьютер T-800 Москва, 2011 г.
- 5. Транспьютерная материнская плата МТБ-8 Москва, 2011 г.
- 6. Электронный коммутатор Москва, 2011 г. Введение в
- 7. Москва, 2011 г. Введение в параллельные
- 8. Узел с общей памятью – два процессора
- 9. Москва, 2011 г. Введение в параллельные
- 10. Узел PowerXplorer Москва, 2011 г. Введение
- 11. Гибридная система Москва, 2011 г.
- 12. Москва, 2011 г. Введение в параллельные
- 13. Плата и 4 модуля Москва, 2011 г.
- 14. Многопроцессорные системы
- 15. Многопроцессорные системы с общей памятью Москва,
- 16. При запуске указываем число требуемых процессоров Np
- 17. Работа начинается с запуска одной программы При
- 18. Синхронный метод Send(адрес данных, размер, номер процессора)
- 19. A=3 Send(&A) A=5 Синхронные Москва, 2011
- 20. A=3 АSend(&A) A=5 Асинхронные Москва, 2011
- 21. A=3 АSend(&A) Async() A=5 Асинхронные Москва,
- 22. A=3 АSend(&A) Async() A=5 Асинхронные Москва,
- 23. A=3 АBSend(&A) A=5 Асинхронные буферизованные Москва,
- 24. Свойства канала передачи данных Москва, 2011 г.
- 25. Свойства канала передачи данных Москва, 2011 г.
- 26. Целочисленная неотрицательная переменная Две атомарные операции,
- 27. ускорение параллельного алгоритма S(p)=T1/T(p) Ускорение
- 28. Да: Плохой последовательный алгоритм Влияние аппаратных особенностей
- 29. Да Если первый алгоритм позволяет использовать больше
- 30. Все элементарные операции
- 31. S=1; a=1; for(i=1;i
- 32. Параллельный алгоритм Вычислить для всех i
- 33. Для вычисления xi воспользуемся методом бинарного умножения
- 34. Параллельное вычисление всех требуемых i! ?
- 35. 4 1⋅2⋅ 3⋅4⋅ 5⋅6⋅ 7⋅8⋅9⋅10⋅ 11⋅12
- 36. Для вычисления i! воспользуемся аналогичным методом 4 1⋅2⋅
- 37. Для вычисления i! воспользуемся аналогичным методом 4 1⋅2⋅
- 38. Новые операции Москва, 2009 г. Параллельные методы
- 39. Новые операции Москва, 2009 г. Параллельные методы
- 40. Новые операции Москва, 2009 г. Параллельные методы
- 41. Новые операции Москва, 2009 г. Параллельные методы
- 42. Новые операции Москва, 2009 г. Параллельные
- 43. Новые операции Москва, 2009 г.
- 44. p=n Ускорение и эффективность при p=n
- 45. Определены классы рассматриваемых вычислительных систем Представлены модели
- 46. Сколько нужно процессоров для вычисления суммы ряда
- 47. Якобовский М.В. д.ф.-м.н., проф., зав. сектором
Слайд 1Лекция 1
Основные понятия
Учебный курс
Введение в параллельные алгоритмы
Якобовский М.В., проф., д.ф.-м.н.
Институт прикладной
Слайд 2Многопроцессорные системы
с распределенной памятью
с общей памятью
Гибридные
Модель выполнения программ
Методы взаимодействия
процессов
Методы передачи данных
Семафоры
Ускорение и эффективность параллельных алгоритмов
Пример алгоритма низкой эффективности
Методы передачи данных
Семафоры
Ускорение и эффективность параллельных алгоритмов
Пример алгоритма низкой эффективности
Содержание лекции
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 3Транспьютерная материнская плата МТБ-8
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия
© Якобовский М.В.
из 47
Слайд 4
Транспьютер T-800
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский
М.В.
из 47
Слайд 5Транспьютерная материнская плата МТБ-8
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия
© Якобовский М.В.
из 47
Слайд 6Электронный коммутатор
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский
М.В.
из 47
Слайд 8Узел с общей памятью – два процессора
Москва, 2011 г.
Введение в параллельные
алгоритмы:
Основные понятия © Якобовский М.В.
Основные понятия © Якобовский М.В.
из 47
Слайд 10Узел PowerXplorer
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский
М.В.
из 47
Слайд 11Гибридная система
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский
М.В.
из 47
Слайд 13Плата и 4 модуля
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия
© Якобовский М.В.
из 47
Слайд 14
Многопроцессорные системы с распределенной памятью
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные
понятия © Якобовский М.В.
из 47
Слайд 15
Многопроцессорные системы с общей памятью
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные
понятия © Якобовский М.В.
из 47
Слайд 16При запуске указываем число требуемых процессоров Np и название программы
На выделенных
для расчета узлах запускается Np копий указанной программы
Например, на двух узлах запущены три копии программы. Копия программы с номером 1 не имеет непосредственного доступа к оперативной памяти копий 0 и 2:
Каждая копия программы получает две переменные
Np
rank из диапазона [0 … Np-1]
Любые две копии программы могут непосредственно обмениваться данными с помощью функций передачи сообщений
Например, на двух узлах запущены три копии программы. Копия программы с номером 1 не имеет непосредственного доступа к оперативной памяти копий 0 и 2:
Каждая копия программы получает две переменные
Np
rank из диапазона [0 … Np-1]
Любые две копии программы могут непосредственно обмениваться данными с помощью функций передачи сообщений
Модель программы на распределенной памяти
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 17Работа начинается с запуска одной программы
При необходимости программа порождает новые процессы,
эти процессы:
Обладают собственными локальными переменными
Имеют доступ к глобальным переменным
int a_global; main нить1 нить2
main()
{
int b1_local; запуск нити1
Запуск нити(fun())
} запуск нити2
fun()
{
int b2_local;
Запуск нити(…)
}
Обладают собственными локальными переменными
Имеют доступ к глобальным переменным
int a_global; main нить1 нить2
main()
{
int b1_local; запуск нити1
Запуск нити(fun())
} запуск нити2
fun()
{
int b2_local;
Запуск нити(…)
}
Модель программы на общей памяти
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 18Синхронный метод
Send(адрес данных, размер, номер процессора)
Recv(адрес данных, размер, номер процессора)
Асинхронные
методы
Небуферизованный
ASend(адрес данных, размер, номер процессора)
ARecv(адрес данных, размер, номер процессора)
ASync
Буферизованный
ABSend(адрес данных, размер, номер процессора)
Небуферизованный
ASend(адрес данных, размер, номер процессора)
ARecv(адрес данных, размер, номер процессора)
ASync
Буферизованный
ABSend(адрес данных, размер, номер процессора)
Методы передачи данных
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 19A=3
Send(&A)
A=5
Синхронные
Москва, 2011 г.
B=4
Recv(&B)
Print(B)
Send
Recv
Print(B)
A=5
B=4
A=3
Результат
3
Введение в параллельные алгоритмы:
Основные понятия ©
Якобовский М.В.
из 47
Слайд 20A=3
АSend(&A)
A=5
Асинхронные
Москва, 2011 г.
B=4
АRecv(&B)
Print(B)
Send
ASend
Recv
ARecv
Print(B)
A=5
B=4
A=3
Введение в параллельные алгоритмы:
Основные понятия © Якобовский
М.В.
из 47
Слайд 21A=3
АSend(&A)
Async()
A=5
Асинхронные
Москва, 2011 г.
B=4
АRecv(&B)
Print(B)
ASync
Send
ASend
Recv
ARecv
Print(B)
A=5
B=4
A=3
Введение в параллельные алгоритмы:
Основные понятия © Якобовский
М.В.
из 47
Слайд 22A=3
АSend(&A)
Async()
A=5
Асинхронные
Москва, 2011 г.
B=4
АRecv(&B)
Async()
Print(B)
Результат
3
3
ASync
Send
ASend
ASync
Recv
ARecv
Print(B)
A=5
A=3
B=4
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 23A=3
АBSend(&A)
A=5
Асинхронные буферизованные
Москва, 2011 г.
B=4
АRecv(&B)
Async()
Print(B)
Результат
3
3
Send(&buf)
ABSend
ASync
Recv
ARecv
Print(B)
A=5
buf=A
A=3
B=4
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 24Свойства канала передачи данных
Москва, 2011 г.
Gbit Ethernet
Число передаваемых байт
Введение в параллельные
алгоритмы:
Основные понятия © Якобовский М.В.
Основные понятия © Якобовский М.В.
из 47
T(n)=n*Tпередачи байта+ Tлатентности
Слайд 25Свойства канала передачи данных
Москва, 2011 г.
T(n)=n*Tпередачи байта+ Tлатентности
Число передаваемых байт
Infiniband
Введение в
параллельные алгоритмы:
Основные понятия © Якобовский М.В.
Основные понятия © Якобовский М.В.
из 47
Слайд 26Целочисленная неотрицательная переменная
Две атомарные операции, не считая инициализации
V(S)
Увеличивает значение S
на 1
P(S)
Если S положительно, то уменьшает S на 1
Иначе ждет, пока S не станет больше 0
P(S)
Если S положительно, то уменьшает S на 1
Иначе ждет, пока S не станет больше 0
Семафор
Языки програмирования. Редактор Ф.Женюи. Перевод с англ В.П.Кузнецова. Под ред. В.М.Курочкина. М:."Мир", 1972 Э. Дейкстра. Взаимодействие последовательных процессов.
http://khpi-iip.mipk.kharkiv.edu/library/extent/dijkstra/ewd123/index.html
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 27ускорение
параллельного
алгоритма
S(p)=T1/T(p)
Ускорение и эффективность параллельных алгоритмов
Москва, 2011 г.
Ускорение параллельного алгоритма относительно наилучшего
последовательного
S*(p)=T1 * /T(p)
E *(p)=S *(p)/p
S*(p)=T1 * /T(p)
E *(p)=S *(p)/p
эффективность
использования
процессорной мощности
E(p)=S(p)/p
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 28Да:
Плохой последовательный алгоритм
Влияние аппаратных особенностей вычислительной системы
Может ли быть S(p)>p ?
Москва,
2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 29Да
Если первый алгоритм позволяет использовать больше процессоров, чем второй.
Самый эффективный алгоритм
– использующий один (1) процессор.
Его эффективность по определению равна 100%, но он не всегда самый быстрый.
Его эффективность по определению равна 100%, но он не всегда самый быстрый.
Может ли неэффективный алгоритм работать быстрее эффективного?
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 30
Все элементарные операции (+ - * / ) выполняются за время
τс
Все операции выполняются точно, результат не зависит от порядка их выполнения
Число процессоров неограничено
Все операции выполняются точно, результат не зависит от порядка их выполнения
Число процессоров неограничено
Определить сумму конечного ряда
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 32Параллельный алгоритм
Вычислить для всех i =1,…,n : xi
Вычислить для всех
i =1,…,n : i!
Вычислить для всех i =1,…,n : ai =
Вычислить сумму всех членов ai
Вычислить для всех i =1,…,n : ai =
Вычислить сумму всех членов ai
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 33Для вычисления xi воспользуемся методом бинарного умножения
x
1 x2
2 x3 x4
3 x5 x6
x7 x8
4 x9 x10 x11 x12 x13 x14 x15 x16
4 x9 x10 x11 x12 x13 x14 x15 x16
xi
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 34Параллельное вычисление всех требуемых i! ?
?
Москва, 2011 г.
Введение в параллельные
алгоритмы:
Основные понятия © Якобовский М.В.
Основные понятия © Якобовский М.В.
из 47
Слайд 35
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
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!
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 36Для вычисления 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
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!
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 37Для вычисления 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
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!
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 38Новые операции
Москва, 2009 г.
Параллельные методы и алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
Вычисление всех факториалов до 8! включительно
из 60
Слайд 39Новые операции
Москва, 2009 г.
Параллельные методы и алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
Вычисление всех факториалов до 8! включительно
из 60
Слайд 40Новые операции
Москва, 2009 г.
Параллельные методы и алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
Вычисление всех факториалов до 8! включительно
из 60
Слайд 41Новые операции
Москва, 2009 г.
Параллельные методы и алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
Вычисление всех факториалов до 8! включительно
из 60
Слайд 42
Новые операции
Москва, 2009 г.
Параллельные методы и алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
F=1;
for(i=2;i <= n;i++)
F*=i;
Вычисление всех факториалов до 8! включительно
из 60
Слайд 43
Новые операции
Москва, 2009 г.
Параллельные методы и алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
1
2
4
3
8
5
9
11
6
7
12
10
из 60
Слайд 44 p=n
Ускорение и эффективность при p=n
2
1.5
1.5
Москва, 2011 г.
Введение в параллельные
алгоритмы:
Основные понятия © Якобовский М.В.
Основные понятия © Якобовский М.В.
из 47
Слайд 45Определены классы рассматриваемых вычислительных систем
Представлены модели параллельных программ
Представлен ряд способов организации
взаимодействия последовательных процессов
Представлен алгоритм, обладающий низкой эффективностью, но высоким быстродействием
Представлен алгоритм, обладающий низкой эффективностью, но высоким быстродействием
Заключение
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 46Сколько нужно процессоров для вычисления суммы ряда
за время
2 + q ,
где q – константа
Какие преимущества и недостатки присущи синхронным и асинхронным методам обмена данными?
Приведите примеры алгоритмов обладающих эффективностью больше 100%.
Есть ли процессорные инструкции P(S) и V(S)?
2 + q ,
где q – константа
Какие преимущества и недостатки присущи синхронным и асинхронным методам обмена данными?
Приведите примеры алгоритмов обладающих эффективностью больше 100%.
Есть ли процессорные инструкции P(S) и V(S)?
Вопросы для обсуждения
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
Слайд 47Якобовский М.В.
д.ф.-м.н., проф.,
зав. сектором
«Программного обеспечения многопроцессорных систем и вычислительных
сетей»
Института прикладной математики им. М.В.Келдыша Российской академии наук
mail: mail: lira@imamod.rumail: lira@imamod.ru
web: web: http://lira.imamod.ru
Института прикладной математики им. М.В.Келдыша Российской академии наук
mail: mail: lira@imamod.rumail: lira@imamod.ru
web: web: http://lira.imamod.ru
Контакты
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47
