- •Моделирование и анализ параллельных вычислений.
- •Модель вычислений в виде графа "операции – операнды".
- •Описание схемы выполнения параллельного алгоритма (модель: «операции – операнды»).
- •Определение времени выполнения параллельного алгоритма.
- •Правила разработки алгоритмов.
- •Программирование параллельных алгоритмов.
- •Технология mpi.
- •Введение в библиотеку mpich.
- •Структура параллельной программы с использованием mpi:
- •Передача/прием сообщений между отдельными процессами.
- •Использование модульной структуры.
- •Определение времени выполнения программ.
- •Контроль выполнения программ.
- •Передача данных от одного процесса всем процессам программы.
- •Передача данных от всех процессов одному процессу. Операция редукции.
- •Пример коллективного вызова (без обмена)- коллективная синхронизация.
- •Аварийное завершение параллельной программы
- •Оценка коммуникационных затрат для кластерных систем.
- •Режимы передачи данных mpi.
- •Организация неблокирующих обменов данными между процессами.
- •Одновременное выполнение передачи и приема.
- •Группа процессоров и коммутаторов.
- •Управление группами.
- •Управление коммуникаторами.
- •Показатели эффективности в параллельных алгоритмах.
- •Модельная задача – вычисление частных сумм последовательности числовых значений.
- •Последовательный алгоритм суммирования
- •Каскадная схема суммирования.
- •Каскадная схема с асимптотически ненулевой эффективностью.
- •Построение частичных сумм.
- •Оценка максимального параллелизма.
- •Закон Амдаля
- •Закон Густавсона-Барсиса
- •Анализ масштабируемости параллельных вычислений.
- •Верхняя граница времени выполнения параллельного алгоритма.
- •Факторы, влияющие на производительность, и способы ее повышения.
- •Принципы разработка параллельных алгоритмов.
- •Моделирование (использование моделей) при проектировании параллельных алгоритмов.
- •Этапы разработки параллельных алгоритмов.
- •Разделение вычислительной схемы на независимые части, на основе ее анализа.
- •Определение информационных зависимостей.
- •Масштабирование набора подзадач.
- •Распределение подзадач между процессорами.
- •Умножение матриц при ленточной схеме разделения данных.
- •Определение подзадач.
- •Выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельное решение систем линейных уравнений Алгоритм решения систем линейных уравнений методом Гаусса.
- •Итерация прямого хода алгоритма Гаусса
- •Построение параллельного алгоритма
- •Масштабирование и распределение подзадач по процессорам.
- •Анализ эффективности.
- •Параллельные методы сортировки
- •Принципы распараллеливания
- •Масштабирование параллельных вычислений
- •Пузырьковая сортировка
- •Алгоритм чет-нечетной перестановки
- •Определение подзадач и выделение информационных зависимостей
- •Масштабирование и распределение подзадач по процессорам
- •Анализ эффективности
- •Параллельные вычисления при решении задач на графах.
- •Программная реализация параллельного алгоритма Флойда:
- •Определение подзадач.
- •Анализ эффективности
- •Результаты вычислительных экспериментов для параллельного алгоритма Флойда
- •Работа pvm
- •Структура идентификатора td
- •Модель передачи сообщений
- •Настройка pvm
- •Структура каталога pvm:
- •Наиболее распространенные проблемы
- •Пример простейшей программы
- •Структура программы pvm.
- •Выводы по pvm:
- •Классификация вычислительных систем
- •Алгоритмы предварительного распределения данных (графы)
- •Режимы параллельных вычислений с общей памятью
- •Основные обозначения псевдокода
- •Распределение данных в erew
- •Параллельное программирование с использованием общей памяти
- •Многопоточное программирование
- •Спецификация posix Threads
- •Пример программы с использованием posix Threads
- •Механизмы синхронизации потоков
- •Среда Open mp
- •Основные правила:
- •Синхронизация
- •Обзор средств параллельного и распределенного программирования.
- •Литература:
Одновременное выполнение передачи и приема.
Одной из часто выполняемых форм информационного взаимодействия в параллельных программах является обмен данными между процессами, когда для продолжения вычислений процессам необходимо отправить данные одним процессам и в то же время получить сообщения от других. Простейший вариант этой ситуации состоит, например, в обмене данными между двумя процессами. Реализация таких обменов при помощи обычных парных операций передачи данных может быть неэффективна, кроме того, такая реализация должна гарантировать отсутствие тупиковых ситуаций, которые могут возникать, например, когда два процесса начинают передавать сообщения друг другу с использованием блокирующих функций передачи данных.
Достижение эффективного и гарантированного одновременного выполнения операций передачи и приема данных может быть обеспечено при помощи функции MPI:
int MPI_Sendrecv(void *sbuf,int scount,MPI_Datatype stype,
int dest, int stag, void *rbuf,int rcount,MPI_Datatype rtype,
int source,int rtag, MPI_Comm comm, MPI_Status *status),
где
sbuf, scount, stype, dest, stag — параметры передаваемого сообщения;
rbuf, rcount, rtype, source, rtag — параметры принимаемого сообщения;
comm — коммуникатор, в рамках которого выполняется передача данных;
status — структура данных с информацией о результате выполнения операции.
Как следует из описания, функция MPI_Sendrecv передает сообщение, описываемое параметрами ( sbuf, scount, stype, dest, stag ), процессу с рангом dest и принимает сообщение в буфер, определяемый параметрами ( rbuf, rcount, rtype, source, rtag ), от процесса с рангом source.
Группа процессоров и коммутаторов.
Процессы параллельной программы объединяются в группы. В группу могут входить все процессы параллельной программы ; с другой стороны, в группе может находиться только часть имеющихся процессов. Один и тот же процесс может принадлежать нескольким группам. Управление группами процессов предпринимается для создания на их основе коммуникаторов.
Под коммуникатором в MPI понимается специально создаваемый служебный объект, который объединяет в своем составе группу процессов и ряд дополнительных параметров (контекст), используемых при выполнении операций передачи данных. Парные операции передачи данных выполняются только для процессов, принадлежащих одному и тому же коммуникатору. Коллективные операции применяются одновременно для всех процессов коммуникатора. Создание коммуникаторов предпринимается для уменьшения области действия коллективных операций и для устранения взаимовлияния разных выполняемых частей параллельной программы. Важно еще раз подчеркнуть – коммуникационные операции, выполняемые с использованием разных коммуникаторов, являются независимыми и не влияют друг на друга.
Все имеющиеся в параллельной программе процессы входят в состав создаваемого по умолчанию коммуникатора с идентификатором MPI_COMM_WORLD.
Управление группами.
Группы процессов могут быть созданы только из уже существующих групп. В качестве исходной группы может быть использована группа, связанная с предопределенным коммуникатором MPI_COMM_WORLD. Также иногда может быть полезным коммуникатор MPI_COMM_SELF, определенный для каждого процесса параллельной программы и включающий только этот процесс.
Для получения группы, связанной с существующим коммуникатором, применяется функция:
int MPI_Comm_group(MPI_Comm comm, MPI_Group *group),
где
comm — коммуникатор;
group — группа, связанная с коммуникатором.
Далее, на основе существующих групп, могут быть созданы новые группы:
создание новой группы newgroup из существующей группы oldgroup, которая будет включать в себя n процессов — их ранги перечисляются в массиве ranks:
int MPI_Group_incl(MPI_Group oldgroup, int n, int *ranks,
MPI_Group *newgroup),
где
oldgroup — существующая группа;
n — число элементов в массиве ranks;
ranks — массив рангов процессов, которые будут включены в новую группу;
newgroup — созданная группа;
создание новой группы newgroup из группы oldgroup, которая будет включать в себя n процессов, чьи ранги не совпадают с рангами, перечисленными в массиве ranks:
int MPI_Group_excl(MPI_Group oldgroup, int n, int *ranks,
MPI_Group *newgroup),
где
oldgroup — существующая группа;
n — число элементов в массиве ranks;
ranks — массив рангов процессов, которые будут исключены из новой группы;
newgroup — созданная группа.
Для получения новых групп над имеющимися группами процессов могут быть выполнены операции объединения, пересечения и разности:
создание новой группы newgroup как объединения групп group1 и group2:
int MPI_Group_union(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup),
где
group1 — первая группа;
group2 — вторая группа;
newgroup — объединение групп;
создание новой группы newgroup как пересечения групп group1 и group2:
int MPI_Group_intersection(MPI_Group group1, MPI_Group group2,
MPI_Group *newgroup),
где
group1 — первая группа;
group2 — вторая группа;
newgroup — пересечение групп;
создание новой группы newgroup как разности групп group1 и group2:
int MPI_Group_difference(MPI_Group group1, MPI_Group group2,
MPI_Group *newgroup),
где
group1 — первая группа;
group2 — вторая группа;
newgroup — разность групп;
При конструировании групп может оказаться полезной специальная пустая группа MPI_COMM_EMPTY.
Ряд функций MPI обеспечивает получение информации о группе процессов:
получение количества процессов в группе:
int MPI_Group_size(MPI_Group group, int *size),
где
group — группа;
size — число процессов в группе;
получение ранга текущего процесса в группе:
int MPI_Group_rank(MPI_Group group, int *rank),
где
group — группа;
rank — ранг процесса в группе.
после завершения использования группа должна быть удалена:
int MPI_Group_free(MPI_Group *group),
где
group — группа, подлежащая удалению
(выполнение данной операции не затрагивает коммуникаторы, в которых используется удаляемая группа).