Моделирование и анализ параллельных вычислений.

Сентябрь 3, 2022

Главная
Алгебра
Моделирование и анализ параллельных вычислений.

Содержание

2. Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 1: tн не зависит от объема
3. Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 2: Учитывается n - число пакетов,
4. Оценка трудоемкости операции передачи данных между 2 узлами кластера Предполагается Подготовка данных для 2,3, … пакетов
5. Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 2 – итоговое соотношение
6. Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 3 (упрощение подхода 1) – модель
7. Этапы разработки параллельных алгоритмов (распараллеливания) 1. Анализ общей схемы вычислений - для разделения на независимые (относительно)
8. Дополнительные предположения Равномерность загрузки всех CPU (балансировка). Минимизация коммуникационных взаимодействий между подзадачами. Возможность пересмотра шагов после
9. Этап 1 разработки параллельных алгоритмов 1. Разделение вычислений на независимые подзадачи Требования к подзадачам: Равные объемы
10. Два основных типа вычислительных схем, основанных на разделении данных: Ленточная схема Блочная схема
11. Сфера применимости – однотипная обработка большого набора данных: Матричные вычисления Численные методы решения уравнений в частных
12. Сетки, или решетки
13. Выполнение разных операций над одним набором данных – функциональный параллелизм Обработка разных запросов к БД Одновременное
14. Этап 2 разработки параллельных алгоритмов 2. Выделение информационных зависимостей Взаимосвязан с этапом 1: Выделение подзадач должно
15. Формы информационного взаимодействия Схемы передачи данных: Локальные – обмен для части подзадач (как правило, на соседних
16. Формы информационного взаимодействия Схемы передачи данных: Синхронные – операции передачи данных начинают выполняться только при готовности
17. Этап 3 разработки параллельных алгоритмов 3. Масштабирование Необходимо, если число подзадач ≠ количеству CPU Типы масштабирования:
18. Агрегация Укрупнение вычислений для уменьшения числа подзадач. В результате должно соблюдаться (см. этап 1) : Одинаковая
19. Декомпозиция Детализация вычислений (увеличение числа подзадач) для загрузки всех доступных CPU. Декомпозиция выполняется до базовых задач
20. Этап 4 разработки параллельных алгоритмов 4. Распределение подзадач между CPU. Необходимо для МВС с распределенной памятью.
21. Практические рекомендации Анализируем задачу для выделения подзадач, которые могут выполняться одновременно Изменяем структуру задачи для эффективного
22. Технологии параллельного программирования В основе может быть: Язык параллельного программирования. Прикладной программный интерфейс (API), реализованный с
23. Примеры технологий ПП OpenMP: директивы компилятора для простого параллельного программирования. MPI: библиотечные подпрограммы для реализации высокоэффективной
24. 3. Основы технологии OpenMP. Модель «fork-join». Классификация переменных. Основные директивы и их опции. Распараллеливание по данным
25. Технология разработки параллельных программ для МВС с общей памятью (OpenMP) OpenMP (Open Multi-Processing) — открытый развивающийся
26. Модель программирования OpenMP Разветвление-объединение (fork-join) Работа программы начинается с одного (корневого) потока, или нити (thread –
28. Скачать презентацию

Слайд 2

Оценка трудоемкости операции передачи данных между 2 узлами кластера
Подход 1:
tн

не зависит от объема данных,
tс не зависит от числа пакетов
tпд = tн + mtк + tс
Ограничения не соответствуют действительности ?
Оценка времени (трудоемкости) неточна

Слайд 3

Оценка трудоемкости операции передачи данных между 2 узлами кластера
Подход 2:
Учитывается

n - число пакетов, n = m/(Vmax – Vc)
Vc - объем служебных данных в каждом пакете,
Vmax - максимально возможный для сети размер пакета,
tнач0 – аппаратная (сетевая) задержка (латентность),
tнач1 – время подготовки к передаче в сети 1 байта.

Слайд 4

Оценка трудоемкости операции передачи данных между 2 узлами кластера
Предполагается
Подготовка данных

для 2,3, … пакетов совмещена с пересылкой предшествующих пакетов.
Учитывается увеличение объема передаваемой информации за счет добавления служебных данных (заголовков пакетов)

Слайд 5

Оценка трудоемкости операции передачи данных между 2 узлами кластера
Подход 2

– итоговое соотношение

Слайд 6

Оценка трудоемкости операции передачи данных между 2 узлами кластера
Подход 3

(упрощение подхода 1) – модель Хокни (R.W. Hocney, 1994) – используется для грубых оценок трудоемкости
tпд = tн + mtк = tн + m/R
Оценки через вычислительные эксперименты на кластере:
tн - время передачи сообщения длины 0 для подходов 1 и 3,
tнач0 , tнач1 для подхода 2 - можно оценить через аппроксимацию tпд - времени передачи сообщений размером от 0 до Vmax
R = max (tпд / m) при варьировании m

Слайд 7

Этапы разработки параллельных алгоритмов (распараллеливания)
1. Анализ общей схемы вычислений - для

разделения на независимые (относительно) подзадачи.
2. Определение информационных взаимодействий между подзадачами.
3. Масштабирование алгоритма с учетом числа CPU (укрупнение или детализация подзадач).
4. Распределение подзадач между CPU системы
Примечание. Это общий подход, независимо от типа вычислительной системы, исходной задачи и метода решения.

Слайд 8

Дополнительные предположения
Равномерность загрузки всех CPU (балансировка).
Минимизация коммуникационных взаимодействий между подзадачами.
Возможность пересмотра

шагов после анализа показателей производительности.
Информационные взаимодействия:
Передача сообщений для МВС с распределенной памятью.
Операции доступа к общим переменным для МВС с общей памятью

Слайд 9

Этап 1 разработки параллельных алгоритмов
1. Разделение вычислений на независимые подзадачи
Требования

к подзадачам:
Равные объемы вычислений
Минимум информационных зависимостей
Меньше передач данных
Больше объем сообщений

Слайд 10

Два основных типа вычислительных схем, основанных на разделении данных:
Ленточная схема Блочная

схема

Слайд 11

Сфера применимости – однотипная обработка большого набора данных:
Матричные вычисления
Численные методы решения

уравнений в частных производных.
Имеет место параллелизм по данным ?
Разделение на подзадачи = разделение данных.
Возможны 1,2,3D наборы подзадач с информационными связями между ближайшими соседями – сетки, или решетки.

Слайд 12

Сетки, или решетки

Слайд 13

Выполнение разных операций над одним набором данных – функциональный параллелизм
Обработка разных

запросов к БД
Одновременное выполнение разных алгоритмов для одних и тех же данных
Функциональная декомпозиция м.б. использована для конвейерной обработки данных:
Ввод
Обработка
Сохранение

Слайд 14

Этап 2 разработки параллельных алгоритмов
2. Выделение информационных зависимостей
Взаимосвязан с этапом 1:
Выделение

подзадач должно учитывать возможные информационные связи
Анализ объема информационных обменов может потребовать изменения декомпозиции

Слайд 15

Формы информационного взаимодействия
Схемы передачи данных:
Локальные – обмен для части подзадач (как

правило, на соседних CPU).
Глобальные - обмен между всеми подзадачами.
Структурированные – стандартные регулярные схемы (кольцо, решетка и т.д.).
Произвольные .
Статические – фиксируются при проектировании программы вычислений
Динамические – определяются во время выполнения программы (run-time)

Слайд 16

Формы информационного взаимодействия
Схемы передачи данных:
Синхронные – операции передачи данных
начинают выполняться

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

Слайд 17

Этап 3 разработки параллельных алгоритмов
3. Масштабирование
Необходимо, если число подзадач ≠ количеству

CPU
Типы масштабирования:
Агрегация
Декомпозиция

Слайд 18

Агрегация
Укрупнение вычислений для уменьшения числа подзадач.
В результате должно соблюдаться (см. этап

1) :
Одинаковая вычислительная сложность подзадач.
Минимально возможный уровень объема и интенсивности информационных взаимодействий между подзадачами
?
В первую очередь объединяют коммуникационно трудоемкие подзадачи

Слайд 19

Декомпозиция
Детализация вычислений (увеличение числа подзадач) для загрузки всех доступных CPU.
Декомпозиция выполняется

до базовых задач – с известными параллельными алгоритмами решения

Слайд 20

Этап 4 разработки параллельных алгоритмов
4. Распределение подзадач между CPU.
Необходимо для

МВС с распределенной памятью.
Не требуется, если
1) число подзадач = количеству CPU
2) все CPU связаны напрямую (полный граф)
3) система с общей памятью – распределение выполняется автоматически ОС.

Слайд 21

Практические рекомендации
Анализируем задачу для выделения подзадач, которые могут выполняться одновременно
Изменяем структуру

задачи для эффективного выполнения подзадач:
найти зависимости между подзадачами,
организовать исходный код для эффективного управления.
Реализуем параллельный алгоритм в исходном коде с помощью технологий параллельного программирования

Слайд 22

Технологии параллельного программирования
В основе может быть:
Язык параллельного программирования.
Прикладной программный интерфейс (API),

реализованный с помощью библиотечного интерфейса.
Расширение языка последовательного программирования

Слайд 23

Примеры технологий ПП
OpenMP: директивы компилятора для простого параллельного программирования.
MPI: библиотечные подпрограммы

для реализации высокоэффективной переносимости.
Java: параллельность заложена в языке программирования на основе встроенных типов данных.

Слайд 24

3. Основы технологии OpenMP.
Модель «fork-join».
Классификация переменных.
Основные директивы и

их опции.
Распараллеливание по данным и по операциям.
Решение проблемы синхронизации.

Слайд 25

Технология разработки параллельных программ для МВС с общей памятью (OpenMP)
OpenMP (Open Multi-Processing) —

открытый развивающийся стандарт для распараллеливания программ на языках С, С++, Fortran,
включает описание
директив компилятора,
библиотечных процедур,
переменных ОС,
для программирования многопоточных приложений для МВС с общей памятью (имеется версия и для кластеров).
Наиболее популярная задача OpenMP — написание программ, ориентированных на циклы

Слайд 26

Модель программирования OpenMP
Разветвление-объединение (fork-join)
Работа программы начинается с одного (корневого) потока, или

нити (thread – нить, тред).
Для добавления в программу параллелизма выполняется разветвление на несколько потоков, чтобы создать группу потоков.
Потоки группы выполняются параллельно в рамках фрагмента кода, т.наз. параллельного участка.
В конце параллельного участка все потоки заканчивают свою работу и снова объединяются вместе.
После этого корневой поток продолжает выполняться до тех пор, пока не начнется следующий параллельный участок (или не наступит конец программы).

Моделирование и анализ параллельных вычислений.

Содержание

Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 1:tн

Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 2:Учитывается

Оценка трудоемкости операции передачи данных между 2 узлами кластера ПредполагаетсяПодготовка данных

Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 2

Оценка трудоемкости операции передачи данных между 2 узлами кластера Подход 3

Этапы разработки параллельных алгоритмов (распараллеливания)1. Анализ общей схемы вычислений - для

Этап 1 разработки параллельных алгоритмов 1. Разделение вычислений на независимые подзадачиТребования

Два основных типа вычислительных схем, основанных на разделении данных:Ленточная схема Блочная

Сфера применимости – однотипная обработка большого набора данных:Матричные вычисленияЧисленные методы решения

Сетки, или решетки

Выполнение разных операций над одним набором данных – функциональный параллелизмОбработка разных

Этап 2 разработки параллельных алгоритмов2. Выделение информационных зависимостейВзаимосвязан с этапом 1:Выделение

Формы информационного взаимодействияСхемы передачи данных:Локальные – обмен для части подзадач (как

Формы информационного взаимодействияСхемы передачи данных:Синхронные – операции передачи данных начинают выполняться

Этап 3 разработки параллельных алгоритмов3. МасштабированиеНеобходимо, если число подзадач ≠ количеству

АгрегацияУкрупнение вычислений для уменьшения числа подзадач.В результате должно соблюдаться (см. этап

ДекомпозицияДетализация вычислений (увеличение числа подзадач) для загрузки всех доступных CPU.Декомпозиция выполняется

Этап 4 разработки параллельных алгоритмов4. Распределение подзадач между CPU. Необходимо для

Практические рекомендацииАнализируем задачу для выделения подзадач, которые могут выполняться одновременноИзменяем структуру

Технологии параллельного программированияВ основе может быть:Язык параллельного программирования.Прикладной программный интерфейс (API),

Примеры технологий ППOpenMP: директивы компилятора для простого параллельного программирования.MPI: библиотечные подпрограммы

3. Основы технологии OpenMP. Модель «fork-join». Классификация переменных. Основные директивы и

Технология разработки параллельных программ для МВС с общей памятью (OpenMP)OpenMP (Open Multi-Processing) —

Модель программирования OpenMPРазветвление-объединение (fork-join)Работа программы начинается с одного (корневого) потока, или

Похожие презентации