Лекция 2 Методы построения параллельных программ Учебный курс Введение в параллельные алгоритмы

Август 25, 2022

Главная
Информатика
Лекция 2 Методы построения параллельных программ Учебный курс Введение в параллельные алгоритмы

Содержание

2. … если для нас представляют интерес реально работающие системы, то требуется убедиться, (и убедить всех сомневающихся)
3. Методы построения параллельных алгоритмов и их свойства: Статическая балансировка метод сдваивания геометрический параллелизм конвейерный параллелизм Динамическая
4. Обладает запасом внутреннего параллелизма Есть возможность одновременного выполнения операций Допускает возможность равномерного распределения вычислительных операций между
5. Операции, отсутствующие в наилучшем последовательном алгоритме: Синхронизация Обмен данными Дублирование операций Новые операции Накладные расходы Москва,
6. Потери времени на передачу данных между процессами Процессор 1 Процессор 2 Обмен данными Москва, 2009 г.
7. Потери времени на ожидание долго выполняющихся процессов Процессор 1 Процессор 2 Процессор 3 Синхронизация Москва, 2009
8. S=0; For(i=0;i S+=a[i]; Send(S) Дублирование операций Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных
9. Вычисление всех факториалов до 8! включительно Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных
10. Вычисление всех факториалов до 8! включительно Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных
11. Метод сдванивания Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
12. Стена Фокса Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
13. Метод геометрического параллелизма Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
14. Метод коллективного решения (укладка паркета) Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ
15. Метод коллективного решения (укладка паркета) Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ
16. Send(ai); Send(ai+1); Recv(s); Вычисление определенного интеграла Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных
17. Метод конвейерного параллелизма Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
18. Статическая и динамическая балансировка загрузки процессоров Статическая балансировка метод сдваивания геометрический параллелизм конвейерный параллелизм Динамическая балансировка
19. r=0; for(i=0;i { d=a[i]+b[i]+r; c[i]=d%10; r=d/10; } c[i]=r; Определение суммы двух многоразрядных чисел Москва, 2009 г.
20. Последовательное распространение разряда переноса на четырёх процессорах «Параллельный» алгоритм Москва, 2009 г. Введение в параллельные алгоритмы:
21. Спекулятивное вычисление двух сумм Спекулятивный алгоритм Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных
22. r1=0; r2=1; for(i=0;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; Спекулятивный
23. Спекулятивное вычисление двух сумм Спекулятивный алгоритм Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных
24. Рассмотрены методы построения параллельных алгоритмов Рассмотрена проблема балансировки загрузки процессоров Представлен масштабируемый параллельный метод сложения многоразрядных
25. В чем заключается проблема балансировки загрузки? В чем заключаются методы геометрического параллелизма, конвейерного параллелизма и коллективного
27. Скачать презентацию

Слайд 2

… если для нас представляют интерес реально работающие системы, то

требуется убедиться, (и убедить всех сомневающихся) в корректности наших построений
… системе часто придется работать в невоспроизводимых обстоятельствах, и мы едва ли можем ожидать сколько-нибудь серьезной помощи от тестов
Dijkstra E.W.
1966

Предварительные замечания

Москва, 2009 г.

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

из 26

Слайд 3

Методы построения параллельных алгоритмов и их свойства:
Статическая балансировка
метод сдваивания
геометрический параллелизм
конвейерный параллелизм
Динамическая

балансировка
коллективное решение
Пример задачи, для параллельного решения которой необходимо создание качественно нового алгоритма

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

Москва, 2009 г.

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

из 26

Слайд 4

Обладает запасом внутреннего параллелизма
Есть возможность одновременного выполнения операций
Допускает возможность равномерного распределения

вычислительных операций между процессорами
Обладает низким уровнем накладных расходов

Хороший параллельный алгоритм

Москва, 2009 г.

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

большим

большим числом

из 26

Слайд 5

Операции, отсутствующие в наилучшем последовательном алгоритме:
Синхронизация
Обмен данными
Дублирование операций
Новые операции
Накладные расходы
Москва, 2009

г.

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

из 26

Слайд 6

Потери времени на передачу данных между процессами
Процессор 1 Процессор 2
Обмен

данными

Москва, 2009 г.

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

из 26

Слайд 7

Потери времени на ожидание долго выполняющихся процессов
Процессор 1 Процессор 2 Процессор

Синхронизация

Москва, 2009 г.

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

из 26

Слайд 8

S=0;
For(i=0;i S+=a[i];
Send(S)
Дублирование операций
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных

программ © Якобовский М.В.
S=0;
For(i=n1;i S+=a[i];
Send(S)

Recv(S1)
Recv(S2)
S=S1+S2

из 26

Слайд 9

Вычисление всех факториалов до 8! включительно
Москва, 2009 г.
Введение в параллельные алгоритмы:

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

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

из 26

Слайд 10

Вычисление всех факториалов до 8! включительно
Москва, 2009 г.
Введение в параллельные алгоритмы:

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

из 26

Слайд 11

Метод сдванивания
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ

Каскадная схема
Модифицированная каскадная схема В.П.Гергель Основы параллельных вычислений, лекция 4, слайд 23

из 26

Слайд 12

Стена Фокса
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ

n – ширина стены
к – высота стены

из 26

Слайд 13

Метод геометрического параллелизма
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных

программ © Якобовский М.В.

из 26

Слайд 14

Метод коллективного решения (укладка паркета)
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы

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

из 26

Слайд 15

Метод коллективного решения (укладка паркета)
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы

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

Число порций

Обработка порции

Обмен данными

r – размер порции

из 26

Слайд 16

Send(ai); Send(ai+1); Recv(s);
Вычисление определенного интеграла
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы

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

из 26

Слайд 17

Метод конвейерного параллелизма
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных

программ © Якобовский М.В.

из 26

Слайд 18

Статическая и динамическая балансировка загрузки процессоров
Статическая балансировка
метод сдваивания
геометрический параллелизм
конвейерный параллелизм
Динамическая балансировка
коллективное

решение

Москва, 2009 г.

из 26

Слайд 19

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 г.
Введение в параллельные алгоритмы: Методы

T1= 4nτс

из 26

Слайд 20

Последовательное распространение разряда переноса на четырёх процессорах
«Параллельный» алгоритм
Москва, 2009 г.
Введение в

из 26

Слайд 21

Спекулятивное вычисление двух сумм
Спекулятивный алгоритм
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы

из 26

Слайд 22

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τс

из 26

Слайд 23

Спекулятивное вычисление двух сумм
Спекулятивный алгоритм
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы

из 26

Слайд 24

Рассмотрены методы построения параллельных алгоритмов
Рассмотрена проблема балансировки загрузки процессоров
Представлен масштабируемый параллельный

метод сложения многоразрядных чисел, основанный на неэффективном последовательном алгоритме

Заключение

Москва, 2009 г.

из 26

Слайд 25

В чем заключается проблема балансировки загрузки?
В чем заключаются методы геометрического параллелизма,

конвейерного параллелизма и коллективного решения?
Чем определяются максимальные ускорения, достигаемые при применении этих методов?
В чем отличие методов статической и динамической балансировки загрузки?

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

Москва, 2009 г.

из 26

Лекция 2 Методы построения параллельных программ Учебный курс Введение в параллельные алгоритмы

Содержание

… если для нас представляют интерес реально работающие системы, то

Обладает запасом внутреннего параллелизмаЕсть возможность одновременного выполнения операцийДопускает возможность равномерного распределения

Операции, отсутствующие в наилучшем последовательном алгоритме:СинхронизацияОбмен даннымиДублирование операцийНовые операцииНакладные расходыМосква, 2009

Потери времени на передачу данных между процессами Процессор 1 Процессор 2Обмен

Потери времени на ожидание долго выполняющихся процессовПроцессор 1 Процессор 2 Процессор

S=0;For(i=0;i S+=a[i];Send(S)Дублирование операцийМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения параллельных

Вычисление всех факториалов до 8! включительноМосква, 2009 г.Введение в параллельные алгоритмы:

Вычисление всех факториалов до 8! включительноМосква, 2009 г.Введение в параллельные алгоритмы:

Метод сдваниванияМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения параллельных программ

Стена ФоксаМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения параллельных программ

Метод геометрического параллелизмаМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения параллельных

Метод коллективного решения (укладка паркета)Москва, 2009 г.Введение в параллельные алгоритмы: Методы

Метод коллективного решения (укладка паркета)Москва, 2009 г.Введение в параллельные алгоритмы: Методы

Send(ai); Send(ai+1); Recv(s);Вычисление определенного интегралаМосква, 2009 г.Введение в параллельные алгоритмы: Методы

Метод конвейерного параллелизмаМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения параллельных

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 г.Введение в параллельные алгоритмы: Методы

Последовательное распространение разряда переноса на четырёх процессорах«Параллельный» алгоритмМосква, 2009 г.Введение в

Спекулятивное вычисление двух суммСпекулятивный алгоритмМосква, 2009 г.Введение в параллельные алгоритмы: Методы

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 г.Введение в параллельные алгоритмы:

Спекулятивное вычисление двух суммСпекулятивный алгоритмМосква, 2009 г.Введение в параллельные алгоритмы: Методы

Рассмотрены методы построения параллельных алгоритмовРассмотрена проблема балансировки загрузки процессоровПредставлен масштабируемый параллельный

В чем заключается проблема балансировки загрузки?В чем заключаются методы геометрического параллелизма,

Похожие презентации

Обладает запасом внутреннего параллелизма
Есть возможность одновременного выполнения операций
Допускает возможность равномерного распределения

Операции, отсутствующие в наилучшем последовательном алгоритме:
Синхронизация
Обмен данными
Дублирование операций
Новые операции
Накладные расходы
Москва, 2009

Потери времени на передачу данных между процессами
Процессор 1 Процессор 2
Обмен

Потери времени на ожидание долго выполняющихся процессов
Процессор 1 Процессор 2 Процессор

S=0;
For(i=0;i S+=a[i];
Send(S)
Дублирование операций
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных

Вычисление всех факториалов до 8! включительно
Москва, 2009 г.
Введение в параллельные алгоритмы:

Вычисление всех факториалов до 8! включительно
Москва, 2009 г.
Введение в параллельные алгоритмы:

Метод сдванивания
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ

Стена Фокса
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ

Метод геометрического параллелизма
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных

Метод коллективного решения (укладка паркета)
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы

Метод коллективного решения (укладка паркета)
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы

Send(ai); Send(ai+1); Recv(s);
Вычисление определенного интеграла
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы

Метод конвейерного параллелизма
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы построения параллельных

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 г.
Введение в параллельные алгоритмы: Методы

Последовательное распространение разряда переноса на четырёх процессорах
«Параллельный» алгоритм
Москва, 2009 г.
Введение в

Спекулятивное вычисление двух сумм
Спекулятивный алгоритм
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы

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 г.
Введение в параллельные алгоритмы:

Спекулятивное вычисление двух сумм
Спекулятивный алгоритм
Москва, 2009 г.
Введение в параллельные алгоритмы: Методы

Рассмотрены методы построения параллельных алгоритмов
Рассмотрена проблема балансировки загрузки процессоров
Представлен масштабируемый параллельный

В чем заключается проблема балансировки загрузки?
В чем заключаются методы геометрического параллелизма,