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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47

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
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47

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
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47

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
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47

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

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

Целочисленная неотрицательная переменная
Две атомарные операции, не считая инициализации
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 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47

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

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

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

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

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

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

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

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

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

Для вычисления 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!
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47

Для вычисления 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!
Москва, 2011 г.
Введение в параллельные алгоритмы:
Основные понятия © Якобовский М.В.
из 47

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

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

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

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

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

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

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

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

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