Основы параллельного программирования вычислительных систем с распределенной и разделяемой памятью

int MPI_Cart_rank (MPI_Comm comm, int *coords, int *rank)

Для обратного преобразования – функция

int MPI_Cart_coords (MPI_Comm comm,

int rank,

int ndims,

int *coords)

Для определения соседних процессов в измерении  dir MPI предоставляет функцию

int MPI_Cart_shift (MPI_Comm comm,

int dir,

int displ,

int *rank_source,

int *rank_dest)

Пример. Рассмотрим 12 процессов, из которых сформирована решетчатая структура 3х4 с периодическими соединениями. Каждый процесс хранит вещественное значение, которым он обменивается с соседним в измерении 0 процессом.

int coords[2], dims[2], periods[2], source, dest, my_rank,

reorder;

MPI_Comm comm_2d;

MPI_status status;

float a, b;

MPI_Comm_rank (MPI_COMM_WORLD, &my_rank);

dims[0] = 3; dims[1] = 4;

periods[0] = periods[1] = 1;

reorder = 0;

MPI_Cart_create (MPI_COMM_WORLD, 2, dims, periods, reorder,

&comm_2d);

MPI_Cart_coords (comm_2d, my_rank, 2, coords);

MPI_Cart_shift (comm_2d, 0, coords[1], &source, &dest);

a = my_rank;

MPI_Sendrecv (&a, 1, MPI_FLOAT, dest, 0, &b, 1, MPI_FLOAT,

source, 0, comm_2d, &status);

#

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

int MPI_Cart_sub (MPI_Comm comm,

  int *remain dims,

  MPI Comm *new_comm)

Пример. Пусть для коммуникатора comm_3d была определена виртуальная решетка 2х3х4. Вызов

int MPI_Cart_sub (comm_3d, remain_dims, &new_comm)

где remain_dims=(1,0,1)сгенерирует три решетки 2х4 и каждый процесс получит свой коммуникатор для соответствующей ему подрешетки (см. рисунок 9). #

Рисунок 9 – Разделение трехмерной решетки размера 2х3х4 на три двумерные решетки размером 2х4 каждая

Для получения информации о виртуальной топологии, определенной для некоторого коммуникатора, можно  использовать MPI-функцию

int MPI_Cartdim_get (MPI_Comm comm, int *ndims)

возвращающую параметр ndims – количество измерений виртуальной решетки, ассоциированной с коммуникатором comm, и функцию

int MPI_Cart_get (MPI_Comm comm,

int maxdims,

int *dims,

int *periods,

int *coords)

возвращающую информацию о виртуальной  топологии, ассоциированной  с коммуникатором comm. Эта виртуальная топология должна иметь maxdims измерений, и массивы dims, periods и coords должны быть такой размерности. Возвращается следующая информация: целочисленный массив dims содержит число процессов в каждом направлении виртуальной решетки, логический массив periods соответствующую информацию о периодичности. Целочисленный массив coords содержит декартовы координаты вызывающего процесса.

 

 

 

 

3.3.3 Временные и прерывающие  процессы

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

double MPI_Wtime (void)

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

start = MPI_Wtime();

part_to_measure();

end = MPI_Wtime();

Функция

double MPI_Wtick (void)

возвращает время в секундах между двумя последовательными отсчетами часов. Если разрешением является микросекунда, то эта функция возвратит 10^-6.

Выполнение всех процессов  коммуникатора может быть прервано путем вызова MPI-функции

int MPI_Abort (MPI_Comm comm, int error_code)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 Введение в потоковое программирование  в OpenMP

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

OpenMP – переносимый стандарт программирования систем с разделяемой памятью. Интерфейс прикладной программы (API, application program interface) OpenMP предоставляет набор директив компилятора, библиотечных подпрограмм и переменных окружения. Директивы компилятора могут быть использованы для расширения последовательных языков Fortran, C и C++ различными конструкциями; библиотечные подпрограммы и переменные окружения – для контроля исполняющей системы.

Модель программирования OpenMP основана на взаимодействующих потоках, выполняющихся одновременно на нескольких процессорах или ядрах. Потоки создаются и уничтожаются в соответствии с моделью «ветвление-объединение» (fork-join). Выполнение программы OpenMP начинается с одного базового потока, исполняющего программу последовательно до тех пор, пока не встретится первая конструкция parallel. Встретив эту конструкцию, базовый поток создает набор потоков, в который входит определенное количество новых потоков и сам базовый поток. Режим параллельного исполнения может быть осуществлен в стиле SPMD, однако назначение различных задач различным потокам также возможно. OpenMP предоставляет директивы для различных моделей исполнения. В конце параллельной области программы осуществляется барьерная синхронизация, и далее только базовый поток продолжает свое исполнение.

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

 

Ключевыми элементами OpenMP являются:

• конструкции для создания потоков;
• конструкции распределения работы между потоками;
• конструкции для управления работой с данными;
• конструкции для синхронизации потоков;
• процедуры библиотеки поддержки времени выполнения;
• переменные окружения.

Силу и простоту ОреnМР можно продемонстрировать на примере. Следующий цикл конвертирует каждый 32-разрядный пиксел массива, соответствующий цветовой модели RGB (Red, Green, Blue — красный, зеленый, синий), в монохромный 8-разрядный пиксел. Единственная прагма,  вставленная непосредственно перед циклом, — это все, что нужно в ОреnМР для параллельного выполнения.

#pragma omp parallel for

for ( i - 0; i < numPixels; i++)

{

pGrayScaleBitmap[i] = (unsigned BYTE)

( pRGBB1tmap[i].red * 0.299 +

pRGBBitmap[i].green * 0.587 +

pRGBB1tmap[i].blue * 0.114 );

}

Рассмотрим цикл внимательнее. В первую очередь обратите внимание, что в примере имеет место разделение работы — этим термином в ОреnМР описывают распределение работы между программными потоками.

Когда разделение работы происходит с помощью конструкции for (как  в  данном примере), то итерации цикла  распределяются между несколькими  потоками. При этом реализация ОреnМР сама определяет, сколько потоков нужно создать и как лучше ими управлять. Программисту достаточно просто  сообщить ОреnМР, какой цикл нужно обрабатывать с помощью потоков. То есть программисту, чтобы добиться параллелизма, нет нужды писать код для  создания, инициализации, управления и завершения потоков. Компилятор ОреnМР и библиотека времени выполнения сами позаботятся об этом и о многих других деталях.

В текущей спецификации ОреnМР версии 2.5 устанавливаются следующие пять ограничений на поточный цикл:

•  Переменная цикла должна быть целым со знаком. Целые без знака не  работают (это ограничение планируется устранить в будущей  спецификации ОреnМР версии 3.0).

•  Операция сравнения должна иметь форму loop_variable.

•  Третье выражение (та часть, где инкрементируется переменная цикла for) должна быть либо целым сложением, либо целым вычитанием значения, не зависящего от итерации цикла.

•  Если операцией сравнения является < или <=, то переменная цикла должна инкрементироваться при каждой итерации; и наоборот, если операцией сравнения является > или >=, то переменная цикла должна декрементироваться при каждой итерации.

•  Цикл должен иметь единственную точку входа и единственную точку  выхода, а это означает, что не разрешаются переходы изнутри цикла наружу или снаружи внутрь, исключая применение инструкции exit, которая  завершает все приложение. При использовании инструкции goto или break она должна выполнять переход внутри цикла, а не наружу. То же самое относится к обработке исключений — они должны перехватываться внутри цикла.

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

Перечисленные ограничения нужно  соблюдать для того, чтобы компилятор мог обеспечить параллельную обработку цикла средствами ОреnМР.

4.1 Проблемы поточной обработки цикла

Поточная обработка цикла означает превращение независимых итераций цикла в программные потоки и  выполнение этих потоков параллельно. В некотором смысле это переупорядочивание, при котором исходный порядок следования итераций цикла может стать неопределенным. Кроме того, поскольку тело цикла не является атомарной операцией, инструкции двух разных итераций могут выполняться одновременно. В теории последовательный цикл можно преобразовать в поточный, если в цикле нет зависимостей. Поэтому при добавлении OpenMP-прагм первой проблемой станет выявление и реструктуризация «горячих» циклов таким образом, чтобы они не имели зависимостей но данным между итерациями цикла.

4.2 Условия гонок

Условия гонок могут быть результатом выходных зависимостей, когда несколько программных потоков  пытаются обновить одну и ту же область памяти (или переменную). В общем случае компиляторы C++ и Fortran выполняют прагмы или директивы стандарта ОреnМР, когда встречают их при компиляции, однако компилятор не выявляет условий гонок (или игнорирует их). Таким образом, цикл, показанный в  следующем примере (в котором несколько программных потоков обновляют переменную х), приведет к нежелательным результатам. В подобной ситуации код необходимо изменить путем приватизации или синхронизации, используя  механизмы наподобие мьютексов. Например, вы можете просто добавить  предложения private(x) к прагме parallel for, устранив в этом цикле условия гонок для переменной х.

// Для переменной х существуют условия гонок;

// устранить их можно  с помощью предложения private(x).

#pragma omp parallel for

for ( k - 0; k < 80; k++ )

{

x = sin(k*2.0)*100 + 1;

if ( x > 60 ) x - x % 60 + 1;

printf ( "x %6 - Xd\n\ k. x );

}

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

Однако в случае ОреnМР условия  гонок легко не заметить. Одна из утилит, которые могут помочь распознать такие ситуации, — это Intel® Thread Checker, входящая в состав Intel VTune™ Performance Analyzer.

4.3 Управление общими и приватными данными

При написании многопоточных программ понимание того, какие данные  являются общими, а какие остаются приватными, становится исключительно  важным — не только с точки зрения производительности, но и с точки зрения правильности программы. ОреnМР делает эту разницу очевидной для программиста при помощи целого набора предложений, таких как shared, private и default, причем это тот аспект, который можно настроить вручную. При использовании ОреnМР именно разработчик указывает компилятору, какие области памяти должны быть для потоков общими, а какие должны оставаться приватными.

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

По умолчанию все переменные в параллельной области являются общими, но есть три исключения. Во-первых, в циклах рага 11 el for индекс цикла является приватным. В следующем примере переменная к — приватная. Во-вторых, переменные, являющиеся локальными для параллельной области, также являются приватными. И, в-третьих, любые переменные, перечисленные в предложении private, firstprivate, lastprivate или reduction, также являются приватными.

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