close

Вход

Забыли?

вход по аккаунту

?

Введение в параллельные алгоритмы

код для вставкиСкачать
Интернет Университет
Суперкомпьютерных технологий
Учебный курс
Введение в параллельные алгоритмы
Лекция 2
Методы построения параллельных программ
Якобовский М.В., д.ф.-м.н.
Институт математического
моделирования РАН, Москва
Предварительные замечания
… если для нас представляют интерес реально
работающие системы, то требуется
убедиться, (и убедить всех сомневающихся) в
корректности наших построений
… системе часто придется работать в
невоспроизводимых обстоятельствах, и мы едва
ли можем ожидать сколько-нибудь серьезной
помощи от тестов
Dijkstra E.W.
1966
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
2 из 26
Содержание лекции
Методы построения параллельных алгоритмов и
их свойства:
– Статическая балансировка
• метод сдваивания
• геометрический параллелизм
• конвейерный параллелизм
– Динамическая балансировка
• коллективное решение
Пример задачи, для параллельного решения
которой необходимо создание качественно
нового алгоритма
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
3 из 26
Хороший параллельный алгоритм
большим
Обладает запасом внутреннего параллелизма
– Есть возможность одновременного выполнения
операций
Допускает возможность равномерного
распределения вычислительных операций между
процессорами
большим числом
Обладает низким уровнем накладных расходов
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
4 из 26
Накладные расходы
Операции, отсутствующие в наилучшем
последовательном алгоритме:
–
–
–
–
Синхронизация
Обмен данными
Дублирование операций
Новые операции
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
5 из 26
Обмен данными
Потери времени на передачу данных между процессами
Процессор 1
Москва, 2009 г.
Процессор 2
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
6 из 26
Синхронизация
Потери времени на ожидание долго выполняющихся процессов
Процессор 1
Москва, 2009 г.
Процессор 2
Процессор 3
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
7 из 26
Дублирование операций
S=0;
For(i=0;i<n1;i++)
S+=a[i];
Send(S)
S=0;
For(i=n1;i<n;i++)
S+=a[i];
Send(S)
Recv(S1)
Recv(S2)
S=S1+S2
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
8 из 26
Вычисление всех факториалов до 8! включительно
Шаг
1
2
3
Процессор 1
Процессор 2
1 2
123
12345
3 4
1234
123456
F=1;
for(i=2;i <= n;i++)
F*=i;
T1 ( n ) c ( n 1)
Москва, 2009 г.
Процессор 3
5 6
7 8
567
5678
1234567 12345678
T p n / 2 ( n ) c log
S Процессор 4
n 1
log
2
n
7
n
4 p
3
n 8
p4
E p 4 (n 8) 2
7
12
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
9 из 26
Вычисление всех факториалов до 8! включительно
Шаг
1
2
3
Процессор 1
Процессор 2
1 2
123
12345
3 4
1234
123456
T p n / 2 ( n ) c log
Шаг
1
2
3
Москва, 2009 г.
2
n
S log
Процессор 1
1
2
4
n 1
2!
3!
5!
2
n
n 8
p4
Процессор 2
8
3
5
3 4
4!
6!
Процессор 3
Процессор 4
5 6
7 8
567
5678
1234567 12345678
7
4 p
3
E p 4 ( n 8) Процессор 3
9
11
6
5 6
567
7!
7
12
Процессор 4
10
12
7
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
7 8
5678
8!
10 из 26
Метод сдванивания
Каскадная схема
T p n / 2 ( n ) c log
S pn / 2 (n) 2
n
a1
n 1
log
2
E pn / 2 (n) n
a2
a3
a1+a2
1
a4
a3+a4
a5
a5+a6
a1+a2+a3+a4
log
2
n
a6
a7
a8
a7+a8
a5+a6+a7+a8
a1+a2+a3+a4+a5+a6+a7+a8
Модифицированная каскадная схема
В.П.Гергель Основы параллельных вычислений, лекция 4, слайд 23
T
p
n
( n ) 2 c log
2
n
2
log 2 n
S
p
n
1
(n) log 2 n
Москва, 2009 г.
n 1
2 log
2
n
E
p
n
log 2 n
(n) 1
2
X1 X2 X3 X4
X5 X6 X7 X8
X9 X1 0 X1 1 X1
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
2
X1 3 X1 4 X1 5 X1
6
11 из 26
Стена Фокса
n – ширина стены
к – высота стены
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
12 из 26
Метод геометрического параллелизма
T1 ( kn ) c kn
S p ( kn ) p
1
1 4
Москва, 2009 г.
p s
n c
T p ( kn ) c
E p ( kn ) kn
p
4 k s
1
1 4
p s
n c
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
13 из 26
Метод коллективного решения (укладка паркета)
c
Tp N
p
c s s
master
p max Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
c
s
14 из 26
Метод коллективного решения (укладка паркета)
Число порций
T1 ( kn ) c kn
T p ( kn ) S
E
p
p
r c
s
r c
kn
rp
Обработка порции
r c
s
Обмен данными
r c
( kn ) s
Москва, 2009 г.
1
1
p max
1
1 r c
1
p max
s
1
( kn ) s
2
1
s
r c
p max r c
s
r – размер порции
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
15 из 26
Вычисление определенного интеграла
Send(ai); Send(ai+1); Recv(s);
a i 1
B
I f x dx f x dx
i
A
ai
T p s max i
i
1
Москва, 2009 г.
2
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
16 из 26
Метод конвейерного параллелизма
T1 ( kn ) c kn
S p ( kn ) p
1
1
Москва, 2009 г.
s
c
T p ( kn ) c
kn
E p ( kn ) k
p
n
p
s
1
1
s
c
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
17 из 26
Статическая и динамическая балансировка
загрузки процессоров
– Статическая балансировка
• метод сдваивания
• геометрический параллелизм
• конвейерный параллелизм
– Динамическая балансировка
• коллективное решение
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
18 из 26
Определение суммы двух многоразрядных чисел
r=0;
for(i=0;i<=n;i++)
{
d=a[i]+b[i]+r;
c[i]=d%10;
r=d/10;
}
c[i]=r;
Москва, 2009 г.
6934317835
3221643577
1015596141 2
T1= 4nс
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
19 из 26
«Параллельный» алгоритм
Последовательное распространение разряда
переноса на четырёх процессорах
99
99
99999999
99
1
100
1
100
100000000
100
100
100
Москва, 2009 г.
99
00
00
00
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
20 из 26
Спекулятивный алгоритм
Спекулятивное вычисление двух сумм
99
99
99
100
99
100
99
100
100
00
00
99999999
1
100000000
Москва, 2009 г.
99
99
1
100
+0
+1
00
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
21 из 26
Спекулятивный алгоритм
r1=0;
r2=1;
for(i=0;i<=n1;i++)
{
d1=a[i]+b[i]+r1;
c1[i]=d1%10;
r1=d1/10;
d2=a[i]+b[i]+r2;
c2[i]=d2%10;
r2=d2/10;
}
Recv(&r)
if(r)c=c1;
else c=c2;
Москва, 2009 г.
T’= 8n1с
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
22 из 26
Спекулятивный алгоритм
Спекулятивное вычисление двух сумм
T1 4 n c
Tp 8
Sp n
p
c
p
99
99
99
100
99
100
99
100
100
00
00
99
1
100
+0
+1
2
E p 50 %
Москва, 2009 г.
99
00
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
23 из 26
Заключение
Рассмотрены методы построения параллельных
алгоритмов
Рассмотрена проблема балансировки загрузки
процессоров
Представлен масштабируемый параллельный
метод сложения многоразрядных чисел,
основанный на неэффективном
последовательном алгоритме
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
24 из 26
Вопросы для обсуждения
В чем заключается проблема балансировки
загрузки?
В чем заключаются методы геометрического
параллелизма, конвейерного параллелизма и
коллективного решения?
Чем определяются максимальные ускорения,
достигаемые при применении этих методов?
В чем отличие методов статической и
динамической балансировки загрузки?
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
25 из 26
Контакты
Якобовский М.В.
д.ф.-м.н.,
зав. сектором
«Программного обеспечения многопроцессорных
систем и вычислительных сетей»
Института математического моделирования
Российской академии наук
mail: lira@imamod.ru
web: http://lira.imamod.ru
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
26 из 26
Документ
Категория
Презентации по информатике
Просмотров
47
Размер файла
2 540 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа