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

кластеров (l = 1).
Основной способ выполнения коммуникационных операций – пакетный

метод

1:
tн не зависит от объема данных,
tс не зависит от числа

пакетов

tпд = tн + mtк + tс

Ограничения не соответствуют действительности ?
Оценка времени (трудоемкости) неточна

2:
Учитывается
n - число пакетов, n = m/(Vmax – Vc)

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

данных для 2,3, … пакетов совмещена с пересылкой предшествующих пакетов.
Учитывается

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

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

для разделения на независимые (относительно) подзадачи.
2. Определение информационных взаимодействий между

подзадачами.
3. Масштабирование алгоритма с учетом числа CPU (укрупнение или детализация подзадач).
4. Распределение подзадач между CPU системы

Примечание. Это общий подход, независимо от типа вычислительной системы, исходной задачи и метода решения.

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

с распределенной памятью.
Операции доступа к общим переменным для МВС с общей памятью

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

объем сообщений

схема Блочная схема

решения уравнений в частных производных.
Имеет место параллелизм по данным ?
Разделение

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

разных запросов к БД
Одновременное выполнение разных алгоритмов для одних и

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

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

может потребовать изменения декомпозиции

(как правило, на соседних CPU).
Глобальные - обмен между всеми подзадачами.
Структурированные

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

выполняться только при готовности всех участников,
завершаются только по окончанию всех

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

количеству CPU

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

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

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

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

для МВС с распределенной памятью.
Не требуется, если
1) число подзадач =

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

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

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

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

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

на основе встроенных типов данных.

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

проблемы синхронизации.

Multi-Processing) —
открытый развивающийся стандарт для распараллеливания программ на языках С, С++, Fortran, 
включает

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

или нити (thread – нить, тред).
Для добавления в программу

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