Параллельное программированиедля ресурсоёмких задач численного моделирования в физике

Физический факультет МГУ им М.В.Ломоносова
Лекция № 1

Физический факультет МГУ им М.В.Ломоносова
Содержание курса
Введение
Архитектура высокопроизводительных систем
Особенности параллельных вычислений
Работа с кластером; операционная система Linux
Технология OpenMP
Интерфейс передачи сообщений MPI
Моделирование физических задач средствами OpenMP и MPI

Структура курса
лекции
практические занятия
самостоятельные задания
ЗАЧЕТ
Физический факультет МГУ им М.В.Ломоносова

Развитие инструментов для научного процесса
Физический факультет МГУ им М.В.Ломоносова
1. Наблюдение
2. Гипотеза
4. Утверждение
3. Прогноз

Области применения суперкомпьютеров
Научно-исследовательские институты
Университеты
Геофизика
Биология
Метеорология
Финансовая область
Энергетика
Наукоемкие отрасли промышленности
Медицина
Генетика
Геологоразведка
Контроль за окружающей средой
Физический факультет МГУ им М.В.Ломоносова

Пример проблемы решаемой с помощью параллельного программирования
Car Crash Simulation:
Поверхность машины моделируется как считанное количество треугольных элементов.
Моделируется позиция каждого элемента во времени с учетом сил действующих на него и его свойств.
Каждый элемент взаимодействует только с соседними элементами
Физический факультет МГУ им М.В.Ломоносова

Сетка конечных элементов
Физический факультет МГУ им М.В.Ломоносова

Архитектура ЭВМ
Архитектура компьютера
Организация компьютера
Схема компьютера
Физический факультет МГУ им М.В.Ломоносова

Архитектура фон Неймана
Программа хранится в компьютере
Программа во время выполнения и необходимые для её работы данные находятся в оперативной памяти
Имеется арифметико-логическое устройство, выполняющее арифметические и логические операции с данными
Имеется устройство управления, которое интерпретирует команды, выбираемые из памяти, и выполняет их
Устройства ввода и вывода используются для ввода программ и данных и для вывода результатов расчетов. Работают под управлением УУ
Физический факультет МГУ им М.В.Ломоносова

Физический факультет МГУ им М.В.Ломоносова
Архитектура фон Неймана II
ПАМЯТЬ
УСТРОЙСТВО
УПРАВЛЕНИЯ
АРИФМЕТИКО-
ЛОГИЧЕСКОЕ
УСТРОЙСТВО
ВВОД
ВЫВОД

Классификация Флинта
Физический факультет МГУ им М.В.Ломоносова

SISD-компьютеры
Физический факультет МГУ им М.В.Ломоносова

SIMD-компьютеры
Физический факультет МГУ им М.В.Ломоносова

MISD-компьютеры
Физический факультет МГУ им М.В.Ломоносова

MIMD-компьютеры
Физический факультет МГУ им М.В.Ломоносова

Компоненты компьютера
Центральный процессор и оперативная память
ядро системы
Внешняя память и устройства ввода/вывода
«периферия»
Коммуникации между компонентами системы
осуществляется посредством шин
Физический факультет МГУ им М.В.Ломоносова

Схема компьютера
Физический факультет МГУ им М.В.Ломоносова

Физический факультет МГУ им М.В.Ломоносова
In June 2010, 2 systems appeared in the TOP500 list.Rank
System Procs Memory(GB) Rmax (GFlops) Rpeak (GFlops) Vendor
13 LomonosovT-Platforms T-Blade2, Xeon 5570 2.93 GHz, Infiniband QDR 35360 54312 350100 414419 T-Platforms
121 SKIF MSUT-Platforms T60, Intel Quadcore 3Ghz, Infiniband DDR 5000 5000 47170 60000 SKIF/T-Platforms

Технологии параллельного программирования
“Все, что начинается хорошо, кончается плохо.
Все, что начинается плохо, кончается еще хуже.”
Из законов Мерфи
Физический факультет МГУ им М.В.Ломоносова

Особенности программирования параллельных вычислений
Физический факультет МГУ им М.В.Ломоносова
Модель программирования
Алгоритм
Информационный граф
Вход
Выход
(n, s)
(v, d)

Примеры алгоритмов
Последовательный
Параллельный
Физический факультет МГУ им М.В.Ломоносова

Основные черты последовательной модели
Применение стандартных языков программирования
Хорошая переносимость программ
Невысокая производительность
Физический факультет МГУ им М.В.Ломоносова

Основные черты параллельной модели
Высокая производительность программ
Применение специальных приёмов программирования
Более высокая трудоёмкость программирования
Проблемы с переносимостью программ
Физический факультет МГУ им М.В.Ломоносова

Фундаментальные требования к параллельным программам
Параллелизм
Локальность
Масштабируемость
Детерминизм
Физический факультет МГУ им М.В.Ломоносова

Параллелизм
Данных
Задач
Физический факультет МГУ им М.В.Ломоносова

Параллелизм данных
Основные особенности подхода:
Обработкой данных управляет одна программа
Пространство имен является глобальным
Слабая синхронизация вычислений на параллельных процессорах
Параллельные операции над элементами массива выполняются одновременно на всех доступных процессорах
Физический факультет МГУ им М.В.Ломоносова

Параллелизм задач
Повышенная трудоёмкость разработки и отладки программы
Программист отвечает за равномерную и сбалансированную загрузку процессоров
Минимизация обмена данными между задачами
Возникновение конфликтов
Физический факультет МГУ им М.В.Ломоносова

Модель задача/канал
задача
задача
задача
задача
задача
асинхронная
передача
синхронная
передача
Физический факультет МГУ им М.В.Ломоносова

Параллелизм задач
Большая гибкость
Большая свобода
Физический факультет МГУ им М.В.Ломоносова
Максимальное быстродействие

Масштабируемость
Независимость результата выполнения параллельной программы от числа процессоров.
Физический факультет МГУ им М.В.Ломоносова

Детерминизм
Физический факультет МГУ им М.В.Ломоносова

Закон Амдала
- один процессор
- N процессоров
Физический факультет МГУ им М.В.Ломоносова

Закон Амдала II
коэффициент ускорения выполнения программы
S - доля последовательной части
P - доля параллельной части
N - число независимых ветвей/процессоров
Физический факультет МГУ им М.В.Ломоносова

Две парадигмы параллельного программирования
Равномерная загрузка процессоров
Эффективная организация обмена информацией между задачами
Физический факультет МГУ им М.В.Ломоносова

Базовый набор операций
Операции управления данными
Операции над массивами в целом, а также их фрагментами
Условные операции
Операции приведения
Операции сдвига
Операции сканирования
Операции, связанные с пересылкой данных
Физический факультет МГУ им М.В.Ломоносова

Управление данными
Физический факультет МГУ им М.В.Ломоносова

Операции над массивами
Физический факультет МГУ им М.В.Ломоносова

Условные операции
Физический факультет МГУ им М.В.Ломоносова

Операции приведения
Физический факультет МГУ им М.В.Ломоносова

Операции сдвига
Физический факультет МГУ им М.В.Ломоносова

Операции сканирования
Физический факультет МГУ им М.В.Ломоносова

Операции пересылки данных
Физический факультет МГУ им М.В.Ломоносова

Разработка параллельного алгоритма
проблема
декомпозиция
коммуникации
укрупнение
планирование
вычислений
подзадачи
процессоры
Физический факультет МГУ им М.В.Ломоносова

Декомпозиция (сегментирование)
Метод декомпозиции данных
Метод функциональной декомпозиции
Физический факультет МГУ им М.В.Ломоносова

Рекомендации по декомпозиции
Количество подзадач должно на порядок превосходить количество процессоров
Следует избегать лишних вычислений и пересылок данных
Подзадачи должны быть примерно одного размера
С увеличением объема задачи количество подзадач увеличивалось
Физический факультет МГУ им М.В.Ломоносова

“Зернистость”
мелкозернистая
среднеблочный
крупноблочный
< 20
~ 500
независимые
программы
Через разделяемые переменные
Через сообщения
Физический факультет МГУ им М.В.Ломоносова

Независимость частей программы
Независимость по данным
Независимость по управлению
Независимость по ресурсам
do k = 1, m
if (a[k] < c) then
a[k] = 1
endif
enddo
do k = 1, m
if (a[k-1] < c) then
a[k] = 1
endif
enddo
Физический факультет МГУ им М.В.Ломоносова

Проектирование коммуникаций
Локальные
Глобальные
Структурированные
Неструктурированные
Статические
Динамические
Синхронные
Асинхронные
Физический факультет МГУ им М.В.Ломоносова

Рекомендации по проектированию коммуникаций
Количество коммуникаций у подзадач должно быть примерно одинаковым
Желательно использовать локальные коммуникации
Коммуникации должны быть , по возможности, параллельными
Физический факультет МГУ им М.В.Ломоносова

Тупиковые ситуации
Физический факультет МГУ им М.В.Ломоносова

Реализация обмена сообщениями
MPI (Message Passing Interface)
PVM (Parallel Virtual Machine)
RPC (Remote Procedure Control)
CORBA (Common Object Request Broker Architecture)
DCOM (Distributed Component Object Model)
Физический факультет МГУ им М.В.Ломоносова

Укрупнение
Физический факультет МГУ им М.В.Ломоносова

Укрупнение
Снижение затрат на коммуникации
При необходимом дублировании вычислений или данных не должно быть потерь в производительности или масштабируемости
Результирующие задачи должны иметь примерно одинаковую трудоёмкость
Сохранение масштабируемости
Сохранение возможности параллельного выполнения
Снижение стоимости и трудоёмкости разработки
Физический факультет МГУ им М.В.Ломоносова

Планирование вычислений
Стратегия управления хозяин/работник
Физический факультет МГУ им М.В.Ломоносова

Характеристики быстродействия
Факторы влияющие на производительность
Технология выполнения аппаратной части
Архитектура вычислительной системы
Методы управления ресурсами
Эффективность параллельного алгоритма
Особенности структуры данных
Эффективность языка программирования
Квалификация программиста
Эффективность транслятора

Последовательность действий
Разработка алгоритма
Предварительный анализ быстродействия программы
Оценка трудоёмкости и целесообразности разработки параллельной программы
Кодирование
Физический факультет МГУ им М.В.Ломоносова

Список литературы:
Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. -СПб.: Петербург, 2002.
Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. -СПб: BHV, 2002.
А.С.Антонов "Параллельное программирование с использованием технологии MPI", издательстве Московского университета 2004
А. А. Букатов, В. Н. Дацюк, А. И. Жегуло. Программирование многопроцессорных вычислительных систем. Ростов-на-Дону. Издательство ООО «ЦВВР», 2003, 208 с
Калиткин Н.Н. Численные методы. - М.: Наука, 1978. - 512 с
В. Д. Корнеев “Параллельное программирование в MPI”, издательство "Регулярная и хаотическая динамика" 2003 г., - 303 стр.
Грегори Р. Эндрюс “Основы многопоточного, параллельного и распределенного программирования”, издательство "Вильямс" 2003 г.- 512 стр.
Богачев К.Ю. “Основы параллельного программирования” издательство "Бином. Лаборатория знаний" 2003 г. - 342 стр.
Воеводин В.В. Параллельные структуры алгоритмов и программ. - М.: ОВМ АН СССР, 1987. - 148с.
http://parallel.ru
Физический факультет МГУ им М.В.Ломоносова