Технологии решения сложных
задач на кластерных
вычислительных системах с
использованием средств MPI
5/22/19
Москва, МЭИ
1
Программа обучения
Решение инженерных задач на вычислительных системах
Основные понятия вычислительной математики
Основные концепции и инструменты программирования
Введение в C/С++
Параллельные технологии решения сложных задач
Понятие параллелизма в программировании и формы его представления.
Использование MPI
Стандарт MPI и его реализации.
Компиляция и запуск MPI программ в Linux и Windows.
Синхронные и асинхронные операции обмена сообщениями MPI.
Коллективные операции MPI обмена сообщениями.
Определяемые пользователем типы данных.
Использование топологий в MPI программах.
Многопоточное программирование в MPI
Вычислительные задачи и их реализация на MPI
Отладка, оптимизация MPI программ
Вспомогательные инструменты при работе с MPI
– Jump shot
– Intel Trace Analyzer
Общие подходы к оптимизации программ.
5/22/19
Москва, МЭИ
2
Введение: Моделирование как методология
• Подход «cut-and-try» устарел
• Современная наука:
Система д/у, представляющая
непрерывную аппроксимацию
микроскопической системы или
дискретная модель
Гб данных
Анализ
Численный
эксперимент
1.Построить модель (выбрать представление)
2. Разработать алгоритм
3. Эффективно выполнить вычисления
4. Оценить погрешность
5. Выполнить визуализацию
• Появляются дисциплины, продвижение в которых возможно только
лишь с помощью моделирования и использования масштабных
Вычисливычислений:
Computer
тельная
– Нанотехнологии
– Микробиология: поиск новых лекарств
– Науки о материалах
5/22/19
Москва, МЭИ
математика
science
Моделиро
вание
3
Введение: Языки программирования
• Сила 0 и 1
c=a+b
01011001010001000111010101000100
01011001011100100010100101000011
00111010101000100111010100100101
01011101010101010101010000111101
C#
Java
Абстракции
C++
Pascal VB
C
asm
Fortran
Простота
Точность
5/22/19
Москва, МЭИ
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
знак мантисса показатель
5/22/19
Москва, МЭИ
5
Параллелизм в задачах
Четыре шага при создании параллельных программ:
1.
Разделение
• Разделение данных и задач на фрагменты
2. Взаимодействие
• Распределение данных между задачами и
установление зависимостей
3. Агломерация
• Задачи группируются для повышения
эффективности использования ресурсов
4. Распределение
• Распределение задач по «вычислителям»
«Designing and Building Parallel Programs», Ян Фостер
5/22/19
6
Москва, МЭИ
6
Параллельное программирование
CPU
CPU
Memory
Memory
CPU
Network
CPU
Memory
5/22/19
CPU
CPU
Bus
CPU
Memory
Memory
Потоки (Threads)
Модель передачи сообщений
•
•
CPU
Множество процессов
Распределение данных с
помощью посылки сообщений
(MPI)
•
•
Москва, МЭИ
Один процесс
– Конкурентное выполнение
Разделяемые данные и
ресурсы (Потоки ОС, OpenMP)
7
Параллельное программирование
Задача
• Разделение
– Разделить задачу на фрагменты
(подзадачи)
• Взаимодействие
– Определить тип и способ
взаимодействия
Подзадачи
Связи
• Агломерация
– Группировать фрагменты задачи
• Распределение
Группировка
подзадач
– Распределить группы задач по
процессорам
Параллельная
программа
5/22/19
Москва, МЭИ
8
Параллельное программирование
Разделение.
Выделить как можно больше параллельных фрагментов
•Независимые вычисления и/или данные
•Количество элементарных действий должно быть
максимальным
Методы декомпозиции:
•Функциональная декомпозиция
•Декомпозиция по данным
Где нет параллелизма?
Подпрограммы, обрабатывающие объекты, имеющие «состояние»
•Выделение памяти
•Ввод-вывод из файлов
Циклы с зависимостями по данным
•Переменная записывается в одной итерации, а считывается в другой –
простой проверкой может быть инвертирование цикла
5/22/19
Москва, МЭИ
9
Параллельное программирование
Atmosphere Model
Функциональная
декомпозиция
Hydrology
Model
– Анализируется процесс
вычислений
Ocean
Model
Land Surface
Model
Декомпозиция по
данным
– Анализируются массивные
или часто используемые
данные
– Одна и та же операция
применяется ко всем
данным
5/22/19
Москва, МЭИ
10
Параллельное программирование
Взаимодействие
Определить тип и способ взаимодействия подзадач, определить,
какие данные должны быть разделяемыми.
Точка-точка
•одна подзадача передает данные другой
Коллективное использование
•группа подзадач работает с одной копией данных
Агломерация
Группировка элементарных действий производится для того,
чтобы:
•повысить производительность и зернистость
•локализовать связи
•сохранить масштабируемость
•упростить программирование
5/22/19
Москва, МЭИ
11
Параллельное программирование
ГОНКИ ДАННЫХ!
Обычно проявляют себя в случаях, когда множество
параллельно выполняющихся задач обращаются к общим
данным.
Порядок выполнения мог подразумеваться
программистом, но не гарантируется в ходе вычислений.
Сложно предугадать
•Недетерминированное выполнение
•В процессе отладки могут не проявляться
5/22/19
Москва, МЭИ
12
Ускорение
Коэффициент ускорения при параллельном выполнении
программ при ее выполнении на N процессорах определяется
следующим образом:
1
k
1 α
α
N
В этой формуле
α – участок программы, выполняющийся полностью
последовательно
1 – α - полностью параллельный участок программы
N – количество «вычислителей»
Ясно, что при N → ∞, K → 1 / α
5/22/19
Москва, МЭИ
13
Закон Амдала
Также часто используется другая формулировка
коэффициента ускорения в форме закона Амдала:
Т – время выполнения последовательного варианта
программы,
P – участок программы, который можно
распараллелить,
1 – P – участок программы, который распараллелить
нельзя,
N – количество «вычислителей»
parallel (1 ) serial
N
И коэффициент ускорения будет
serialопределяться следующим
k
образом:
parallel
5/22/19
Москва, МЭИ
14
