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

Виды алгоритмов Скачать презентацию
<< Циклический алгоритм		Блок-схема >>

Учебный курс Введение в параллельные алгоритмы	Предварительные замечания	Содержание лекции	Хороший параллельный алгоритм	Накладные расходы
Обмен данными				Синхронизация
Дублирование операций	Вычисление всех факториалов до 8	Вычисление всех факториалов до 8	Метод сдванивания	Стена Фокса
Метод геометрического параллелизма	Метод коллективного решения (укладка паркета)	Метод коллективного решения (укладка паркета)	Вычисление определенного интеграла	Метод конвейерного параллелизма
Статическая и динамическая балансировка загрузки процессоров	T1= 4n	«Параллельный» алгоритм	Спекулятивный алгоритм	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 включительно. F=1; for(i=2;i <= n;i++) F*=i; 9 из 26 Москва, 2009 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
10		Вычисление всех факториалов до 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 с. 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 с. Спекулятивный алгоритм 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 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
«Параллельные алгоритмы»