Якобовский Михаил Владимирович
проф., д.ф.-м.н.
Институт прикладной математики им. М.В.Келдыша РАН, Москва
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Интернет Университет Суперкомпьютерных технологий презентация
Содержание
- 1. Интернет Университет Суперкомпьютерных технологий
- 2. … если для нас представляют
- 3. Методы построения параллельных алгоритмов и их свойства:
- 4. Метод сдваивания Москва, 2010 г. Каскадная схема
- 5. Стена Фокса Москва, 2010 г. n –
- 6. Метод геометрического параллелизма Москва, 2010 г.
- 7. Метод коллективного решения (укладка паркета)
- 8. Метод коллективного решения (укладка паркета) Москва,
- 9. Метод конвейерного параллелизма Москва, 2010 г.
- 10. Москва, 2010 г. ? Метод конвейерного параллелизма
- 11. Метод конвейерного параллелизма Москва, 2010 г.
- 12. Москва, 2010 г. Введение в параллельные алгоритмы:
- 13. Москва, 2010 г. Введение в параллельные алгоритмы:
- 14. Москва, 2010 г. Введение в параллельные алгоритмы:
- 15. Москва, 2010 г. Введение в параллельные алгоритмы:
- 16. Москва, 2010 г. Введение в параллельные алгоритмы:
- 17. Москва, 2010 г. Введение в параллельные алгоритмы:
- 18. Москва, 2010 г. Введение в параллельные алгоритмы:
- 19. Москва, 2010 г. Введение в параллельные алгоритмы:
- 20. Москва, 2010 г. Введение в параллельные алгоритмы:
- 21. Москва, 2010 г. Введение в параллельные алгоритмы:
- 22. Москва, 2010 г. Введение в параллельные алгоритмы:
- 23. Москва, 2010 г. Введение в параллельные алгоритмы:
- 24. Метод конвейерного параллелизма Москва, 2010 г.
- 25. Москва, 2010 г. Введение в параллельные
- 26. Москва, 2010 г. Введение в параллельные
- 27. Причины дисбаланса вычислительной нагрузки Разные процессоры Внешнее
- 28. Медленный процессор Москва, 2010 г. Какой объем
- 29. Метод геометрического параллелизма Москва, 2010 г.
- 30. Метод геометрического параллелизма Москва, 2010 г.
- 31. Диффузная балансировка загрузки Москва, 2010 г.
- 32. Диффузная балансировка загрузки Москва, 2010 г.
- 33. Диффузная балансировка загрузки Москва, 2010 г.
- 34. Статическое распределение Москва, 2010 г.
- 35. Москва, 2010 г. Постановка задачи диффузной балансировки
- 36. Москва, 2010 г.
- 37. Статическая и динамическая балансировка загрузки процессоров Статическая
- 38. Общая схема вычислений Москва, 2010 г. K
- 39. r=0; for(i=0;i
- 40. Последовательное распространение разряда переноса на четырёх процессорах
- 41. Москва, 2010 г. ? Параллельный
- 42. Спекулятивное вычисление двух сумм Спекулятивный алгоритм
- 43. r1=0; r2=1; for(i=0;i
- 44. Спекулятивное вычисление двух сумм Спекулятивный алгоритм
- 45. Рассмотрены некоторые методы построения параллельных алгоритмов
- 46. Якобовский М.В. проф., д.ф.-м.н., зав.
… если для нас представляют интерес реально работающие системы, то требуется убедиться, (и убедить всех сомневающихся) в корректности наших построений … системе часто придется работать в невоспроизводимых
Слайд 1Интернет Университет
Суперкомпьютерных технологий
Лекция 3
Методы построения параллельных программ (продолжение)
Учебный курс
Введение в
параллельные алгоритмы
Слайд 2 … если для нас представляют интерес реально работающие системы,
то требуется убедиться, (и убедить всех сомневающихся) в корректности наших построений
… системе часто придется работать в невоспроизводимых обстоятельствах, и мы едва ли можем ожидать сколько-нибудь серьезной помощи от тестов
Dijkstra E.W.
1966
… системе часто придется работать в невоспроизводимых обстоятельствах, и мы едва ли можем ожидать сколько-нибудь серьезной помощи от тестов
Dijkstra E.W.
1966
Предварительные замечания
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 3Методы построения параллельных алгоритмов и их свойства:
Статическая балансировка
метод сдваивания
геометрический параллелизм
конвейерный параллелизм
Динамическая
балансировка
коллективное решение
диффузная балансировка загрузки
коллективное решение
диффузная балансировка загрузки
Содержание лекции
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 4Метод сдваивания
Москва, 2010 г.
Каскадная схема
Модифицированная каскадная схема
В.П.Гергель Основы параллельных вычислений,
лекция 4, слайд 23
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 5Стена Фокса
Москва, 2010 г.
n – ширина стены
к – высота стены
Введение
в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 6Метод геометрического параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 7
Метод коллективного решения (укладка паркета)
Москва, 2010 г.
Введение в параллельные алгоритмы:
Методы построения параллельных программ © Якобовский М.В.
Слайд 8
Метод коллективного решения (укладка паркета)
Москва, 2010 г.
Число порций
Обработка порции
Обмен данными
r –
размер порции
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 9Метод конвейерного параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 10Москва, 2010 г.
?
Метод конвейерного параллелизма
Время выполнения на p процессорах
Введение в
параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 11Метод конвейерного параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 12Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
for(t=0;t 0 1 2 3 4 5 6 7 f[i] fnew[i]
fnew[0]=g(t);
for(i=1;i
for(i=0;i
}
Слайд 13Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 14Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 15Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 16Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 17Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 18Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 19Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 20Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 21Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 22Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 23Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 24Метод конвейерного параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 25
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 26
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Объём хранимых данных
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 27Причины дисбаланса вычислительной нагрузки
Разные процессоры
Внешнее воздействие
Разная вычислительная сложность заданий
Результат дисбаланса
Эффективная производительность
определяется самым медленным процессором
Диффузная балансировка
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 28Медленный процессор
Москва, 2010 г.
Какой объем работ забрать у среднего процессора и
кому его передать?
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 29Метод геометрического параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 30Метод геометрического параллелизма
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 31Диффузная балансировка загрузки
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 32Диффузная балансировка загрузки
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 33Диффузная балансировка загрузки
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 34Статическое распределение
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных
программ © Якобовский М.В.
Слайд 35Москва, 2010 г.
Постановка задачи диффузной балансировки
Дано:
Количество точек – N
Количество процессоров –
p
Процессор i обработал ni точек за время ti
Требуется:
Найти количества точек n’i , которое следует обработать процессорам на следующем шаге
Определить сколько точек каждый из процессоров должен передать соседним процессорам
Процессор i обработал ni точек за время ti
Требуется:
Найти количества точек n’i , которое следует обработать процессорам на следующем шаге
Определить сколько точек каждый из процессоров должен передать соседним процессорам
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 36
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
Диффузная балансировка
Слайд 37Статическая и динамическая балансировка загрузки процессоров
Статическая балансировка
метод сдваивания
геометрический параллелизм
конвейерный параллелизм
Динамическая балансировка
коллективное
решение
диффузная балансировка
диффузная балансировка
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Резюме
Слайд 38Общая схема вычислений
Москва, 2010 г.
K = 1 000 000;
шаг_вывода = 10
000;
for(шаг=0;шаг{
for(кирпич=rank*n/p;кирпич<(rank+1)*n/p;кирпич++)
Уложить (кирпич)
Обменяться данными о точках, прилегающих к внутренним границам()
if( шаг % шаг_вывода == 0 )
{
Вывести промежуточные результаты()
}
}
for(шаг=0;шаг
for(кирпич=rank*n/p;кирпич<(rank+1)*n/p;кирпич++)
Уложить (кирпич)
Обменяться данными о точках, прилегающих к внутренним границам()
if( шаг % шаг_вывода == 0 )
{
Вывести промежуточные результаты()
}
}
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 40Последовательное распространение разряда переноса на четырёх процессорах
«Параллельный» алгоритм
Москва, 2010 г.
Введение
в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 41Москва, 2010 г.
?
Параллельный алгоритм
«
»
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 42Спекулятивное вычисление двух сумм
Спекулятивный алгоритм
Москва, 2010 г.
Введение в параллельные алгоритмы:
Методы построения параллельных программ © Якобовский М.В.
Слайд 43r1=0;
r2=1;
for(i=0;i
8n1τс
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 44Спекулятивное вычисление двух сумм
Спекулятивный алгоритм
Москва, 2010 г.
Введение в параллельные алгоритмы:
Методы построения параллельных программ © Якобовский М.В.
Слайд 45Рассмотрены некоторые методы построения параллельных алгоритмов
Рассмотрен алгоритм диффузной балансировки загрузки процессоров
Представлен
масштабируемый параллельный алгоритм, основанный на неэффективном последовательном алгоритме
Заключение
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 46Якобовский М.В.
проф., д.ф.-м.н.,
зав. сектором
«Программного обеспечения многопроцессорных систем и
вычислительных сетей»
Института прикладной математики им. М.В.Келдыша Российской академии наук
mail: mail: lira@imamod.rumail: lira@imamod.ru
web: web: http://lira.imamod.ru
Института прикладной математики им. М.В.Келдыша Российской академии наук
mail: mail: lira@imamod.rumail: lira@imamod.ru
web: web: http://lira.imamod.ru
Контакты
Москва, 2010 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
