u_course

Функция возвращает число процессоров в компьютере.

int omp_get _thread_num (void);

Функция возвращает номер вызывающего потока в текущей группе потоков. Функция возвращает значение в диапазоне от 0 до

omp_get_num_threads - 1.

int omp_get_num_threads (void);

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

int omp_set_num_threads (int num_threads);

Функция задает число потоков для выполнения следующей параллельной области, которая встретится текущему выполняемому потоку. Переменная num_threads – число потоков.

int omp_get_max_threads (void);

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

Число потоков, используемых для выполнения параллельных областей, зависит от двух других параметров среды OpenMP: поддержки динамического создания потоков и вложения областей.

Поддержка динамического создания потоков определяется значением параметра булевого типа, который по умолчанию равен false. Если при входе потока в параллельную область этот параметр имеет значение false, исполняющая среда OpenMP создает группу, число потоков в которой равно значению, возвращаемому функцией omp_get_max_threads(). По умолчанию omp_get_max_threads() возвращает число потоков, поддерживаемых аппаратно, или значение переменной OMP_NUM_THREADS. Если поддержка динамического создания потоков включена, исполняющая среда OpenMP создаст группу, которая может содержать переменное число потоков, не превышающее значение, которое возвращается функцией omp_get_max_threads().

Вложение параллельных областей также определяется булевой пере-

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

Функция устанавливает параметр булевого типа, отвечающий за возможность динамического создания потоков. Если переменная dynamic_threads имеет значение true – то потоки создаются динамически, в противном случае создается фиксированное число потоков.

int omp_get _dynamic (void);

Функция возвращает текущее значение параметра, отвечающего за возможность динамического создания потоков.

void omp_set_nested (int nested_threads);

Функция устанавливает параметр булевого типа, отвечающий за возможность вложения параллельных областей. Если переменная nested_threads имеет значение true – то во вложенных параллельных областях создаются новые нити, в противном случае новых нитей не создается.

int omp_ get _ nested (void):

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

Следующий пример демонстрирует использование функций исполняющей среды OpenMP.

#include <stdio.h> #include <omp.h>

int main()

{

printf("Количество процессоров в системе = %d\n", omp_get_num_procs()); omp_set_dynamic(1);

omp_set_num_threads(10);

#pragma omp parallel // параллельная область 1

{

#pragma omp single

printf("Число нитей в динамической области = %d\n", omp_get_num_threads());

}

printf("\n");

omp_set_dynamic(0); omp_set_num_threads(10);

#pragma omp parallel // параллельная область 2

{

#pragma omp single

printf("Число нитей в нединамической области = %d\n", omp_get_num_threads());

}

printf("\n");

omp_set_dynamic(1); omp_set_num_threads(10);

#pragma omp parallel // параллельная область 3

{

#pragma omp parallel

{

#pragma omp single

printf("Вложение областей отключено, число нитей = %d\n", omp_get_num_threads());

}

}

printf("\n");

omp_set_nested(1);

#pragma omp parallel // параллельный регион 4

{

#pragma omp parallel

{

#pragma omp single

printf("Вложение областей включено, число нитей = %d\n", omp_get_num_threads());

}

}

}

В примере реализованы четыре отдельных параллельных области и две вложенных. Скомпилировав этот код и выполнив его на обычном двухпроцессорном компьютере, мы получили такой результат:

Количество процессоров в системе = 2 Число нитей в динамической области = 2 Число нитей в нединамической области = 10

Вложение областей отключено, число нитей = 1 Вложение областей отключено, число нитей = 1

Вложение областей включено, число нитей = 2 Вложение областей включено, число нитей = 2

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

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

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

Следующий пример аналогичен предыдущему коду создания третьей и четвертой параллельных областей, но динамическое создание потоков отключено:

omp_set_dynamic(0); omp_set_nested(1); omp_set_num_threads(10);

#pragma omp parallel { #pragma omp parallel

{

#pragma omp single

printf("Число нитей во вложенной области = %d\n", omp_get_num_threads());

}

}

В этом случае для первой параллельной области создается группа из 10 потоков, затем при входе во вложенную параллельную область для каждого из этих 10 потоков создается группа также из 10 потоков. В общей сложности вложенная параллельная область выполняют 100 потоков:

Число нитей во вложенной области = 10 Число нитей во вложенной области = 10 Число нитей во вложенной области = 10 Число нитей во вложенной области = 10 Число нитей во вложенной области = 10 Число нитей во вложенной области = 10 Число нитей во вложенной области = 10 Число нитей во вложенной области = 10 Число нитей во вложенной области = 10 Число нитей во вложенной области = 10

Алгоритмы планирования

По умолчанию в OpenMP для планирования параллельного выполнения циклов for применяется алгоритм, называемый статическим планированием (static scheduling). Это означает, что все потоки из группы выполняют одинаковое число итераций цикла. Если n – число итераций цикла, а T — число потоков в группе, каждый поток выполнит n/T итераций. Однако OpenMP поддерживает и другие механизмы планирования, оптимальные в разных ситуа-

циях: динамическое планирование (dynamic scheduling), планирование в период выполнения (runtime scheduling) и управляемое планирование (guided scheduling).

Для определения механизма планирования используется раздел schedule в директивах #pragma omp for или #pragma omp parallel for. Формат этого раздела выглядит следующим образом:

schedule(алгоритм планирования[, число итераций])

Здесь параметр алгоритм планирования может принимать одно из следующих значений: dynamic, guided, runtime. Параметр число итераций устанавливает порцию итераций цикла, единовременно отводимую каждому потоку.

При динамическом планировании (dynamic) каждый поток выполняет указанное число итераций. Если это число не задано, по умолчанию оно равно 1. После того как поток завершит выполнение заданных итераций, он переходит к следующему набору итераций. Так продолжается, пока не будут пройдены все итерации. Последний набор итераций может быть меньше, чем изначально заданный. Такой подход к выполнению цикла напоминает алгоритм «портфель задач», рассмотренный в главе 2.

При управляемом планировании (guided) число итераций, выполняемых каждым потоком, определяется по следующей формуле:

число_выполняемых_потоком_итераций =

max (число_нераспределенных_итераций/omp_get_num_threads(),

число итераций)

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

Ниже приведены примеры использования директивы schedule, которые выполняют распараллеленные циклы по 100 итераций с разными алгоритмами планирования:

#pragma omp parallel for schedule(dynamic, 15) for(int i = 0; i < 100; ++i)

...

#pragma omp parallel for schedule(guided, 15) for(int i = 0; i < 100; ++i)

...

Например, при наличии четырех потоков директива

#pragma omp for schedule(dynamic,15) для цикла for из 100 итераций может быть

выполнена следующим образом:

Поток 0 получает право на выполнение итераций 1-15 Поток 1 получает право на выполнение итераций 16-30 Поток 2 получает право на выполнение итераций 31-45 Поток 3 получает право на выполнение итераций 46-60 Поток 2 завершает выполнение итераций Поток 2 получает право на выполнение итераций 61-75

Поток 3 завершает выполнение итераций Поток 3 получает право на выполнение итераций 76-90 Поток 0 завершает выполнение итераций

Поток 0 получает право на выполнение итераций 91-100

Для этого же набора потоков директива #pragma omp for schedule(guided,15) распределит итерации цикла, например, следующим образом:

Поток 0 получает право на выполнение итераций 1-25 Поток 1 получает право на выполнение итераций 26-44 Поток 2 получает право на выполнение итераций 45-59 Поток 3 получает право на выполнение итераций 60-64 Поток 2 завершает выполнение итераций Поток 2 получает право на выполнение итераций 65-79 Поток 3 завершает выполнение итераций

Поток 3 получает право на выполнение итераций 80-94 Поток 2 завершает выполнение итераций Поток 2 получает право на выполнение итераций 95-100

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

Планирование в период выполнения (runtime) – это скорее даже не алгоритм планирования, а способ динамического выбора одного из трех описанных алгоритмов. Если в разделе schedule указан параметр runtime, исполняющая среда OpenMP использует алгоритм планирования, заданный для конкретного цикла for при помощи переменной OMP_SCHEDULE. Она имеет фор-

мат «тип[,число итераций]», например: set OMP_SCHEDULE=dynamic,8

Планирование в период выполнения дает определенную гибкость в выборе типа планирования, при этом по умолчанию применяется статическое планирование.

Оптимизация программ OpenMP

Ограничение на ускорение, связанное с распараллеливанием алгоритма дает закон Амдала. Предположим, что в программе доля операций, которые нужно выполнять последовательно, равна f, где 0<=f<=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам. Для того,

чтобы оценить, какое ускорение S может быть получено на компьютере из p процессоров при данном значении f, можно воспользоваться законом Амдала:

S ≤ 1 / (f+(1-f)/p)

Например, если 9/10 программы исполняется параллельно, а 1/10 попрежнему последовательно, то ускорения более, чем в 10 раз, получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (ясно, что 10 получается только в том случае, когда время исполнения параллельной части равно пренебрежимо мало)1.

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

Поэтому при программировании с использованием OpenMP желательно придерживаться следующих рекомендаций:

не создавать параллельные секции без необходимости, т.е. нет смысла распараллеливать сложение 10-ти чисел;

избегать лишних точек синхронизации, по возможности использо-

вать nowait;

минимизировать количество общих данных.

В таблице указаны ориентировочные уровни затрат в тактах на различные операции.

Таблица 5.2 Уровни затрат производительности в различных случаях

1 Посмотрим на проблему с другой стороны: какую часть кода надо ускорить, чтобы получить заданное ускорение? Ответ можно найти в следствии закона Амдала: для того чтобы ускорить выполнение программы

в q раз необходимо ускорить не менее, чем в q раз не менее, чем (1-1/q)-ю часть программы. Следователь-

но, если есть желание ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить ускорение в 100 раз не менее, чем на 99.99% кода!

Компиляция программ

Реализация OpenMP в С и С++ по большей части возложена на компилятор, поэтому полнота реализации стандарта и дополнительные возможности немного различаются в разных компиляторах. На сегодняшний день, наиболее распространенными компиляторами, поддерживающими OpenMP,

являются Intel C Compiler 10, Sun C Compiler, GNU C Compiler 4.2. Далее бу-

дет рассмотрена компиляция программ с помощью компилятора GNU . Опция компилятора -openmp активизирует реализованные в компилято-

ре средства OpenMP. Команда компиляция программмы будет выглядеть примерно следующим образом:

g++ <файл с исходным кодом> -o <исполняемый файл> -openmp

Вслучае включения опции -openmp компилятор определяет символ _OPENMP, с помощью которого можно выяснить, включены ли средства

OpenMP.

Если в программе используются функции OpenMP то необходимо подключить заголовочный файл <omp.h>.

Вобщем случае OpenMP-программа будет выглядеть следующим обра-

зом:

#include <omp.h> #ifdef _OPENMP

// часть программы, работающая только в случае компиляции с OpenMP

#endif

// программа

Ограничения OpenMP

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