2016 Ответы на экзаменационные вопросы, страница 2

Процессорные партиции

• Подмножества вычислительных узлов, выделяемых задаче

• Каждой задаче выделяется своя партиция

• Загрузка задачи на исполнение производится независимо от других задач

• Размер партиции определяется кратным 32

• (на текущий момент на системе ВМК - кратным 128 )

• Для партиций размером кратным 512 поддерживается топология тора

1. Последовательная и параллельная сложность алгоритмов, информационный граф и ресурс параллелизма алгоритмов.

Последовательная сложность (serial complexity) алгоритма - число операций, которые нужно выполнить при его последовательном исполнении.

Параллельная сложность (parallel complexity) алгоритма - число шагов, за которое можно выполнить данный алгоритм в предположении доступности неограниченного числа необходимых процессоров (функциональных устройств, вычислительных узлов, ядер и т.п.). Параллельная сложность алгоритма понимается как высота канонической ярусно-параллельной формы.

Граф алгоритма (algorithm graph) - это ориентированный ациклический мультиграф, вершины которого соответствуют операциям алгоритма, а дуги - передаче данных между ними. Вершины графа алгоритма могут соединяться несколькими дугами, в частности когда в качестве разных аргументов одной и той же операции используется одна и та же величина. Граф алгоритма почти всегда является параметризованным графом. В частности, его вид часто зависит от входных данных.

Граф алгоритма используется как удобное представление алгоритма при исследовании его структуры, ресурса параллелизма, а также других свойств. Его можно рассматривать как параметризованную информационную историю. Он сохраняет её информативность, при это обладая компактностью за счёт параметризации. Разработана методика построения графа алгоритма по исходному тексту программ.

Ресурс параллелизма – что можно распараллелить. Желательно эффективно.

Разложение Холецкого:

Масштабируемость

Эффективность

1. Организация параллельных вычислений с использованием технологии передачи сообщений MPI. Основные группы функций MPI. Обработка ошибок в MPI.

• MPI 1.1 Standard разрабатывался 92-94

• MPI 2.0 - 95-97

• MPI 2.1 – 2008

• MPI 3.1 – 2015

Реализации MPI

• MPICH

• LAM/MPI

• Mvapich

• OpenMPI

• Коммерческие реализации Intel,IBM и др.

Модель MPI

• Параллельная программа состоит из процессов, процессы могут быть многопоточными.MPI реализует передачу сообщений между процессами.

• MPI реализует передачу сообщений между процессами.

• Межпроцессное взаимодействие предполагает:

  • синхронизацию

  • перемещение данных из адресного пространства одного процесса в адресное пространство другого процесса

Модель программ

• SPMD – Single Program Multiple Data

• Одна и та же программа выполняется различными процессорами

• Управляющими операторами выбираются различные части программы на каждом процессоре.

Модель выполнения

• Запуск: mpirun

• При запуске указываем число требуемых процессоров np и название программы: пример: mpirun –np 3 prog

• Каждый процесс MPI-программы получает два значения:

  • np – число процессов

  • rank из диапазона [0 … np-1] – номер процесса

• Любые два процесса могут непосредственно обмениваться данными с помощью функций передачи сообщений

Основы передачи данных в MPI

• Технология передачи данных MPI предполагает кооперативный обмен.

• Данные посылаются одним процессом и принимаются другим.

• Передача и синхронизация совмещены.

Основные понятия

• Процессы объединяются в группы.

• Каждое сообщение посылается в рамках некоторого контекста и должно быть получено в том же контексте.

• Группа и контекст вместе определяют коммуникатор.

• Процесс идентифицируется своим номером в группе, ассоциированной с коммуникатором.

Основные группы функций MPI

• Определение среды

• Передачи «точка-точка»

• Коллективные операции

• Производные типы данных

• Группы процессов

• Виртуальные топологии

• Односторонние передачи

• Параллельный ввод-вывод

Понятие коммуникатора MPI

• Все обращения к MPI функциям содержат коммуникатор, как параметр.

• Наиболее часто используемый коммуникатор MPI_COMM_WORLD:

  • определяется при вызове MPI_Init

  • содержит ВСЕ процессы программы

• Другие предопределенные коммуникаторы:

  • MPI_COMM_SELF – только один (собственный) процесс

  • MPI_COMM_NULL – пустой коммуникатор

Типы данных MPI

• Данные в сообщении описываются тройкой: (address, count, datatype), где

• datatype определяется рекурсивно как:

  • предопределенный базовый тип, соответствующий типу данных в базовом языке (например, MPI_INT, MPI_DOUBLE_PRECISION)

  • Непрерывный массив MPI типов

  • Векторный тип

  • Индексированыый тип

  • Произвольные структуры

• MPI включает функции для построения пользовательских типов данных, например, типа данных, описывающих пары (int, float).

Понятие тэга

• Сообщение сопровождается определяемым пользователем признаком – целым числом – тэгом для идентификации принимаемого сообщения

• Теги сообщений у отправителя и получателя должны быть согласованы. Можно указать в качестве значения тэга константу MPI_ANY_TAG.

Функции определения среды

• int MPI_Init(int *argc, char ***argv) должна первым вызовом, вызывается только один раз

• int MPI_Comm_size(MPI_Comm comm, int *size) – число процессов в коммуникаторе

• int MPI_Comm_rank(MPI_Comm comm, int *rank) – номер процесса в коммуникаторе (нумерация с 0)

• int MPI_Finalize() – завершает работу процесса

• int MPI_Abort (MPI_Comm_size(MPI_Comm comm, int*errorcode) – завершает работу программы

Обработка ошибок MPI-функций - Определяется константой MPI_SUCCESS

int error;

……

error = MPI_Init(&argc, &argv));

If (error != MPI_SUCCESS)

{

fprintf (stderr, “ MPI_Init error \n”);

return 1;

}

Обработка ошибок MPI-функций - Определяется константой MPI_SUCCESS

1. Функции двухточечных передач данных в MPI. Способы организации неблокирующих передач.

Взаимодействие «точка-точка»

• Самая простая форма обмена сообщением

• Один процесс посылает сообщения другому

• Несколько вариантов реализации того, как пересылка и выполнение программы совмещаются

Варианты передачи «точка-точка»

• Синхронные пересылки

• Асинхронные передачи

• Блокирующие передачи

• Неблокирующие передачи

Блокирующие и неблокирующие передачи

• Определяют, при каких условиях операции передачи завершаются:

  • Блокирующие: возврат из функций передачи сообщений только по завершению передачи

  • Неблокирующие: немедленный возврат из функций, пользователь должен контролировать завершение передач

Основа 2-точечных обменов

• int MPI_Send(void *buf,int count, MPI_Datatype datatype,int dest, int tag, MPI_Comm comm)

  • buf – адрес буфера

  • count – число пересылаемых элементов

  • Datatype – MPI datatype

  • dest – rank процесса-получателя

  • tag – определяемый пользователем параметр,

  • comm – MPI-коммуникатор

• int MPI_Recv(void *buf,int count, MPI_Datatype datatype,int source, int tag, MPI_Comm comm, MPI_Status *status)

  • buf – адрес буфера

  • count – число пересылаемых элементов

  • Datatype – MPI datatype

  • source – rank процесса-отправителя

  • tag – определяемый пользователем параметр,

  • comm – MPI-коммуникатор,

  • status – статус

Wildcarding (джокеры)

• Получатель может использовать джокер для получения сообщения от ЛЮБОГО процесса MPI_ANY_SOURCE

• Для получения сообщения с ЛЮБЫМ тэгом MPI_ANY_TAG

• Реальные номер процесса-отправителя и тэг возвращаются через параметр status

Информация о завершившемся приеме сообщения

• Возвращается функцией MPI_Recv через параметр status

• Содержит:

  • Source: status.MPI_SOURCE

  • Tag: status.MPI_TAG

  • Count: MPI_Get_count

Полученное сообщение

• Может быть меньшего размера, чем указано в функции MPI_Recv

• count – число реально полученных элементов

C: int MPI_Get_count (MPI_Status *status, MPI_Datatype datatype, int *count)

MPI_Probe

int MPI_Probe(int source, int tag, MPI_Comm comm, MPI_Status* status) Проверка статуса операции приема сообщения. Параметры аналогичны функции MPI_Recv

Совмещение передач типа «отсылка-прием»

int MPI_Sendrecv (void *sendbuf,

int sendcount, MPI_Datatype sendtype,

int dest, int sendtag,

void *rcvbuf, int rcvcount, MPI_Datatype rcvtype,

int source, int rcvtag,

MPI_Comm comm,

MPI_Status *status)

Обмен данными одного типа с замещением

int MPI_Sendrecv_replace

(void* buf, int count,

MPI_Datatype datatype,

int dest, int sendtag,

int source, int recvtag,

MPI_Comm comm, MPI_Status *status)

Неблокирующие коммуникации

Цель – уменьшение времени работы параллельной программы за счет совмещения вычислений и обменов.

Неблокирующие операции завершаются, не дожидаясь окончания передачи данных.

Проверка состояния передач и ожидание завершение передач выполняются специальными функциями.

Форматы неблокирующих функций

MPI_Isend(buf,count,datatype,dest,tag,comm,request)

MPI_Irecv(buf,count,datatype,source,tag,comm, request)

Проверка завершения операций MPI_Wait() and MPI_Test().

MPI_Wait() ожидание завершения.

MPI_Test() проверка завершения. Возвращается флаг, указывающий на результат завершения.

Замер времени MPI_Wtime

• Время замеряется в секундах

• Выделяется интервал в программе

double MPI_Wtime(void);

1. Организация коллективных передач данных в MPI: назначение, основные функции.

Характеристики коллективных передач

• Коллективные операции не являются помехой операциям типа «точка-точка» и наоборот

• Все процессы коммуникатора должны вызывать коллективную операцию

• Синхронизация не гарантируется (за исключением барьера)

• Нет неблокирующих коллективных операций

• Нет тэгов

• Принимающий буфер должен точно соответствовать размеру отсылаемого буфера

Широковещательная рассылка

• One-to-all передача: один и тот же буфер отсылается от процесса root всем остальным процессам в коммуникаторе

• int MPI_Bcast (void *buffer, int, count, MPI_Datatype datatype,int root, MPI_Comm comm)

• Все процессы должны указать один тот же root и communicator

Scatter

• One-to-all communication: различные данные из одного процесса рассылаются всем процессам коммуникатора (в порядке их номеров)

• int MPI_Scatter(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount,MPI_Datatype recvtype, int root, MPI_Comm comm)

• sendcount – число элементов, посланных каждому процессу, не общее число отосланных элементов;

• send параметры имеют смысл только для процесса root

Глобальные операции редукции

• Операции выполняются над данными, распределенными по процессам коммуникатора

• Примеры:

  • Глобальная сумма или произведение

  • Глобальный максимум (минимум)

  • Глобальная операция, определенная пользователем

Общая форма

int MPI_Reduce(void* sendbuf, void* recvbuf, int count, MPI_Datatype datatype, MPI_Op op, int root,MPI_Comm comm)

• count число операций “op” выполняемых над последовательными элементами буфера sendbuf

• (также размер recvbuf)

• op является ассоциативной операцией, которая выполняется над парой операндов типа datatype и возвращает результат того же типа

1. Понятие о виртуальной топологии процессов в MPI. Функции MPI для работы с виртуальными топологиями. Использование виртуальных топологий для реализации сеточных задач.

Декартова топология

• Логическая топология, определяемая многомерной решеткой.

• Обобщение линейной и матричной топологий на произвольное число измерений.

• Для создания коммуникатора с декартовой топологией используется функция MPI_Cart_create. С помощью этой функции можно создавать топологии с произвольным числом измерений, причем по каждому измерению в отдельности можно накладывать периодические граничные условия.

Основные функции:

• MPI_CART_CREATE

  • Создает структуру «прямоугольная решетка» произвольной размерности.

  • int MPI_Cart_create(MPI_Comm old_comm, int ndims, int *dim_size, int *periods, int reorder, MPI_Comm *new_comm)

• MPI_CART_COORDS

• MPI_CART_RANK

• MPI_CART_SUB

  • Используется для разделения коммуникатора на подгруппы . MPI_CART_SUB создает новый коммуникатор меньшей размерности

  • int MPI_Cart_sub( MPI_Comm old_comm, int *belongs, MPI_Comm *new_comm)

• MPI_CARTDIM_GET

• MPI_CART_GET

• MPI_CART_SHIFT

  • Получение номеров посылающего (source) и принимающего (dest) процессов в декартовой топологии коммуникатора comm для осуществления сдвига вдоль измерения direction на величину disp.

  • int MPI_Cart_shift( MPI_Comm comm, int direction, int displ, int *source, int *dest )

  • Для периодических измерений осуществляется циклический сдвиг, для непериодических – линейный сдвиг.

  • Для n-мерной декартовой решетки значение direction должно быть в пределах от 0 до n-1.

  • Значения source и dest можно использовать, например, для обмена функцией MPI_Sendrecv.

  • Не является коллективной операцией!

Обмен данными в программе.

• Процессу необходимо обменяться данными с соседями.

• Из-за того что данные хранятся в памяти не непрерывно, для выполнения межпроцессорных обменов предварительно формируются передаваемые сообщения.

• Потом при помощи функций MPI_Cart_shift происходит определение ранга процесса, которому надо послать данные, и процесса, от которого данные необходимо получить. После чего при помощи MPI_Sendrecv - обмен данными с соседними процессами.

1. Задача Дирихле для уравнения Пуассона в прямоугольнике, разностная аппроксимация задачи на прямоугольной неравномерной сетке.

В прямоугольной области