Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Методы построения параллельных программ

Содержание

… если для нас представляют интерес реально работающие системы, то требуется убедиться, (и убедить всех сомневающихся) в корректности наших построений … системе часто придется работать в невоспроизводимых обстоятельствах, и мы едва ли можем
Лекция 2 Методы построения параллельных программУчебный курсВведение в параллельные алгоритмыЯкобовский М.В., д.ф.-м.н.Институт математического моделирования РАН, Москва … если для нас представляют интерес реально работающие системы, то Методы построения параллельных алгоритмов и их свойства:Статическая балансировкаметод сдваиваниягеометрический параллелизмконвейерный параллелизмДинамическая балансировкаколлективное Обладает запасом внутреннего параллелизмаЕсть возможность одновременного выполнения операцийДопускает возможность равномерного распределения вычислительных Операции, отсутствующие в наилучшем последовательном алгоритме:СинхронизацияОбмен даннымиДублирование операцийНовые операцииНакладные расходыМосква, 2009 г.Введение Потери времени на передачу данных между процессами Потери времени на ожидание долго выполняющихся процессов S=0;For(i=0;i Вычисление всех факториалов до 8! включительноМосква, 2009 г.Введение в параллельные алгоритмы: Методы Вычисление всех факториалов до 8! включительноМосква, 2009 г.Введение в параллельные алгоритмы: Методы Метод сдваниванияМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения параллельных программ © Стена ФоксаМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения параллельных программ © Метод геометрического параллелизмаМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения параллельных программ Метод коллективного решения (укладка паркета)Москва, 2009 г.Введение в параллельные алгоритмы: Методы построения Метод коллективного решения (укладка паркета)Москва, 2009 г.Введение в параллельные алгоритмы: Методы построения Send(ai); Send(ai+1); Recv(s);Вычисление определенного интегралаМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения Метод конвейерного параллелизмаМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения параллельных программ Статическая и динамическая балансировка загрузки процессоровСтатическая балансировкаметод сдваиваниягеометрический параллелизмконвейерный параллелизмДинамическая балансировкаколлективное решениеМосква, r=0;for(i=0;i Последовательное распространение разряда переноса на четырёх процессорах«Параллельный» алгоритмМосква, 2009 г.Введение в параллельные Спекулятивное вычисление двух суммСпекулятивный алгоритмМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения r1=0; r2=1;for(i=0;i Спекулятивное вычисление двух суммСпекулятивный алгоритмМосква, 2009 г.Введение в параллельные алгоритмы: Методы построения Рассмотрены методы построения параллельных алгоритмовРассмотрена проблема балансировки загрузки процессоровПредставлен масштабируемый параллельный метод В чем заключается проблема балансировки загрузки?В чем заключаются методы геометрического параллелизма, конвейерного Якобовский М.В. д.ф.-м.н., зав. сектором «Программного обеспечения многопроцессорных систем и вычислительных сетей»
Слайды презентации

Слайд 2 … если для нас представляют интерес

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

реально работающие системы, то требуется убедиться, (и убедить всех

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

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

Москва, 2009 г.

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

из 26

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

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

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

которой необходимо создание качественно нового алгоритма

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

Москва, 2009 г.

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

из 26

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

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

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

накладных расходов

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

Москва, 2009 г.

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

большим

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

из 26

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

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

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

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

из 26

Слайд 6 Потери времени на передачу данных между процессами

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

Процессор 1 Процессор

2

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

Москва, 2009 г.

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









из 26

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

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


Процессор 1

Процессор 2 Процессор 3

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

Москва, 2009 г.

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










из 26

Слайд 8



S=0;
For(i=0;i

S=0;For(i=0;i

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

S=0;
For(i=n1;i

S+=a[i];
Send(S)

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



из 26

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

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

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

М.В.




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

из 26

Слайд 10

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

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

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

М.В.




1

2

4

3

8

5

9

11

6

7

12

10

из 26

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

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

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




Модифицированная каскадная схема

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

из 26

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

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

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

– высота стены

из 26

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

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

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

Слайд 14

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

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

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

из 26

Слайд 15
Метод коллективного решения (укладка паркета)
Москва, 2009 г.
Введение в

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

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

Число

порций



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

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

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

из 26

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

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

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










из 26

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

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

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

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

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

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



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

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

из 26

Слайд 19 r=0;
for(i=0;i

r=0;for(i=0;i

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

4nτс

из 26

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

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

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

© Якобовский М.В.

из 26

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

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

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

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

из 26

Слайд 22 r1=0;
r2=1;
for(i=0;i

r1=0; r2=1;for(i=0;i

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

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

T’= 8n1τс

из 26

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

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

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

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

из 26

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

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

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

неэффективном последовательном алгоритме

Заключение

Москва, 2009 г.

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

из 26

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

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

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

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

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

Москва, 2009 г.

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

из 26

  • Имя файла: metody-postroeniya-parallelnyh-programm.pptx
  • Количество просмотров: 162
  • Количество скачиваний: 0
- Предыдущая Кто такие варяги
Следующая - Международные конференции по туризму

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

Внешний доступ к службам RMS Внешний доступ к службам RMS 117
Свойства объектов Свойства объектов 98
ОБЪЕКТЫ ОКРУЖАЮЩЕГО МИРА ОБЪЕКТЫ ОКРУЖАЮЩЕГО МИРА 162
Возможности настольных издательских систем Возможности настольных издательских систем 125
Архитектура вычислительной системы Архитектура вычислительной системы 130
Введение в базы данных Введение в базы данных 134
Урок 15. Таблицы Урок 15. Таблицы 136
Функциональная схема компьютера Функциональная схема компьютера 105
Интеллектуальные информационные системы 3 Интеллектуальные информационные системы 3 129
Технология создания и редактирования изображений в векторном редакторе Технология создания и редактирования изображений в векторном редакторе 120
Презентация проект Мир ребусов Презентация проект Мир ребусов 184
Презентация по информатике Базы данных 11 класс Презентация по информатике Базы данных 11 класс 175
Информационно-коммуникационные технологии в образовании Информационно-коммуникационные технологии в образовании 150
Архитектура ORACLE. Области оперативной памяти (Лекция 5) Архитектура ORACLE. Области оперативной памяти (Лекция 5) 119
Системно-деятельностный подход на уроках информатики Системно-деятельностный подход на уроках информатики 129
Зарядка для ума Зарядка для ума 199
Системы объектов Системы объектов 127
Презентация по информатике 10 класс Содержательный подход к измерению информации Презентация по информатике 10 класс Содержательный подход к измерению информации 193
Компьютерные вирусы и антивирусные программы Компьютерные вирусы и антивирусные программы 107
Занимательная_информатика Занимательная_информатика 212
Технические средства компьютерной графики Технические средства компьютерной графики 144
Хранение и передача информации Хранение и передача информации 120
Презентация Базы данных: среда и принципы работы (9 класс) Презентация Базы данных: среда и принципы работы (9 класс) 184
Презентацияы на тему Решение экономических задач в электронных таблицах Презентацияы на тему Решение экономических задач в электронных таблицах 140
Презентация по информатике на тему Хакеры: гении или злодеи? Презентация по информатике на тему Хакеры: гении или злодеи? 173
Что умеет компьютер? Что умеет компьютер? 116
Перспективы развития и применения информационно-правовых систем Перспективы развития и применения информационно-правовых систем 196
MSC.Dytran - 12 MSC.Dytran - 12 218
Презентация к уроку информатики по теме Создание движущихся изображений Презентация к уроку информатики по теме Создание движущихся изображений 139
MS WORD МӘТІНДІК ПРОЦЕССОРЫ тақырыбына ашық сабақ MS WORD МӘТІНДІК ПРОЦЕССОРЫ тақырыбына ашық сабақ 222