Якобовский Михаил Владимирович
проф., д.ф.-м.н.
Институт прикладной математики им. М.В.Келдыша РАН, Москва
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Интернет Университет Суперкомпьютерных технологий презентация
Содержание
- 1. Интернет Университет Суперкомпьютерных технологий
- 2. Методы построения параллельных алгоритмов и их свойства:
- 3. Метод сдваивания Москва, 2011 г. Каскадная схема
- 4. Метод геометрического параллелизма Москва, 2011 г.
- 5. Метод коллективного решения (укладка паркета) Москва,
- 6. Метод конвейерного параллелизма Москва, 2011 г.
- 7. Москва, 2011 г. ? Метод конвейерного параллелизма
- 8. Метод конвейерного параллелизма Москва, 2011 г.
- 9. Москва, 2011 г. Введение в параллельные алгоритмы:
- 10. Москва, 2011 г. Введение в параллельные алгоритмы:
- 11. Москва, 2011 г. Введение в параллельные алгоритмы:
- 12. Москва, 2011 г. Введение в параллельные алгоритмы:
- 13. Москва, 2011 г. Введение в параллельные алгоритмы:
- 14. Москва, 2011 г. Введение в параллельные алгоритмы:
- 15. Москва, 2011 г. Введение в параллельные алгоритмы:
- 16. Москва, 2011 г. Введение в параллельные алгоритмы:
- 17. Москва, 2011 г. Введение в параллельные алгоритмы:
- 18. Москва, 2011 г. Введение в параллельные алгоритмы:
- 19. Москва, 2011 г. Введение в параллельные алгоритмы:
- 20. Москва, 2011 г. Введение в параллельные алгоритмы:
- 21. Метод конвейерного параллелизма Москва, 2011 г.
- 22. Москва, 2011 г. Введение в параллельные
- 23. Москва, 2011 г. Введение в параллельные
- 24. Причины дисбаланса вычислительной нагрузки Разные процессоры Внешнее
- 25. Медленный процессор Москва, 2011 г. Какой объем
- 26. Метод геометрического параллелизма Москва, 2011 г.
- 27. Метод геометрического параллелизма Москва, 2011 г.
- 28. Диффузная балансировка загрузки Москва, 2011 г.
- 29. Диффузная балансировка загрузки Москва, 2011 г.
- 30. Диффузная балансировка загрузки Москва, 2011 г.
- 31. Статическое распределение Москва, 2011 г.
- 32. Москва, 2011 г. Постановка задачи диффузной балансировки
- 33. Москва, 2011 г.
- 34. Статическая и динамическая балансировка загрузки процессоров Статическая
- 35. Иные алгоритмы Москва, 2011 г. Замедлить,
- 36. r=0; for(i=0;i
- 37. Последовательное распространение разряда переноса на четырёх процессорах
- 38. Москва, 2011 г. ? Параллельный
- 39. Спекулятивное вычисление двух сумм Спекулятивный алгоритм
- 40. r1=0; r2=1; for(i=0;i
- 41. Спекулятивное вычисление двух сумм Спекулятивный алгоритм
- 42. Общая схема вычислений Москва, 2011 г. K
- 43. Рассмотрены некоторые методы построения параллельных алгоритмов
- 44. Якобовский М.В. проф., д.ф.-м.н., зав.
Слайд 1Интернет Университет
Суперкомпьютерных технологий
Лекция 3
Методы построения параллельных программ (продолжение)
Учебный курс
Введение в
параллельные алгоритмы
Слайд 2Методы построения параллельных алгоритмов и их свойства:
Статическая балансировка
метод сдваивания
геометрический параллелизм
конвейерный параллелизм
Динамическая
балансировка
коллективное решение
диффузная балансировка загрузки
коллективное решение
диффузная балансировка загрузки
Содержание лекции
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 3Метод сдваивания
Москва, 2011 г.
Каскадная схема
Модифицированная каскадная схема
В.П.Гергель Основы параллельных вычислений,
лекция 4, слайд 23
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 4Метод геометрического параллелизма
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 5
Метод коллективного решения (укладка паркета)
Москва, 2011 г.
Число порций
Обработка порции
Обмен данными
r –
размер порции
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 6Метод конвейерного параллелизма
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 7Москва, 2011 г.
?
Метод конвейерного параллелизма
Время выполнения на p процессорах
Введение в
параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 8Метод конвейерного параллелизма
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 9Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
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
}
Слайд 10Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 11Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 12Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 13Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 14Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 15Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 16Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 17Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 18Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 19Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 20Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 21Метод конвейерного параллелизма
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 22
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Метод конвейерного параллелизма
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 23
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский
М.В.
Объём хранимых данных
процессор 0 процессор 1 процессор 2 процессор 3
Слайд 24Причины дисбаланса вычислительной нагрузки
Разные процессоры
Внешнее воздействие
Разная вычислительная сложность заданий
Результат дисбаланса
Эффективная производительность
определяется самым медленным процессором
Диффузная балансировка
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 25Медленный процессор
Москва, 2011 г.
Какой объем работ забрать у среднего процессора и
кому его передать?
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 26Метод геометрического параллелизма
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 27Метод геометрического параллелизма
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 28Диффузная балансировка загрузки
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 29Диффузная балансировка загрузки
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 30Диффузная балансировка загрузки
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения
параллельных программ © Якобовский М.В.
Слайд 31Статическое распределение
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных
программ © Якобовский М.В.
Слайд 32Москва, 2011 г.
Постановка задачи диффузной балансировки
Дано:
Количество точек – N
Количество процессоров –
p
Процессор i обработал ni точек за время ti
Требуется:
Найти количества точек n’i , которое следует обработать процессорам на следующем шаге
Определить сколько точек каждый из процессоров должен передать соседним процессорам
Процессор i обработал ni точек за время ti
Требуется:
Найти количества точек n’i , которое следует обработать процессорам на следующем шаге
Определить сколько точек каждый из процессоров должен передать соседним процессорам
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 33
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ
© Якобовский М.В.
Диффузная балансировка
Слайд 34Статическая и динамическая балансировка загрузки процессоров
Статическая балансировка
метод сдваивания
геометрический параллелизм
конвейерный параллелизм
Динамическая балансировка
коллективное
решение
диффузная балансировка
диффузная балансировка
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Простые алгоритмы
Слайд 35Иные алгоритмы
Москва, 2011 г.
Замедлить, чтобы выполнить быстрее
Введение в параллельные алгоритмы:
Методы построения параллельных программ © Якобовский М.В.
Слайд 37Последовательное распространение разряда переноса на четырёх процессорах
«Параллельный» алгоритм
Москва, 2011 г.
Введение
в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 38Москва, 2011 г.
?
Параллельный алгоритм
«
»
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 39Спекулятивное вычисление двух сумм
Спекулятивный алгоритм
Москва, 2011 г.
Введение в параллельные алгоритмы:
Методы построения параллельных программ © Якобовский М.В.
Слайд 40r1=0;
r2=1;
for(i=0;i
8n1τс
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 41Спекулятивное вычисление двух сумм
Спекулятивный алгоритм
Москва, 2011 г.
Введение в параллельные алгоритмы:
Методы построения параллельных программ © Якобовский М.В.
Слайд 42Общая схема вычислений
Москва, 2011 г.
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 )
{
Вывести промежуточные результаты()
}
}
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 43Рассмотрены некоторые методы построения параллельных алгоритмов
Рассмотрен алгоритм диффузной балансировки загрузки процессоров
Представлен
масштабируемый параллельный алгоритм, основанный на неэффективном последовательном алгоритме
Заключение
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
Слайд 44Якобовский М.В.
проф., д.ф.-м.н.,
зав. сектором
«Программного обеспечения вычислительных систем и
сетей»
Института прикладной математики им. М.В.Келдыша Российской академии наук
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
Контакты
Москва, 2011 г.
Введение в параллельные алгоритмы: Методы построения параллельных программ © Якобовский М.В.
