Топологии процессов icon

Топологии процессов




Скачати 115.42 Kb.
НазваТопологии процессов
Дата14.07.2012
Розмір115.42 Kb.
ТипДокументи
1. /BOOK/CHAPTER1.DOC
2. /BOOK/CHAPTER2.DOC
3. /BOOK/CHAPTER3.DOC
4. /BOOK/CHAPTER4.DOC
5. /BOOK/CHAPTER5.DOC
6. /BOOK/CHAPTER6.DOC
7. /BOOK/SODERG.DOC
Предисловие к mpi
Mpi договоренности
Сканирующая связь
Коллективная связь
Группы Контексты, и Коммуникаторы
Топологии процессов
Содержаhие


Глава 6


Топологии процессов


6.1 Введение


Эта глава обсуждает топологии как один из механизмов MPI. Топология -дополнительный атрибут, который может добавляться к коммуникатору интра;топологии не могут быть добавлены к межкоммуникаторам. Топология можетобеспечить удобный механизм присваивания имен для процессов группы (в пределах коммуникатора), и к тому же, может помочь распределению процессов на аппаратные средства.

Как установлено в главе 5 группа в MPI это n процессов. Каждому про-цессу в группе назначается ранг между 0 и n-1. В многих параллельных прило-жениях линейное ранжирование процессов неприемлемо и часто процессы разме-щаются в такой топологии как двух- или трехмерные решетки или вообще логи-ческое размещение процессов описывается графом. В этой главе мы ссылаемся на эти логические размещения процессов какна "виртуальные топологии." Однако нужно различать виртуальные топологиипроцессов и топологию основных аппаратных средств. Описание виртуальных то-пологий зависит только от приложения пользователя и является машинно-неза-висимо.


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


Образцом связи комплекта процессов может являться граф. Узлы графа

это процессы, а дуги это соединнения между процессами. Так как MPI обеспе-

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

Определение виртуальной топологии с точки зрения графа достаточно длявсех приложений. Топологии типа кольца, двух- или многомерных решеток, являются частными случаями графа.

Hужный грф получается при помощи определенного присваиванию уни-кальных имен процессам.


6.3 Обзор функций


Функции MPI_GRAPH_CREATE и MPI_CART_CREATE используются, чтобы создать виртуальную топологию графа и декартовую топологию соответственноФункции создания топологий требуют входной коммуникатор, который определяет комплект процессов на которых должна быть отображена топология. В результате действия этих функций создается новый коммуникатор topol, которыйнесет топологическую структуру как кешированную информацию (смотри Главу 5).

Вспомогательная функция MPI_DIMS_CREATE вычислят нужное распределение процессов среди данного количества измерений.

Функция MPI_TOPO_TEST запрашивается тип топологии, связанной с данным коммуникатором.

Топологическая информация может получаться из коммуникатора с помощью функций MPI_GRAPHDIMS_GET и MPI_GRAPH_GET для графов, и

MPI_CARTDIM_GET и MPI_CART_GET для декартовых топологий.


Функции MPI_CART_RANK и MPI_CART_COORDS переводят декартовые координаты в групповой ранг, и наоборот;

Функция MPI_CART_SHIFT помогае определить ранги процессов, которыенужны для связи на декартовом уровне.

Функции MPI_GRAPH_NEIGHBORS_COUNT и MPI_GRAPH_NEIGHBORS работают с соседними узлами графа.


6.4 Конструкторы топологии


6.4.1 Декартовый конструктор


MPI_CART_CREATE(comm old, ndims, dims, periods, reorder, comm cart)

IN comm - входной коммуникатор (handle)

IN ndims - ко-во измерений декартовой решетки (integer)

IN dims - массив размерности ndims содержащий ко-во процессов

в каждом измерении решетки (array of integer)

IN periods - массив размерности ndims содержащий true или false

(array of logial)

IN reorder - ранжирование записей (true) или (false) (logical)

OUT comm cart - коммуникатор с созданной декартовой топологией (handle)


int MPI_Cart_create(MPI Comm comm old, int ndims, int *dims, int *periods,

int reorder, MPI Comm *comm cart)

MPI_CART_CREATE(COMM OLD, NDIMS, DIMS, PERIODS, REORDER, COMM CART, IERROR)

INTEGER COMM OLD, NDIMS, DIMS(*), COMM CART, IERROR

LOGICAL PERIODS(*), REORDER


MPI_CART_CREATE возвращать указатель на новый коммуникатор в которомописана декартовая топология. Если recorder = false, тогда ранг каждого процесса в новой группе идентичный рангу в старой группе. В противном случае, функция может преобразовать ранги процессов для лучшего наложения виртуальной топологии на физическую машину. Если общий размер декартов решетки меньший чем размер группы сомм, то некоторым процессам будет возвращено MPI_COMM_NULL. Команда твозвратит ошибку если определенная решетка большечем процессов в группе.


6.4.2 Декартовая функция:


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


MPI_DIMS_CREATE(nnodes, ndims, dims)

IN nnodes - число узлов в решетке (integer)

IN ndims - чило декартовых измерений (integer)

INOUT dims - массив размерности ndims содержащий ко-во процессов

в каждом измерении решетки (array of integer)


int MPI_Dims_create(int nnodes, int ndims, int *dims)

MPI_DIMS_CREATE(NNODES, NDIMS, DIMS, IERROR)

INTEGER NNODES, NDIMS, DIMS(*), IERROR


Данные в массиве dims распределяются так, чтобы описать декартовуюрешетку с ndims измерениями и nnodes узлами.


Пример 6.1

+-------------------------------------------------------+

¦in dims ¦ Функция ¦ out dims ¦

+--------+-----------------------------+----------------¦

¦ (0,0) ¦ MPI_DIMS_CREATE(5, 2, dims) ¦ (3,2) ¦

¦ (0,0) ¦ MPI DIMS CREATE(8, 2, dims) ¦ (7,1) ¦

¦ (0,3,0)¦ MPI DIMS CREATE(6, 3, dims) ¦ (2,3,1) ¦

¦ (0,3,0)¦ MPI DIMS CREATE(2, 3, dims) ¦ ошибочный вызов¦

+-------------------------------------------------------+


6.4.3 Конструктор графа


MPI_GRAPH_CREATE(comm old, nnodes, index, edges, reorder, comm graph)

IN comm - входной коммуникатор (handle)

IN nnodes - число узлов в графе (integer)

IN index - массив описывающий градусы (array of integers)

IN edges - массив описывающий окончания графа (array of integers)

IN reorder - ранжирование записей (true) или (false) (logical)

OUT comm graph - коммуникатор с созданной топологией графа (handle)

int MPI_Graph_create(MPI Comm comm old, int nnodes, int *index, int *edges,

int reorder, MPI Comm *comm graph)

MPI_GRAPH_CREATE(COMM OLD, NNODES, INDEX, EDGES, REORDER, COMM GRAPH,

IERROR)

INTEGER COMM OLD, NNODES, INDEX(*), EDGES(*), COMM GRAPH, IERROR

LOGICAL REORDER


MPI_GRAPH_CREATE возвращать указатель на новый коммуникатор в котором описана топология графа. Если recorder = false, тогда ранг каждого процесса в новой группе идентичный рангу в старой группе. В противном случае, функция может преобразовать ранги процессов для лучшего наложения виртуальной топологии на физическую машину. Если общий размер графа меньший чем размер группы сомм, то некоторым процессам будет возвращено MPI_COMM_NULL. Команда твозвратит ошибку если определенный граф больше чемпроцессов в группе.

Параметры nnodes, index и edges определяют cтруктуру графа. nnodes количество узелов графа. Узелы перечисляются от 0 до nnodes-1. i-й эллимент массива index хранит общее число соседей i-х узлов графа. Массив edges- хранит перечень самих соседей. Общее число данных в index - nnodes и общее число данных в edges равняется номеру окончания графа.

Определение аргументов nnodes, index и edges иллюстрируется в следующем примере.


Пример 6.2 Принимает четыре процесса 0, 1, 2, 3 со следующей матрицей смежность:

+------------------+

¦процессы ¦ соседи ¦

+---------+--------¦

¦ 0 ¦ 1, 3 ¦

¦ 1 ¦ 0 ¦

¦ 2 ¦ 3 ¦

¦ 3 ¦ 0, 2 ¦

+------------------+


Входные аргументы:

nnodes = 4 ;

index = 2, 3, 4, 6 ( по 2 позицию, со 2 по 3 позицию и т.д.) ;

edges = 1, 3, 0, 3, 0, 2 (перечень соседей)


Следующая информация топологии, которая хранится в коммуникаторе:

- Тип топологии (декартовая/граф),

- Для декартовой топологии :

1. ndims (количество измерений),

2. dims (количества процессов по координатным направлениям),

3. periods (информация периодичности),

- Для топологии графа:

1. index

2. edges, определяющие структуру графа.


6.4.4 Функции запроса топологии


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


MPI_TOPO_TEST(comm, status)

IN comm - коммуникаторr (handle)

OUT status - тип топологии данного коммуникатра (choice)


int MPI_Topo_test(MPI Comm comm, int *status)

MPI_TOPO_TEST(COMM, STATUS, IERROR)

INTEGER COMM, STATUS, IERROR


Функция MPI_TOPO_TEST возвращает тип топологии, который был присвоен данному коммуникатору. Status может принимать следующие значения :


MPI_GRAPH - топология графа

MPI_CART - декартовая топология

MPI_UNDEFINED - топология не определена


MPI_GRAPHDIMS_GET(comm, nnodes, nedges)

IN comm - коммуникатор для группы с топологией графа (handle)

OUT nnodes - число узлов в графе (integer)

OUT nedges - число окончаний графа (integer)


int MPI_Graphdims_get(MPI Comm comm, int *nnodes, int *nedges)

MPI_GRAPHDIMS_GET(COMM, NNODES, NEDGES, IERROR)

INTEGER COMM, NNODES, NEDGES, IERROR


Функция MPI_GRAPHDIMS_GET извлекает информацию из коммуникатора топологии графа.


MPI_GRAPH_GET(comm, maxindex, maxedges, index, edges)

IN comm - коммуникатор со стуктурой графа (handle)

IN maxindex - длина вектора index в вызывающей программе (integer)

IN maxedges - длина вектора edges в вызывающей программе (integer)

OUT index - массив содержащий структуру графа (подробнее

см. MPI_GRAPH_CREATE (аrray of integers)

OUT edges - массив содержащий структуру графа (аrray of integers)


int MPI_Graph_get(MPI Comm comm, int maxindex, int maxedges, int *index,

int *edges)

MPI_GRAPH_GET(COMM, MAXINDEX, MAXEDGES, INDEX, EDGES, IERROR)

INTEGER COMM, MAXINDEX, MAXEDGES, INDEX(*), EDGES(*), IERROR


MPI_CARTDIM_GET(comm, ndims)

IN comm - коммуникатор с декартовой структурой (handle)

OUT ndims - число измерений данной топологии (integer)


int MPI_Cartdim_get(MPI Comm comm, int *ndims)

MPI_CARTDIM_GET(COMM, NDIMS, IERROR)

INTEGER COMM, NDIMS, IERROR


Функции MPI_CARTDIM_GET и MPI GRAPH GET возвращают информациюо топологиях, которая связывалась с коммуникатором при создании этихтопологий.


MPI_CART_GET(comm, maxdims, dims, periods, coords)

IN comm - коммуникатор с декартовой структурой (handle)

IN maxdims - длина вектора {dims, periods и coords} в

вызываемой программе (integer)

OUT dims - ко-во процессов для каждого измерения (array of integer)

OUT periods - (true/false) для каждого измерения (array of logical)

OUT coords - координаты вызываемого процесса в

декартовой структуре (array of integer)

int MPI_Cart_get(MPI Comm comm, int maxdims, int *dims, int *periods,

int *coords)

MPI_CART_GET(COMM, MAXDIMS, DIMS, PERIODS, COORDS, IERROR)

INTEGER COMM, MAXDIMS, DIMS(*), COORDS(*), IERROR

LOGICAL PERIODS(*)


MPI_CART_RANK(comm, coords, rank)

IN comm - коммуникатор с декартовой структурой (handle)

IN coords - координаты вызываемого процесса в

декартовой структуре (array of integer)

OUT rank - ранг данного процесса (integer)


int MPI_Cart_rank(MPI Comm comm, int *coords, int *rank)

MPI_CART_RANK(COMM, COORDS, RANK, IERROR)

INTEGER COMM, COORDS(*), RANK, IERROR


Для группы процесов с декартовой структурой, функция MPI_CART_RANKпереводит логические координаты процесса в ранг.

Для измерения i с periods(i) = true, если координата coords(i), из области coords(i)< 0 или coords(i) >= dims(i), то они изменяются автоматически на 0 <=coords(i)< dims(i).


MPI_CART_COORDS(comm, rank, maxdims, coords)

IN comm - коммуникатор с декартовой структурой (handle)

IN rank - ранг процесса (integer)

IN maxdims - длина вектора координат вызывающей программы (integer)

ОUT coords - координаты вызываемого процесса в

декартовой структуре (array of integer)


int MPI_Cart_coords(MPI Comm comm, int rank, int maxdims, int *coords)

MPI_CART_COORDS(COMM, RANK, MAXDIMS, COORDS, IERROR)

INTEGER COMM, RANK, MAXDIMS, COORDS(*), IERROR


Обратное предыдущей функции. Перевод ранга в координаты.


MP_GRAPH_NEIGHBORS_COUNT(comm, rank, nneighbors)

IN comm - коммуникатор с топологией графа (handle)

IN rank - ранг процесса (integer)

OUT nneighbors - число соседей данного процесса (integer)


int MPI_Graph_neighbors_count(MPI Comm comm, int rank, int *nneighbors)

MPI_GRAPH_NEIGHBORS_COUNT(COMM, RANK, NNEIGHBORS, IERROR)

INTEGER COMM, RANK, NNEIGHBORS, IERROR


MP_GRAPH_NEIGHBORS_COUNT и MPI_GRAPH_NEIGHBORS обеспечивают информацию смежности для топологии графа.


MPI_GRAPH_NEIGHBORS(comm, rank, maxneighbors, neighbors)

IN comm - коммуникатор с топологией графа (handle)

IN rank - ранг процесса (integer)

IN maxneighbors - размер массива neighbors (integer)

OUT neighbors - массив рангов процессов соседних

с данным (array of integer)


int MPI_Graph_neighbors(MPI Comm comm, int rank, int maxneighbors,

int *neighbors)

MPI_GRAPH_NEIGHBORS(COMM, RANK, MAXNEIGHBORS, NEIGHBORS, IERROR)

INTEGER COMM, RANK, MAXNEIGHBORS, NEIGHBORS(*), IERROR


6.4.5 Сдвиг декартовых координат


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


MPI_CART_SHIFT(comm, direction, disp, rank source, rank dest)

IN comm - коммуникатор с дек/артовой структурой (handle)

IN direction - координаты направлени сдвига (integer)

IN disp - смещение ( >0: сдвиг вверх, <0: cдвиг вниз) (integer)

OUT rank source - ранг процесса источника (integer)

OUT rank dest - ранг процессаприемника (integer)


int MPI_Cart_shift(MPI Comm comm, int direction, int disp, int *rank source,

int *rank dest)

MPI_CART_SHIFT(COMM, DIRECTION, DISP, RANK SOURCE, RANK DEST, IERROR)

INTEGER COMM, DIRECTION, DISP, RANK SOURCE, RANK DEST, IERROR


Аргумент direction указывает измерение в котором происходитсдвиг.


Пример 6.3. Коммуникатор comm имеет два измерения. В двумерный массив реально загружены по одному элементу на процесс в переменной A. Hужно сдвинуть столбец i вертикально i раз.


....

C Получение ранга процесса

CALL MPI_COMM_RANK(comm, rank, ierr))

C Получение декартовых координат

CALL MPI_CART_COORDS(comm, rank, maxdims, coords, ierr)

C вычисляет источник и приемник сдвига

CALL MPI_CART_SHIFT(comm, 0, coords(2), source, dest, ierr)

C передача сообщений

CALL MPI_SENDRECV_REPLACE(A, 1, MPI_REAL, dest, 0, source, 0, comm,

+ status, ierr)


6.4.6 Разметка декартовой структуры


MP_CART_SUB(comm, remain_dims, newcomm)

IN comm - коммуникатор с декартовой структурой (handle)

IN remain_dims - логический вектор (logical vector)

OUT newcomm - коммуникатор содержащий подрешетку, которая

должна подключиться (handle)


int MPI_Cart_sub(MPI Comm comm, int *remain dims, MPI Comm *newcomm)

MPI_CART_SUB(COMM, REMAIN DIMS, NEWCOMM, IERROR)

INTEGER COMM, NEWCOMM, IERROR

LOGICAL REMAIN DIMS(*)


MP_CART_SUB разделяет группу коммуникатора в подгруппы, которые формируют нижне-мерные декартовые подрешетки. Если remain_dims(i) = true то это измерение сохраняется. Эта функция тесно связанна с MPI_COMM_SPLIT.


Пример 6.5 Допустим что MPI_CART_CREATE(..., сомм) определяет (2*3*4) решетку. emain_dims = (true,false,true). Тогда вызов


MPI_CART_SUB(comm, remain_dims, comm_new)


создаст три коммуникатора каждый с восмью процессами и декартовыми топологиями 2*4. Если emain_dims = (false,false,true) то вызов


MPI_CART_SUB(comm, remain_dims, comm_new)


создаст шесть коммуникаторов, каждый с четырьмя процессами одно-декартовой топологии.


6.4.7 Функции топологии низкого уровня


Hиже будут рассмотренны две дополнительные функции.


MPI_CART_MAP(comm, ndims, dims, periods, newrank)

IN comm - входной коммуникатор (handle)

IN ndims - число измерений декартовой структуры (integer)

IN dims - массив количеств процессов для каждой

размерности (array of integer)

IN periods - массив размерности ndims содержащий

true или false (array of logial)

OUT newrank - преобразовывает ранг вызываемого

процесса; MPI_UNDEFINED если вызывающий

процесс не принадлежит решетке (integer)


int MPI_Cart_map(MPI Comm comm, int ndims, int *dims, int *periods,

int *newrank)

MPI_CART_MAP(COMM, NDIMS, DIMS, PERIODS, NEWRANK, IERROR)

INTEGER COMM, NDIMS, DIMS(*), NEWRANK, IERROR

LOGICAL PERIODS(*)


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


MPI_GRAPH_MAP(comm, nnodes, index, edges, newrank)

IN comm - входной коммуникатор (handle)

IN nnodes - число узлов графа (integer)

IN index - массив определяющий структуру графа

(см. MPI_GRAPH_CREATE) (array of integer)

IN edges - массив определяющий структуру графа

OUT newrank - преобразовывает ранг вызываемого

процесса; MPI_UNDEFINED если вызывающий

процесс не принадлежит решетке (integer)


int MPI_Graph_map(MPI Comm comm, int nnodes, int *index, int *edges,

int *newrank)

MPI_GRAPH_MAP(COMM, NNODES, INDEX, EDGES, NEWRANK, IERROR)

INTEGER COMM, NNODES, INDEX(*), EDGES(*), NEWRANK, IERROR


6.5 Пример


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

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


integer ndims, num neigh

logical reorder

parameter (ndims=2, num neigh=4, reorder=.true.)

integer comm, comm cart, dims(ndims), neigh def(ndims), ierr

integer neigh rank(num neigh), own position(ndims), i, j

logical periods(ndims)

real*8 u(0:101,0:101), f(0:101,0:101)

data dims /ndims*0 /

comm = MPI_COMM_WORLD

C Установка размера решетки

call MPI_DIMS_CREATE(comm, ndims, dims,ierr)

periods(1) = .TRUE.

periods(2) = .TRUE.

C Создает структуру решетки в группе WORLD и запрашивает собственную позицию

call MPI CART CREATE (comm, ndims, dims, periods, reorder, comm cart,ierr)

call MPI CART GET (comm cart, ndims, dims, periods, own position,ierr)

C Просматривает ранги соседей. Собственные координаты процесса : (i,j).

C Соседи : (i-1,j), (i+1,j), (i,j-1), (i,j+1)

i = own_position(1)

j = own_position(2)

neigh_def(1) = i-1

neigh_def(2) = j

call MPI_CART_RANK (comm_cart, neigh_def, neigh_rank(1),ierr)

neigh_def(1) = i+1

neigh_def(2) = j

call MPI_CART_RANK (comm_cart, neigh_def, neigh_rank(2),ierr)

neigh_def(1) = i

neigh_def(2) = j-1

call MPI_CART_RANK (comm_cart, neigh_def, neigh_rank(3),ierr)

neigh_def(1) = i

neigh_def(2) = j+1

call MPI_CART_RANK (comm_cart, neigh_def, neigh_rank(4),ierr)

C Инициализация решетки и начало итераций

call init (u, f)

do 10 it=1,100

call relax (u, f)

C Обмен данными с соседними процессами

call exchange (u, comm cart, neigh rank, num neigh)

10 continue

call output (u)

end


Рисунок 6.1: Установка структуры задачи для двумерного параллельного Пуассоновского решающего устройства.

Схожі:

Топологии процессов iconДокументи
1. /Моделирование лавинообразных процессов/F01_Титульный лист 16-02-06.doc
2.
Топологии процессов iconДокументи
1. /Моделирование лавинообразных процессов/F01_Титульный лист 16-02-06.doc
2.
Топологии процессов iconДокументи
1. /Моделирование лавинообразных процессов/F01_Титульный лист 16-02-06.doc
2.
Топологии процессов iconДокументи
1. /Моделирование лавинообразных процессов/F01_Титульный лист 16-02-06.doc
2.
Топологии процессов iconДокументи
1. /Моделирование лавинообразных процессов/F01_Титульный лист 16-02-06.doc
2.
Топологии процессов iconДокументи
1. /Моделирование лавинообразных процессов/F01_Титульный лист 16-02-06.doc
2.
Топологии процессов iconЕлектромеханічні системи та автоматизація
Это определяет их от­личительные особенности в пусковых режимах. Из­вестные методы расчета пусковых режимов, основанные на анализе...
Топологии процессов iconХiі международную научно-техническую конференцию «автоматизация технологических объектов и процессов. Поиск молодых»
Целью конференции является обмен информацией о прогрессивных результатах научно-исследова-тельской работы аспирантов, магистрантов...
Топологии процессов iconХiii международную научно-техническую конференцию «автоматизация технологических объектов и процессов. Поиск молодых»
Целью конференции является обмен информацией о прогрессивных результатах научно-исследова-тельской работы аспирантов, магистрантов...
Топологии процессов iconХiv международную научно-техническую конференцию «автоматизация технологических объектов и процессов. Поиск молодых»
Целью конференции является обмен информацией о прогрессивных результатах научно-исследова-тельской работы аспирантов, магистрантов...
Топологии процессов iconХарьковская национальная академия городского хозяйства в. А. Лелюк, А. В. Лелюк, Н. П. Пан совершенствование бизнес-процессов
Лелюк В. А., Лелюк А. В., Пан Н. П. Совершенствование бизнес-процессов: Пер с укр. / Под ред. В. А. Лелюка: Учебное пособие. Харьков:...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи