Интернет Университет Суперкомпьютерных технологий Введение Учебный курс Введение в параллельные алгоритмы Якобовский М.В., проф., д.ф.-м.н. Институт прикладной математики им. М.В.Келдыша РАН, Москва

Цель курса Изучение методов разработки параллельных программ для многопроцессорных вычислительных систем Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 2

Производительность процессора Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 3

Производительность и тактовая частота процессорного ядра Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 4 2,4 кратный рост

Число операций, выполняемых процессорным ядром за один такт Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 5 2 кратный рост

Производительность процессора Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 6

Некоторые системы top500.org Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 7 Cores Rmax Tflops Rpeak Tflops Power MW 1. Sequoia, BlueGene/Q, Power BQC 16C 1.60 GHz, Custom K computer, SPARC64 VIIIfx 2.0GHz, Tofu interconnect / 2011 Fujitsu «Ломоносов», Xeon X5570/X GHz, Nvidia 2070 GPU, PowerXCell 8i, Infiniband QDR Время вычислительных систем, обладающих существенной производительностью и имеющих в своем составе только один процессор прошло

Дозвуковая аэродинамическая труба Т-104, ЦАГИ Скорость потока 10–120 м/с Диаметр сопла 7 м Длина рабочей части 13 м Мощность вентилятора 28.4 МВт Суперкомпьютер СКИФ МГУ «ЧЕБЫШЁВ» Пиковая производительность 60 TFlop/s Мощность комплекса 0.72 МВт Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 8

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

Использование мощностей суперкомпьютеров Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 10 Не конкретизировано Исследования

Вычислительная мощность суперкомпьютеров огромна, но: –Она образована суммой мощностей множества исполнительных устройств На протяжении многих лет увеличение производительность компьютера автоматически означало снижение времени работы существующих программ. Теперь это не так: –Последовательные программы не могут работать на суперкомпьютерах быстрее, чем на однопроцессорных (одноядерных) компьютерах Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 11

Области применения многопроцессорных систем 1)сокращение времени решения вычислительно сложных задач 2)сокращение времени обработки больших объемов данных 3)решение задач реального времени 4) создание систем высокой надежности Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 12

Задачи большого вызова (Kenneth G. Wilson, Cornell University, 1987) Вычислительная газовая динамика: –Создание летательных аппаратов, эффективных автомобильных –Предсказания погоды, и глобальных климатических изменений –Оптимизация нефтедобычи, … Молекулярная динамика: –Создание материалов с заданными свойствами –Разработка новых лекарственных соединений –Сверхпроводимость, Свойства веществ в экстремальных состояниях, … Символьные вычисления –Распознавание речи –Компьютерное зрение –Изучение сложных систем –Автономные системы управления Квантовая хромодинамика и теория конденсированных сред Управляемый термоядерный синтез, Геном человека, … Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 13

Особенности момента Потребность в суперкомпьютерах высока Эффективность использования суперкомпьютеров низка: –Использование каждого ядра последовательной программой составляет проценты и доли процентов –Обмены, синхронизация и другие дополнительные операции снижают эффективность параллельной программы Есть минимальный объем вычислений на процессорное ядро, определяющий число используемых ядер За счет многопроцессорности сложно сокращать время моделирования физического процесса, но можно повышать сложность решаемых задач, например за счет увеличения размеров изучаемых объектов 14

Уточнение круга рассматриваемых алгоритмов Слабо взаимодействующие последовательные процессы Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 15 Вычисления Взаимодействие

Время вычислительных систем, обладающих существенной производительностью и имеющих в своем составе только один процессор прошло Автоматическое создание параллельных программ невозможно Необходимо знать существующие и развивать новые параллельные методы решения задач Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 16

Уточнение круга рассматриваемых систем Системы на основе объединенных сетью типовых вычислительных узлов – системы с распределенной оперативной памятью Системы с доступом всех процессоров к общей оперативной памяти Графические ускорители ПЛИС Нейрокомпьютеры Другие … Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 17

Некоторые из принципов фон Неймана Принцип последовательного программного управления –Программа состоит из набора команд, которые выполняются процессором друг за другом в определенной последовательности Принцип адресуемости памяти –Память состоит из пронумерованных ячеек –Процессору в произвольный момент времени доступна любая ячейка Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 18

Отличие от систем фон Неймана Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 19 Принцип последовательного программного управления Программа состоит из набора команд, которые выполняются процессором друг за другом в определенной последовательности Принцип адресуемости памяти Память состоит из пронумерованных ячеек Процессору в произвольный момент времени доступна любая ячейка Вычисления Взаимодействие

Основные мотивы возникновения курса Сложность создания параллельных алгоритмов и программ: –Неадекватность алгоритмов архитектуре ЭВМ –Недетерминированность параллельных программ –Возможность возникновения тупиков Требует привлечения: –Апробированных, логически простых методов, гарантированно дающих положительный эффект Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 20

Характеристика необходимых знаний и умений Для успешного освоения основного материала курса необходимо: –Знание основ программирования –Общее представление об архитектуре вычислительных систем фон Неймана –Умение оценивать вычислительную сложность простых алгоритмов Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 21

Характеристика необходимых знаний и умений Для выполнения практических заданий необходимы навыки разработки простых параллельных программ, например: –на основе MPI для систем с распределенной памятью –на основе OpenMP или стандарта Posix для систем с общей памятью Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 22

Содержание курса Средства описания параллельных алгоритмов Методы построения параллельных алгоритмов Параллельные алгоритмы сортировки данных Параллельные алгоритмы генерации псевдослучайных чисел Динамическая балансировка загрузки процессоров Параллельные алгоритмы решения систем линейных уравнений Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 23

Средства описания параллельных алгоритмов Структура приложения, выполняющегося на вычислительной системе с распределенной памятью –Методы передачи сообщений Структура приложения, выполняющегося на вычислительной системе с общей памятью –Семафоры –Нити Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 24

Методы построения параллельных алгоритмов Виды параллелизма –Метод сдваивания –Геометрический параллелизм –Метод коллективного решения –Конвейерный параллелизм Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 25

Динамическая балансировка загрузки процессоров Общий взгляд на классификацию методов балансировки загрузки процессоров Задачи, требующие применения методов динамической балансировки загрузки Пример простого алгоритма динамической балансировки загрузки Статическая Динамическая диффузная Динамическая? W i j = W i j – не зависит от времени W i j W i j-1 – меняется медленно W i j W i j-1 – меняется значительно и непрогнозируемо Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 26

27

Эффективность сетка 1000x

Заключение Время однопроцессорных вычислительных систем прошло. Не только суперкомпьютеры, но и современные персональные компьютеры, ноутбуки, игровые приставки основаны на многопроцессорных, многоядерных и других технологиях, предполагающих одновременное выполнение множества инструкций. Для их полноценного использования необходимо иметь представление как о проблемах, возникающих при параллельной обработке данных, так и о базовых методах разработки параллельных алгоритмов и приложений, на получение которого и направлен представленный курс. Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 29

Литература… Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, Грегори Р. Эндрюс - Основы многопоточного, параллельного и распределенного программирования. "Вильямс ", 2003 Роберт Седжвик - Фундаментальные алгоритмы на C. Части Анализ. Структуры данных. Сортировка. Поиск. Алгоритмы на графах Языки програмирования. Редактор Ф.Женюи. Перевод с англ В.П.Кузнецова. Под ред. В.М.Курочкина. М:."Мир", 1972 Э. Дейкстра. Взаимодействие последовательных процессов. iip.mipk.kharkiv.edu/library/extent/dijkstra/ewd123/index.html iip.mipk.kharkiv.edu/library/extent/dijkstra/ewd123/index.html Дональд Э. Кнут Искусство программирования. Том 3. Сортировка и поиск Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 30

Литература… Учебные курсы Интернет Университета Информационных технологий Гергель В.П. Теория и практика параллельных вычислений. Лекции в форме видео-конференций Гергель В.П. Основы параллельных вычислений. Немнюгин С.А. Основы параллельного программирования с использованием MPI. Крюков В.А., Бахтин В.А. Параллельное программирование с OpenMP. Дополнительные учебные курсы: Воеводин В.В. Вычислительная математика и структура алгоритмов. Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 31

Литература Ресурсы Internet Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 32

Вопросы для обсуждения Какие классы задач решаются с применением многопроцессорных систем и суперкомпьютеров? Какие факторы препятствуют эффективному использованию многопроцессорных систем? В чем качественное отличие многопроцессорных систем от систем архитектуры фон Неймана? В чем качественное отличие между алгоритмами для вычислительных систем с большим и с малым числом процессоров? Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 33

Якобовский М.В., профессор, д.ф.-м.н., зав. сектором «Программного обеспечения многопроцессорных систем и вычислительных сетей» Института прикладной математики им. М.В.Келдыша Российской академии наук mail: web: Контакты Москва, 2012 г. Введение в параллельные алгоритмы: Введение © Якобовский М.В. 34