- •Моделирование и анализ параллельных вычислений.
- •Модель вычислений в виде графа "операции – операнды".
- •Описание схемы выполнения параллельного алгоритма (модель: «операции – операнды»).
- •Определение времени выполнения параллельного алгоритма.
- •Правила разработки алгоритмов.
- •Программирование параллельных алгоритмов.
- •Технология mpi.
- •Введение в библиотеку mpich.
- •Структура параллельной программы с использованием mpi:
- •Передача/прием сообщений между отдельными процессами.
- •Использование модульной структуры.
- •Определение времени выполнения программ.
- •Контроль выполнения программ.
- •Передача данных от одного процесса всем процессам программы.
- •Передача данных от всех процессов одному процессу. Операция редукции.
- •Пример коллективного вызова (без обмена)- коллективная синхронизация.
- •Аварийное завершение параллельной программы
- •Оценка коммуникационных затрат для кластерных систем.
- •Режимы передачи данных mpi.
- •Организация неблокирующих обменов данными между процессами.
- •Одновременное выполнение передачи и приема.
- •Группа процессоров и коммутаторов.
- •Управление группами.
- •Управление коммуникаторами.
- •Показатели эффективности в параллельных алгоритмах.
- •Модельная задача – вычисление частных сумм последовательности числовых значений.
- •Последовательный алгоритм суммирования
- •Каскадная схема суммирования.
- •Каскадная схема с асимптотически ненулевой эффективностью.
- •Построение частичных сумм.
- •Оценка максимального параллелизма.
- •Закон Амдаля
- •Закон Густавсона-Барсиса
- •Анализ масштабируемости параллельных вычислений.
- •Верхняя граница времени выполнения параллельного алгоритма.
- •Факторы, влияющие на производительность, и способы ее повышения.
- •Принципы разработка параллельных алгоритмов.
- •Моделирование (использование моделей) при проектировании параллельных алгоритмов.
- •Этапы разработки параллельных алгоритмов.
- •Разделение вычислительной схемы на независимые части, на основе ее анализа.
- •Определение информационных зависимостей.
- •Масштабирование набора подзадач.
- •Распределение подзадач между процессорами.
- •Умножение матриц при ленточной схеме разделения данных.
- •Определение подзадач.
- •Выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельное решение систем линейных уравнений Алгоритм решения систем линейных уравнений методом Гаусса.
- •Итерация прямого хода алгоритма Гаусса
- •Построение параллельного алгоритма
- •Масштабирование и распределение подзадач по процессорам.
- •Анализ эффективности.
- •Параллельные методы сортировки
- •Принципы распараллеливания
- •Масштабирование параллельных вычислений
- •Пузырьковая сортировка
- •Алгоритм чет-нечетной перестановки
- •Определение подзадач и выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельные вычисления при решении задач на графах.
- •Программная реализация параллельного алгоритма Флойда:
- •Определение подзадач.
- •Анализ эффективности
- •Результаты вычислительных экспериментов для параллельного алгоритма Флойда
- •Работа pvm
- •Структура идентификатора td
- •Модель передачи сообщений
- •Настройка pvm
- •Структура каталога pvm:
- •Наиболее распространенные проблемы
- •Пример простейшей программы
- •Структура программы pvm.
- •Выводы по pvm:
- •Классификация вычислительных систем
- •Алгоритмы предварительного распределения данных (графы)
- •Режимы параллельных вычислений с общей памятью
- •Основные обозначения псевдокода
- •Распределение данных в erew
- •Параллельное программирование с использованием общей памяти
- •Многопоточное программирование
- •Спецификация posix Threads
- •Пример программы с использованием posix Threads
- •Механизмы синхронизации потоков
- •Среда Open mp
- •Основные правила:
- •Синхронизация
- •Обзор средств параллельного и распределенного программирования.
- •Литература:
Определение времени выполнения параллельного алгоритма.
Вычислительная схема алгоритма G совместно с расписанием Hp может рассматриваться как модель параллельного алгоритма Ap(G,Hp), исполняемого с использованием p процессоров.
Время выполнения параллельного алгоритма определяется максимальным значением времени, применяемым в расписании
Tp(G, Hp) =
Для выбранной схемы вычислений желательно использование расписания, обеспечивающего минимальное время исполнения алгоритма:
Tp(G) =
Уменьшение времени выполнения может быть обеспечено и путем подбора наилучшей вычислительной схемы:
Tp =
Все оценки могут быть получены для разного числа процессов.
Для анализа максимально возможного параллелизма можно определить оценку наиболее быстрого исполнения алгоритма:
T∞ = – минимально возможное время выполнения параллельного алгоритма при использовании неограниченного количества процессоров.
Оценка T1 определяет время выполнения алгоритма при использовании одного процессора и представляет, тем самым, время выполнения последовательного варианта алгоритма решения задачи. Построение подобной оценки является важной задачей при анализе параллельных алгоритмов, поскольку она необходима для определения эффекта использования параллелизма (ускорения времени решения задачи).
T1 = - при оптимальном выборе модели.
Время решения различных задач на одном процессоре различается.
T1* = min T1 – наиболее быстрый из последних алгоритмов, где операция минимума берется по множеству всех возможных последовательных алгоритмов решения данной задачи.
Обозначим: d(G) — диаметр (длина максимального пути) графа.
Теорема 1.
Минимально возможное время выполнения параллельного алгоритма определяется длиной максимального пути вычислительной схемы алгоритма, т.е.
T∞ (G) = d (G)
Теорема 2.
Пусть существует вершина j, которая является вершиной вывода, такая, что в нее существует путь (i⟹j) из любой вершины i - вершины ввода.При этом число входных дуг, для каждой вершины не превышает двух. Тогда будет справедлива оценка:
T∞ (G)≥
Где n - число вершин ввода.
Теорема 3.
При уменьшении числа используемых процессоров время выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров:
q=cp , где c<1 (>0) ⟹ Tp cTq
Теорема 4.
Для числа процессоров справедлива следующая оценка:
Tp < (T∞ + T1/p)
Теорема 5.
Времени выполнения алгоритма, которое сопоставимо с минимально возможным временем T∞, можно достичь при количестве процессоров порядка p ~T1/T∞, а именно:
Если p ≥ T1/ T∞, то Tp 2T∞.
При меньшем количестве процессоров время выполнения алгоритма не может превышать более чем в 2 раза наилучшее время вычислений при имеющемся числе процессоров:
Если p< T1/ T∞, то T1/p≤ Tp ≤2 T1/p
Правила разработки алгоритмов.
Схема графа должна быть выбрана таким образом, чтобы его диаметр был бы минимальным.
d(G) min
Целесообразно выбирать число процессоров следующим образом:
p T1/T∞.
Для времени выполнения алгоритма с использованием p процессоров выполняются ограничения рассмотренных соотношений.
Лекция 2