Современные технологии параллельного программирования Перепелкин В.А. м.н.с. ИВМиМГ СО РАН Летняя школа параллельных вычислений 2012 г. Институт вычислительной математики и математической геофизики СО РАН

Параллельные вычисления в нашей жизни Многоядерные настольные компьютеры, ноутбуки и смартфоны Многоядерные настольные компьютеры, ноутбуки и смартфоны Вычислительные кластеры в университетах, институтах и промышленных предприятиях Вычислительные кластеры в университетах, институтах и промышленных предприятиях Сети банкоматов и мультикасс Сети банкоматов и мультикасс Социальные сети Социальные сети Многопользовательские игры Многопользовательские игры

Где нужны параллельные вычисления Высокая производительность – количество вычислений в единицу времени Высокая производительность – количество вычислений в единицу времени Большие объемы памяти Большие объемы памяти Распределенность – «привязка» системы к удалённым частям реальности Распределенность – «привязка» системы к удалённым частям реальности

Потребности в вычислительных мощностях на примере задачи моделирования климата Лишь атмосфера, период 100 лет: операций * операций * Производительность компьютеров измеряется в операциях в секунду: 1 Pflops = 10 3 Tflops = 10 6 Gflops = операций в секунду Потребности в производительности: Решить задачу за час: 27,8 Tflops Решить задачу за 12 часов: 2,3 Tflops Решить задачу за месяц: 0,04 Tflops *В.В. Воеводин. Вычислительная математика и структура алгоритмов. М.:МГУ, 2006: сетка с ячейкой 1°, 40 слоев по высоте, шаг по времени минут. Wikipedi a

Исследование конформационной подвижности мутантных форм белков ИЦиГ СО РАН, НовосибирскИТПМ СО РАН, Новосибирск Моделирование обтекания перспективных спускаемых космических аппаратов Исследование конформационной подвижности мутантных форм белков

Астрофизика Программы президиума РАН: «Происхождение и эволюция биосферы» «Происхождение и эволюция звезд и галактик» ИК СО РАН, Институт астрономии РАН ИВМ и МГ СО РАН

Сервисы в Интернете Нагрузка в поисковике «Яндекс»: Нагрузка в поисковике «Яндекс»: –30 млн. запросов в день –Поиск по нескольким миллиардам документов –Более 20 тыс. серверов по всему миру (из них 100 в среднем сломано) (из них 100 в среднем сломано) –Время отклика менее 0,5 сек.

Почему не делать сверхмощных последовательных компьютеров? Тактовая частота процессора: 500 ГГц Тактовая частота процессора: 500 ГГц Система охлаждения на основе жидкого гелия Система охлаждения на основе жидкого гелия IBM и Georgia Institute of Technology, 2006 г. IBM и Georgia Institute of Technology, 2006 г.

Три «стены» последовательных архитектур процессоров Стена памяти: относительная производительность памяти падает Стена памяти: относительная производительность памяти падает Стена тактовой частоты: экспоненциальный рост тепловыделения, кремний плавится Стена тактовой частоты: экспоненциальный рост тепловыделения, кремний плавится Стена техпроцесса: размер транзистора уменьшился до размера нескольких атомов Стена техпроцесса: размер транзистора уменьшился до размера нескольких атомов

Самые высокопроизводительные ресурсы планеты Вычислительный кластер Sequoia (IBM, USA) Вычислительный кластер Sequoia (IBM, USA) –1,5 млн. ядер –Потребляет 8 МВатт –1,5 Пбайт памяти –Производительность 20 PFlops Грид-систма BOINC (добровольные вычисления, проект университета Беркли) Грид-систма BOINC (добровольные вычисления, проект университета Беркли) –0,5 млн. компьютеров –Производительность 6 PFlops

Системы программирования (не только параллельного) Цель: облегчить труд программиста (но не заменить) Цель: облегчить труд программиста (но не заменить) Функции: Функции: –Рефакторинг кода –Управление проектом –Программные оптимизации кода –Фоновая компиляция и сборка проекта –Помощь в отладке –…

Особенности параллельного программирования Существенно более важна настройка на оборудование Существенно более важна настройка на оборудование Параллельная программа недетерминирована (многовариантна) – её сложнее понимать и контролировать Параллельная программа недетерминирована (многовариантна) – её сложнее понимать и контролировать Сложнее обеспечивать переносимость программ (с сохранением свойств исполнения) Сложнее обеспечивать переносимость программ (с сохранением свойств исполнения) Данные распределены по разным компьютерам – необходимо организовать к ним доступ Данные распределены по разным компьютерам – необходимо организовать к ним доступ Необходимо синхронизовать доступ к общим ресурсам разных компьютеров Необходимо синхронизовать доступ к общим ресурсам разных компьютеров В целом параллельная программа должна быть «умнее», чем последовательная, а значит – её сложнее создать

Наивный подход: автоматическое распараллеливание кода Идея: создать программу, преобразующую последовательные программы в параллельные Идея: создать программу, преобразующую последовательные программы в параллельные Автоматическое распараллеливание – трудноавтоматизируемая задача Автоматическое распараллеливание – трудноавтоматизируемая задача Нет возможности проводить алгоритмическую оптимизацию, а значит преобразовать алгоритм из последовательного в параллельный Нет возможности проводить алгоритмическую оптимизацию, а значит преобразовать алгоритм из последовательного в параллельный

Автоматическая эффективная реализация алгоритма Классическая задача планирования является NP-полной Классическая задача планирования является NP-полной Трудно автоматически обеспечить эффективную реализацию алгоритма Трудно автоматически обеспечить эффективную реализацию алгоритма

Автоматическая отладка параллельных программ Проблема останова – классический пример алгоритмически неразрешимой задачи Проблема останова – классический пример алгоритмически неразрешимой задачи Верификация параллельного кода существенно сложнее, чем последовательного, за счёт недетерминизма исполнения Верификация параллельного кода существенно сложнее, чем последовательного, за счёт недетерминизма исполнения

Необходимость использования дополнительных (частных) моделей Программа содержит в себе всю информацию о себе, но извлечь её система программирования может не всегда и не всю Программа содержит в себе всю информацию о себе, но извлечь её система программирования может не всегда и не всю

Промежуточный итог: Как оценивать системы ПП? Что автоматизируется системой? Что автоматизируется системой? –Проработка труднорешаемых задач Какой ценой это достигается? Какой ценой это достигается? –К какой модели необходимо «привязать» программу Какова область применения системы? Какова область применения системы? –В каких случаях её использование оправдано

OpenMP: Open MultiProcessing

Модель: потоки в общей памяти Модель: потоки в общей памяти Идея: разметка кода на параллельные секции Идея: разметка кода на параллельные секции Автоматизация: генерация параллельного кода Автоматизация: генерация параллельного кодаОсобенности: –Человек принимает решения о распараллеливании и описывает их декларативно –Машина реализует эти решения

MPI: Message Passing Interface

Модель: сообщающиеся процессы Модель: сообщающиеся процессы Идея: предоставить интерфейс для синхронизации и обмена сообщениями Идея: предоставить интерфейс для синхронизации и обмена сообщениями Автоматизация: виртуализация аппаратного обеспечения Автоматизация: виртуализация аппаратного обеспеченияОсобенности: –Необходимые свойства программы человек выбирает и обеспечивает сам

Charm++ и ProActive

Модель: акторы Модель: акторы Идея: дать средства для описания программы в модели акторов Идея: дать средства для описания программы в модели акторов Автоматизация: реализуется модель акторов Автоматизация: реализуется модель акторовОсобенности: –Есть возможность обеспечивать многие свойства программы автоматически

OpenTS: Open T-System

Модель: аппликативная (функциональная) Модель: аппликативная (функциональная) Идея: выделить функции без т.н. «побочных эффектов» и реализовывать их параллельно Идея: выделить функции без т.н. «побочных эффектов» и реализовывать их параллельно Автоматизация: распараллеливание графа вызова функций Автоматизация: распараллеливание графа вызова функцийОсобенности: –Независимо от «содержательной» части алгоритма автоматически решается задача выбора эффективной реализации

KeLP: Kernel Lattice Parallelism

Модель: распределенная обработка данных Модель: распределенная обработка данных Идея: генерировать программу на основе описания численных алгоритмов на сетках Идея: генерировать программу на основе описания численных алгоритмов на сетках Автоматизация: генерируется программа целиком на основе описания сеток и вычислений на них Автоматизация: генерируется программа целиком на основе описания сеток и вычислений на нихОсобенности: –За счёт специализации в конкретной области достигается полная автоматизация программирования

Parallel Haskell Модель: аппликативная (функциональная) Модель: аппликативная (функциональная) Идея: реализация декларативной программы на параллельном вычислителе, места распараллеливания указывает человек Идея: реализация декларативной программы на параллельном вычислителе, места распараллеливания указывает человек Автоматизация: генерация программы по заданной спецификации Автоматизация: генерация программы по заданной спецификацииОсобенности: –Полная автоматизация, что означает узкую прикладную область, но гарантированную корректность

LuNA: Language for Numerical Algorithms mxm.cpp const N=200; const M=10; df A[i,j] := block(8*N*N) | i=..M,j=..M; df B[i,j] := block(8*N*N) | i=..M,j=..M; df C[i,j] := block(8*N*N) | i=..M,j=..M; cf mul[i,j,k] := mult (in: A[i,k], B[k,j], C[i,j]; out: C[i,j]) | i=..M, j=..M, k=..M; mul[i,j,k].location = i*L/M*L+j*L/M | i=..M,j=..M,k=..M; mul[i,j,k].priority = M+(i+j-k+M)%M | i=..M,j=..M,k=..M;

LuNA: Language for Numerical Algorithms Модель: Аппликативная (функциональная) Модель: Аппликативная (функциональная) Идея: Автоматизировать генерацию программы, но сделать эту генерацию управляемой человеком Идея: Автоматизировать генерацию программы, но сделать эту генерацию управляемой человеком Автоматизация: Генерация программы в соответствии с декларативными схемами исполнения Автоматизация: Генерация программы в соответствии с декларативными схемами исполненияОсобенности: –Удобная модель программы для автоматизации программирования –Разделение труда между человеком и машиной в соответствии с их возможностями

Итоги лекции Параллельное программирование сложно и потому важную роль играют системы параллельного программирования Параллельное программирование сложно и потому важную роль играют системы параллельного программирования Не всю работу возможно выполнять автоматически и необходимо понимать где проходит разделение ролей человека и машины Не всю работу возможно выполнять автоматически и необходимо понимать где проходит разделение ролей человека и машины Существует и развивается множество систем параллельного программирования Существует и развивается множество систем параллельного программирования

Спасибо за внимание Спасибо за внимание

A B C A i,k ABC B k,j C i,j 33 Пример отображения ФА на мультикомпьютер ФВ отображены на узлы мультикомпьютера ФВ отображены на узлы мультикомпьютера Зафиксирован порядок выполнения ФВ Зафиксирован порядок выполнения ФВ Зафиксированы маршруты перемещения ФД Зафиксированы маршруты перемещения ФД