Виды алгоритмов Скачать
презентацию
<<  Циклический алгоритм Блок-схема  >>
Учебный курс Введение в параллельные алгоритмы
Учебный курс Введение в параллельные алгоритмы
Предварительные замечания
Предварительные замечания
Содержание лекции
Содержание лекции
Хороший параллельный алгоритм
Хороший параллельный алгоритм
Накладные расходы
Накладные расходы
Обмен данными
Обмен данными
Синхронизация
Синхронизация
Дублирование операций
Дублирование операций
Вычисление всех факториалов до 8
Вычисление всех факториалов до 8
Вычисление всех факториалов до 8
Вычисление всех факториалов до 8
Метод сдванивания
Метод сдванивания
Стена Фокса
Стена Фокса
Метод геометрического параллелизма
Метод геометрического параллелизма
Метод коллективного решения (укладка паркета)
Метод коллективного решения (укладка паркета)
Метод коллективного решения (укладка паркета)
Метод коллективного решения (укладка паркета)
Вычисление определенного интеграла
Вычисление определенного интеграла
Метод конвейерного параллелизма
Метод конвейерного параллелизма
Статическая и динамическая балансировка загрузки процессоров
Статическая и динамическая балансировка загрузки процессоров
T1= 4n
T1= 4n
«Параллельный» алгоритм
«Параллельный» алгоритм
Спекулятивный алгоритм
Спекулятивный алгоритм
T’= 8n1
T’= 8n1
Спекулятивный алгоритм
Спекулятивный алгоритм
Заключение
Заключение
Вопросы для обсуждения
Вопросы для обсуждения
Контакты
Контакты
Слайды из презентации «Параллельные алгоритмы» к уроку информатики на тему «Виды алгоритмов»

Автор: Якобовский М.В.. Чтобы увеличить слайд, нажмите на его эскиз. Чтобы использовать презентацию на уроке, скачайте файл «Параллельные алгоритмы.ppt» бесплатно в zip-архиве размером 391 КБ.

Скачать презентацию

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

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

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

Лекция 2 Методы построения параллельных программ

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

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

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

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

2 из 26

Москва, 2009 г.

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

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

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

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

3 из 26

Москва, 2009 г.

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

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

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

Большим

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

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

4 из 26

Москва, 2009 г.

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

5 Накладные расходы

Накладные расходы

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

5 из 26

Москва, 2009 г.

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

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

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

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

6 из 26

Москва, 2009 г.

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

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

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

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

7 из 26

Москва, 2009 г.

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

8 Дублирование операций

Дублирование операций

S=0; For(i=n1;i<n;i++) S+=a[i]; Send(S)

S=0; For(i=0;i<n1;i++) S+=a[i]; Send(S)

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

8 из 26

Москва, 2009 г.

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

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

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

включительно.

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

9 из 26

Москва, 2009 г.

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

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

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

включительно.

1

8

9

10

2

3

11

12

4

5

6

7

10 из 26

Москва, 2009 г.

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

11 Метод сдванивания

Метод сдванивания

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

11 из 26

Москва, 2009 г.

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

12 Стена Фокса

Стена Фокса

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

12 из 26

Москва, 2009 г.

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

13 Метод геометрического параллелизма

Метод геометрического параллелизма

13 из 26

Москва, 2009 г.

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

14 Метод коллективного решения (укладка паркета)

Метод коллективного решения (укладка паркета)

14 из 26

Москва, 2009 г.

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

15 Метод коллективного решения (укладка паркета)

Метод коллективного решения (укладка паркета)

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

Число порций

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

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

15 из 26

Москва, 2009 г.

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

16 Вычисление определенного интеграла

Вычисление определенного интеграла

Send(ai); Send(ai+1); Recv(s);

16 из 26

Москва, 2009 г.

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

17 Метод конвейерного параллелизма

Метод конвейерного параллелизма

17 из 26

Москва, 2009 г.

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

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

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

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

18 из 26

Москва, 2009 г.

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

19 T1= 4n

T1= 4n

с.

r=0; for(i=0;i<=n;i++) { d=a[i]+b[i]+r; c[i]=d%10; r=d/10; } c[i]=r;

Определение суммы двух многоразрядных чисел

19 из 26

Москва, 2009 г.

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

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

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

Последовательное распространение разряда переноса на четырёх процессорах

20 из 26

Москва, 2009 г.

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

21 Спекулятивный алгоритм

Спекулятивный алгоритм

Спекулятивное вычисление двух сумм

21 из 26

Москва, 2009 г.

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

22 T’= 8n1

T’= 8n1

с.

Спекулятивный алгоритм

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;

22 из 26

Москва, 2009 г.

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

23 Спекулятивный алгоритм

Спекулятивный алгоритм

Спекулятивное вычисление двух сумм

23 из 26

Москва, 2009 г.

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

24 Заключение

Заключение

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

24 из 26

Москва, 2009 г.

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

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

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

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

25 из 26

Москва, 2009 г.

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

26 Контакты

Контакты

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

26 из 26

Москва, 2009 г.

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

«Параллельные алгоритмы»
http://900igr.net/prezentatsii/informatika/Parallelnye-algoritmy/Parallelnye-algoritmy.html
cсылка на страницу
Урок

Информатика

126 тем
Слайды
Презентация: Параллельные алгоритмы.ppt | Тема: Виды алгоритмов | Урок: Информатика | Вид: Слайды