Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 12 лет назад пользователемwww.intuit.ru
1 Интернет Университет Суперкомпьютерных технологий Лекция 3 Методы построения параллельных программ (продолжение) Учебный курс Введение в параллельные алгоритмы Якобовский Михаил Владимирович проф., д.ф.-м.н. Институт прикладной математики им. М.В.Келдыша РАН, Москва 1
2 … если для нас представляют интерес реально работающие системы, то требуется убедиться, (и убедить всех сомневающихся) в корректности наших построений … системе часто придется работать в невоспроизводимых обстоятельствах, и мы едва ли можем ожидать сколько-нибудь серьезной помощи от тестов Dijkstra E.W Предварительные замечания Москва, 2010 г. 2 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
3 Методы построения параллельных алгоритмов и их свойства: –Статическая балансировка метод сдваивания геометрический параллелизм конвейерный параллелизм –Динамическая балансировка коллективное решение диффузная балансировка загрузки Содержание лекции Москва, 2010 г. 3 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
4 Метод сдваивания Москва, 2010 г. Каскадная схема Модифицированная каскадная схема В.П.Гергель Основы параллельных вычислений, лекция 4, слайд 23 В.П.Гергель Основы параллельных вычислений, лекция 4, слайд 23 4 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
5 Стена Фокса Москва, 2010 г. n – ширина стены к – высота стены 5 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
6 Метод геометрического параллелизма Москва, 2010 г. 6 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
7 master Метод коллективного решения (укладка паркета) Москва, 2010 г. 7 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
8 Метод коллективного решения (укладка паркета) Москва, 2010 г. Число порций Обработка порции Обмен данными r – размер порции 8 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
9 Метод конвейерного параллелизма Москва, 2010 г. 9 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
10 Москва, 2010 г. ? Метод конвейерного параллелизма Время выполнения на p процессорах 10 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
11 Метод конвейерного параллелизма Москва, 2010 г. 11 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
12 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 12 Метод конвейерного параллелизма for(t=0;t
13 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 13 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
14 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 14 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
15 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 15 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
16 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 16 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
17 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 17 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
18 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 18 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
19 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 19 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
20 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 20 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
21 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 21 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
22 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 22 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
23 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 23 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
24 Метод конвейерного параллелизма Москва, 2010 г. 24 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
25 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 25 Метод конвейерного параллелизма процессор 0 процессор 1 процессор 2 процессор 3
26 Москва, 2010 г. Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. 26 Объём хранимых данных процессор 0 процессор 1 процессор 2 процессор 3
27 Причины дисбаланса вычислительной нагрузки –Разные процессоры –Внешнее воздействие –Разная вычислительная сложность заданий Результат дисбаланса –Эффективная производительность определяется самым медленным процессором Диффузная балансировка Москва, 2010 г. 27 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
28 Медленный процессор Москва, 2010 г. Какой объем работ забрать у среднего процессора и кому его передать? 28 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
29 Метод геометрического параллелизма Москва, 2010 г. 29 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
30 Метод геометрического параллелизма Москва, 2010 г. 30 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
31 Диффузная балансировка загрузки Москва, 2010 г. 31 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
32 Диффузная балансировка загрузки Москва, 2010 г. 32 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
33 Диффузная балансировка загрузки Москва, 2010 г. 33 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
34 Статическое распределение Москва, 2010 г. 34 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
35 Москва, 2010 г. Постановка задачи диффузной балансировки Дано: Количество точек – N Количество процессоров – p Процессор i обработал n i точек за время t i Требуется: Найти количества точек n i, которое следует обработать процессорам на следующем шаге Определить сколько точек каждый из процессоров должен передать соседним процессорам 35 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
36 Москва, 2010 г. 36 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. Диффузная балансировка
37 Статическая и динамическая балансировка загрузки процессоров –Статическая балансировка метод сдваивания геометрический параллелизм конвейерный параллелизм –Динамическая балансировка коллективное решение диффузная балансировка Москва, 2010 г. 37 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В. Резюме
38 Общая схема вычислений Москва, 2010 г. K = ; шаг_вывода = ; for(шаг=0;шаг
39 r=0; for(i=0;i
40 Последовательное распространение разряда переноса на четырёх процессорах «Параллельный» алгоритм Москва, 2010 г. 40 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
41 Москва, 2010 г. ? Параллельный алгоритм« » 41 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
42 Спекулятивное вычисление двух сумм Спекулятивный алгоритм Москва, 2010 г Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
43 r1=0; r2=1; for(i=0;i
44 Спекулятивное вычисление двух сумм Спекулятивный алгоритм Москва, 2010 г Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
45 Рассмотрены некоторые методы построения параллельных алгоритмов Рассмотрен алгоритм диффузной балансировки загрузки процессоров Представлен масштабируемый параллельный алгоритм, основанный на неэффективном последовательном алгоритме Заключение Москва, 2010 г. 45 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
46 Якобовский М.В. проф., д.ф.-м.н., зав. сектором «Программного обеспечения многопроцессорных систем и вычислительных сетей» Института прикладной математики им. М.В.Келдыша Российской академии наук mail: web: Контакты Москва, 2010 г. 46 Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.