Технологии решения сложных задач с использованием MPI

Посмотреть архив целиком
Технологии решения сложных
задач на кластерных
вычислительных системах с
использованием средств MPI

7/22/16

Москва, МЭИ

1

Программа обучения
Решение инженерных задач на вычислительных системах
Основные понятия вычислительной математики
Основные концепции и инструменты программирования
Введение в C/С++

Параллельные технологии решения сложных задач
Понятие параллелизма в программировании и формы его представления.

Использование MPI
Стандарт MPI и его реализации.
Компиляция и запуск MPI программ в Linux и Windows.
Синхронные и асинхронные операции обмена сообщениями MPI.
Коллективные операции MPI обмена сообщениями.
Определяемые пользователем типы данных.
Использование топологий в MPI программах.
Многопоточное программирование в MPI

Вычислительные задачи и их реализация на MPI
Отладка, оптимизация MPI программ
Вспомогательные инструменты при работе с MPI
– Jump shot
– Intel Trace Analyzer
Общие подходы к оптимизации программ.

7/22/16

Москва, МЭИ

2

Введение: Моделирование как методология

• Подход «cut-and-try» устарел
• Современная
наука:
Система д/у,
представляющая
непрерывную
Гб данных
Численны
аппроксимацию
й
микроскопической
экспериме
системы или дискретная
нт
модель
1.Построить модель (выбрать представление)
2. Разработать алгоритм
3. Эффективно выполнить вычисления
4. Оценить погрешность
5. Выполнить визуализацию

Анализ

• Появляются дисциплины, продвижение в которых
возможно только лишь с помощью моделирования и
Вычисли
использования масштабных вычислений:
-тельная Compute
– Нанотехнологии
– Микробиология: поиск новых лекарств
– Науки о материалах

7/22/16

Москва, МЭИ

математи
ка

r science

Моделир
ование

3

Введение: Языки программирования

• Сила 0 и 1
c=a+b

?

0101100101000100011101010
1000100
0101100101110010001010010
1000011
0011101010100010011101010
0100101
Абстракции
C#
0101110101010101010101000
Java
0111101
C++
C

asm

Fortran

Точность

7/22/16

Москва, МЭИ

Pasc VB
al

Просто
та

4

Основные понятия вычислительной математики






Вектор aT=(a1,a2,…,an)
Матрица A (m x n), A[i,j]
Функция
O(f(n))

Округление!
Системы счисления
12610= 1 ? 102 + 2 ? 101 + 6 ? 100
Двоичная система:
011111102 = 0? 27 + 1 ? 26 + 1 ? 25 + 1 ? 24 + 1?
23 + 1 ? 22 + 1 ? 21 + 0 ? 20
Числа с плавающей точкой:
+
.126
?
103
знак мантисса показатель
7/22/16

Москва, МЭИ

5

Параллелизм в задачах
Четыре шага при создании параллельных программ:
1.

Разделение
• Разделение данных и задач на фрагменты
2. Взаимодействие
• Распределение данных между задачами и
установление зависимостей
3. Агломерация
• Задачи группируются для повышения
эффективности использования ресурсов
4. Распределение
• Распределение задач по «вычислителям»

«Designing and Building Parallel Programs», Ян Фостер
7/22/16

Москва, МЭИ

6

6

Параллельное программирование

CPU

CPU

Memory

Memory

CPU

Network

CPU

7/22/16

CP
U

Memory

Memory

Модель передачи
сообщений



CPU

Bus
CPU

Memory

CP
U

Множество процессов
Распределение данных с
помощью посылки
сообщений (MPI)

Москва, МЭИ

Потоки (Threads)



Один процесс
– Конкурентное
выполнение
Разделяемые данные и
ресурсы (Потоки ОС,
OpenMP)

7

Параллельное программирование

Задача

• Разделение

– Разделить задачу на
фрагменты (подзадачи)

• Взаимодействие
– Определить тип и способ
взаимодействия

Подзадачи
Связи

• Агломерация

– Группировать фрагменты
задачи

• Распределение
– Распределить группы
задач по процессорам

7/22/16

Москва, МЭИ

Группировка
подзадач
Параллельная 
программа

8

Параллельное программирование
Разделение.
Выделить как можно больше параллельных фрагментов
•Независимые вычисления и/или данные
•Количество элементарных действий должно быть
максимальным
Методы декомпозиции:
•Функциональная декомпозиция
•Декомпозиция по данным

Где нет параллелизма?
Подпрограммы, обрабатывающие объекты, имеющие «состояние»
•Выделение памяти
•Ввод-вывод из файлов
Циклы с зависимостями по данным
•Переменная записывается в одной итерации, а считывается в
другой – простой проверкой может быть инвертирование цикла

7/22/16

Москва, МЭИ

9

Параллельное программирование
Atmosphere Model

Функциональная
декомпозиция

– Анализируется процесс
вычислений

Hydrology
Model

Ocean
Model

Land Surface
Model

? Декомпозиция по
данным
– Анализируются массивные
или часто используемые
данные
– Одна и та же операция
применяется ко всем
данным
7/22/16

Москва, МЭИ

10

Параллельное программирование

Взаимодействие
Определить тип и способ взаимодействия подзадач, определить,
какие данные должны быть разделяемыми.
Точка-точка
•одна подзадача передает данные другой
Коллективное использование
•группа подзадач работает с одной копией данных

Агломерация
Группировка элементарных действий производится для того,
чтобы:
•повысить производительность и зернистость
•локализовать связи
•сохранить масштабируемость
•упростить программирование

7/22/16

Москва, МЭИ

11

Параллельное программирование
ГОНКИ ДАННЫХ!
Обычно проявляют себя в случаях, когда множество
параллельно выполняющихся задач обращаются к общим
данным.
Порядок выполнения мог подразумеваться
программистом, но не гарантируется в ходе вычислений.
Сложно предугадать
•Недетерминированное выполнение
•В процессе отладки могут не проявляться

7/22/16

Москва, МЭИ

12

Ускорение
Коэффициент ускорения при параллельном выполнении
программ при ее выполнении на N процессорах определяется
следующим образом:

1
k ?
1? ?
??
N
В этой формуле
? – участок программы, выполняющийся полностью
последовательно
1 – ? - полностью параллельный участок программы
N – количество «вычислителей»

Ясно, что при N ? ?, K ? 1 / ?

7/22/16

Москва, МЭИ

13

Закон Амдала
Также часто используется другая формулировка
коэффициента ускорения в форме закона Амдала:
Т – время выполнения последовательного варианта
программы,
P – участок программы, который можно
распараллелить,
1 – P – участок программы, который распараллелить
нельзя,
N – количество «вычислителей»

??
?
?parallel ?? (1 ? ?) ? ? ?serial
N?
?

И коэффициент ускорения будет
?serialопределяться следующим
k?
образом:

?parallel

7/22/16

Москва, МЭИ

14






Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.