OpenMP и C++.
Введение.
Компьютерный зоопарк.
Последние годы связаны с резким изменением направления развития процессоров — появления многоядерных и многопоточных процессоров.
Последние 10 лет прошли под знаком беспрецедентного роста процессорных ядер.
Накоплен бесценный опыт на многоядерных машинах. Рассмотрим некоторые подходы к ускорению на кластерах.
Первую скрипку играет OpenMP, но он работает на одном узле, т. к. OpenMP использует общую память.
Нами рассмотрены 3 случая расширения общей памяти:
- SendRecv;
- Shmem;
- Односторонние сообщения MPI.
Прилагаются примеры 3-х случаев. Но, для начала рассмотрим, как работает OpenMP.
Реализация многопоточности без лишних усилий.
Среди специалистов, занимающихся параллельными вычислениями, популярна шутка «Параллельные вычисления — технология будущего… и так будет всегда». Эта шутка не теряет актуальность уже несколько десятилетий. Аналогичные настроения были распространены в сообществе разработчиков архитектур компьютеров, обеспокоенном тем, что скоро будет достигнут предел тактовой частоты процессоров, однако частоты процессоров продолжают повышаться, хотя гораздо медленнее, чем раньше. Сплав оптимизма специалистов по параллельным вычислениям и пессимизма архитекторов систем способствовал появлению революционных многоядерных процессоров.
Главные производители процессоров сместили акцент с повышения тактовых частот на реализацию параллелизма в самих процессорах за счет использования многоядерной архитектуры. Идея проста: интегрировать в один процессор более одного ядра. Система, включающая процессор с двумя ядрами, по сути, не отличается от двухпроцессорного компьютера, а система с четырехядерным процессором — от четырехпроцессорного. Этот подход позволяет избежать многих технологических проблем, связанных с повышением тактовых частот, и создавать при этом более производительные процессоры.
Все это прекрасно, но если ваше приложение не будет использовать несколько ядер, его быстродействие никак не изменится. Именно здесь и вступает в игру технология OpenMP, которая помогает программистам на C++ быстрее создавать многопоточные приложения.
Подробно описать OpenMP в одной статье просто немыслимо, так как это очень объемный и мощный API. Рассматривайте эту статью как введение, где демонстрируется применение различных средств OpenMP для быстрого написания многопоточных программ. Если вам понадобится дополнительная информация по этой тематике, мы рекомендуем обратиться к спецификации, доступной на сайте OpenMP, — она на удивление легко читается.
Параллельная обработка в OpenMP.
Работа OpenMP-приложения начинается с единственного потока — основного. В приложении могут содержаться параллельные регионы, входя в которые, основной поток создает группы потоков (включающие основной поток). В конце параллельного региона группы потоков останавливаются, а выполнение основного потока продолжается. В параллельный регион могут быть вложены другие параллельные регионы, в которых каждый поток первоначального региона становится основным для своей группы потоков. Вложенные регионы могут в свою очередь включать регионы более глубокого уровня вложенности.
Конструкции OpenMP.
OpenMP прост в использовании и включает лишь два базовых типа конструкций: директивы pragma и функции исполняющей среды OpenMP. Директивы pragma, как правило, указывают компилятору реализовать параллельное выполнение блоков кода. Все эти директивы начинаются с #pragma omp. Как и любые другие директивы pragma, они игнорируются компилятором, не поддерживающим конкретную технологию — в данном случае OpenMP.
Для реализации параллельного выполнения блоков приложения нужно просто добавить в код директивы pragma и, если нужно, воспользоваться функциями библиотеки OpenMP периода выполнения. Директивы pragma имеют следующий формат:
#pragma omp <директива> [раздел [ [,] раздел]...]
OpenMP поддерживает директивы parallel, for, parallel for, section, sections, single, master, critical, flush, ordered и atomic, которые определяют или механизмы разделения работы или конструкции синхронизации. В этой статье мы обсудим большинство директив.
Реализация параллельной обработки.
Хотя директив OpenMP много, все они сразу нам не понадобятся. Самая важная и распространенная директива — parallel. Она создает параллельный регион для следующего за ней структурированного блока, например:
#pragma omp parallel [раздел[ [,] раздел]...] структурированный блок
Эта директива сообщает компилятору, что структурированный блок кода должен быть выполнен параллельно, в нескольких потоках. Каждый поток будет выполнять один и тот же поток команд, но не один и тот же набор команд — все зависит от операторов, управляющих логикой программы, таких как if-else.
В качестве примера рассмотрим классическую программу «Hello World»:
#pragma omp parallel
{
printf("Hello World\n");
}
В двухпроцессорной системе вы, конечно же, рассчитывали бы получить следующее:
Hello World Hello World
Тем не менее, результат мог бы оказаться и таким:
HellHell oo WorWlodrl d
Давайте взглянем на более серьезный пример, который определяет средние значения двух соседних элементов массива и записывает результаты в другой массив. В этом примере используется новая для вас OpenMP-конструкция #pragma omp for, которая относится к директивам разделения работы (work- sharing directive). Такие директивы применяются не для параллельного выполнения кода, а для логического распределения группы потоков, чтобы реализовать указанные конструкции управляющей логики. Директива #pragma omp for сообщает, что при выполнении цикла for в параллельном регионе итерации цикла должны быть распределены между потоками группы:
#pragma omp parallel
{
#pragma omp for
for(int i = 1; i < size; ++i)
x[i] = (y[i-1] + y[i+1])/2;
}
Если бы этот код выполнялся на четырехпроцессорном компьютере, а у переменной size было бы значение 100, то выполнение итераций 1—25 могло бы быть поручено первому процессору, 26— 50 — второму, 51—75 — третьему, а 76—99 — четвертому. Это характерно для политики планирования, называемой статической. Политики планирования мы обсудим позднее.
Следует отметить, что в конце параллельного региона выполняется барьерная синхронизация (barrier synchronization). Иначе говоря, достигнув конца региона, все потоки блокируются до тех пор, пока последний поток не завершит свою работу.
Так как циклы являются самыми распространенными конструкциями, где выполнение кода можно распараллелить, OpenMP поддерживает сокращенный способ записи комбинации директив #pragma omp parallel и #pragma omp for:
#pragma omp parallel for
for(int i = 1; i < size; ++i)
x[i] = (y[i-1] + y[i+1])/2;
Обратите внимание, что в этом цикле нет зависимостей, т. е. одна итерация цикла не зависит от результатов выполнения других итераций. А вот в двух следующих циклах есть два вида зависимости:
for(int i = 1; i <= n; ++i) // цикл 1
a[i] = a[i-1] + b[i];
for(int i = 0; i < n; ++i) // цикл 2
x[i] = x[i+1] + b[i];
Распараллелить цикл 1 проблематично потому, что для выполнения итерации i нужно знать результат итерации i-1, т. е. итерация i зависит от итерации i-1. Распараллелить цикл 2 тоже проблематично, но по другой причине. В этом цикле вы можете вычислить значение x[i] до x[i-1], однако, сделав так, вы больше не сможете вычислить значение x[i-1]. Наблюдается зависимость итерации i-1 от итерации i.
При распараллеливании циклов вы должны убедиться в том, что итерации цикла не имеют зависимостей. Если цикл не содержит зависимостей, компилятор может выполнять цикл в любом порядке, даже параллельно. Соблюдение этого важного требования компилятор не проверяет — вы сами должны заботиться об этом. Если вы укажете компилятору распараллелить цикл, содержащий зависимости, компилятор подчинится, что приведет к ошибке.
Общие и частные данные.
Разрабатывая параллельные программы, вы должны понимать, какие данные являются общими (shared), а какие частными (private), — от этого зависит не только производительность, но и корректная работа программы. В OpenMP это различие очевидно, к тому же вы можете настроить его вручную.
Общие переменные доступны всем потокам из группы, поэтому изменения таких переменных в одном потоке видимы другим потокам в параллельном регионе. Что касается частных переменных, то каждый поток из группы располагает их отдельными экземплярами, поэтому изменения таких переменных в одном потоке никак не сказываются на их экземплярах, принадлежащих другим потокам.
Директивы pragma для синхронизации.
При одновременном выполнении нескольких потоков часто возникает необходимость их синхронизации. OpenMP поддерживает несколько типов синхронизации, помогающих во многих ситуациях.
Один из типов — неявная барьерная синхронизация, которая выполняется в конце каждого параллельного региона для всех сопоставленных с ним потоков. Механизм барьерной синхронизации таков, что, пока все потоки не достигнут конца параллельного региона, ни один поток не сможет перейти его границу.
Неявная барьерная синхронизация выполняется также в конце каждого блока #pragma omp for, #pragma omp single и #pragma omp sections. Чтобы отключить неявную барьерную синхронизацию в каком-либо из этих трех блоков разделения работы, укажите раздел nowait:
#pragma omp parallel
{
#pragma omp for nowait
for(int i = 1; i < size; ++i)
x[i] = (y[i-1] + y[i+1])/2;
}
Как видите, этот раздел директивы распараллеливания говорит о том, что синхронизировать потоки в конце цикла for не надо, хотя в конце параллельного региона они все же будут синхронизированы.
Второй тип — явная барьерная синхронизация. В некоторых ситуациях ее целесообразно выполнять наряду с неявной. Для этого включите в код директиву #pragma omp barrier.
Подпрограммы исполняющей среды OpenMP.
Помимо уже описанных директив OpenMP поддерживает ряд полезных подпрограмм. Они делятся на три обширных категории: функции исполняющей среды, блокировки/синхронизации и работы с таймерами (последние в этой статье не рассматриваются). Все эти функции имеют имена, начинающиеся с omp_, и определены в заголовочном файле omp.h.
Подпрограммы первой категории позволяют запрашивать и задавать различные параметры операционной среды OpenMP. Функции, имена которых начинаются на omp_set_, можно вызывать только вне параллельных регионов. Все остальные функции можно использовать как внутри параллельных регионов, так и вне таковых.
Методы синхронизации/блокировки.
OpenMP включает и функции, предназначенные для синхронизации кода. В OpenMP два типа блокировок: простые и вкладываемые (nestable); блокировки обоих типов могут находиться в одном из трех состояний — неинициализированном, заблокированном и разблокированном.
Простые блокировки (omp_lock_t) не могут быть установлены более одного раза, даже тем же потоком. Вкладываемые блокировки (omp_nest_lock_t) идентичны простым с тем исключением, что, когда поток пытается установить уже принадлежащую ему вкладываемую блокировку, он не блокируется. Кроме того, OpenMP ведет учет ссылок на вкладываемые блокировки и следит за тем, сколько раз они были установлены.
OpenMP предоставляет подпрограммы, выполняющие операции над этими блокировками. Каждая такая функция имеет два варианта: для простых и для вкладываемых блокировок. Вы можете выполнить над блокировкой пять действий: инициализировать ее, установить (захватить), освободить, проверить и уничтожить. Все эти операции очень похожи на Win32-функции для работы с критическими секциями, и это не случайность: на самом деле технология OpenMP реализована как оболочка этих функций.
Когда использовать OpenMP.
Знать, когда использовать технологию OpenMP, не менее важно, чем уметь с ней работать. Надеемся, что наши советы вам помогут.
Целевая платформа является многопроцессорной или многоядерной. Если приложение полностью использует ресурсы одного ядра или процессора, то, сделав его многопоточным при помощи OpenMP, вы почти наверняка повысите его быстродействие.
Приложение должно быть кроссплатформенным. OpenMP — кроссплатформенный и широко поддерживаемый API. А так как он реализован на основе директив pragma, приложение можно скомпилировать даже при помощи компилятора, не поддерживающего стандарт OpenMP.
Выполнение циклов нужно распараллелить. Весь свой потенциал OpenMP демонстрирует при организации параллельного выполнения циклов. Если в приложении есть длительные циклы без зависимостей, OpenMP — идеальное решение.
Перед выпуском приложения нужно повысить его быстродействие. Так как технология OpenMP не требует переработки архитектуры приложения, она прекрасно подходит для внесения в код небольших изменений, позволяющих повысить его быстродействие.
В то же время следует признать, что OpenMP — не панацея от всех бед. Эта технология ориентирована в первую очередь на разработчиков высокопроизводительных вычислительных систем и наиболее эффективна, если код включает много циклов и работает с разделяемыми массивами данных.
Простейшая модельная программа.
Рассказывать о составе и назначении программного обеспечения суперкомпьютеров лучше всего на конкретном примере. Выберем модельную программу, спланируем «на бумаге» ее параллельную реализацию, а затем – посмотрим, какого рода программное обеспечение нам потребуется, чтобы выполнить эту параллельную реализацию на суперкомпьютере вообще, и на кластере рабочих станций – в частности.
1. Решение двумерной краевой задачи для уравнения теплопроводности методом Якоби. Физика задачи: рассмотрим однородный прямоугольный параллелепипед («кирпич»), к боковым граням которого плотно прислонены «утюги» бесконечной массы и заданной температуры. По мере прогрева «кирпича» в нем установится некоторое распределение температуры, которое нам и требуется найти. Будем рассматривать двумерное приближение задачи. Это значит, что кирпич предполагается очень высоким, и нас будет интересовать распределение температуры в его горизонтальном срезе, достаточно удаленном как от верхней, так и от нижней грани. Для краткости будем далее называть эту задачу «задачей о прогреве кирпича». Подчеркнем, что ни физическая, ни вычислительно – математическая сторона этой прекрасно изученной задачи нас не интересует – мы рассматриваем ее как пример заданной и не обсуждаемой вычислительной процедуры, для которой надо построить параллельную реализацию. Данная задача является краевой задачей для уравнения в частных производных (уравнения теплопроводности), которую можно приблизить задачей на равномерной четырехугольной сетке. Сеточную задачу, в свою очередь, можно решать итерационным методом – мы выберем метод Якоби. Численный метод, к которому мы приходим, двигаясь упомянутым путем, очень прост. Имеется двумерный массив F, значения элементов которого – это нормализованные значения температуры в узлах сетки, «наброшенной» на срез кирпича. По краям массива находятся значения температуры утюгов – граничные условия. Они в процессе расчета не изменяются. Со всеми остальными значениями поступаем так:
- для каждой ячейки вычисляем новое значение как среднее арифметическое значений четырех ее соседей,
- после того, как новые значения вычислены для всех ячеек, заменяем старые значения новыми, попутно вычисляя максимум абсолютной величины отклонения новых значений от старых,
- повторяем эти два шага до тех пор, пока максимум абсолютной величины отклонения не станет меньше заданного порога малости.
Для упрощения наших модельных рассмотрений исключим из алгоритма вычисление отклонений – будем просто выполнять фиксированное число итераций. Вот текст последовательной (для одного процессора) реализации этой вычислительной процедуры:
#include <stdio.h>
/***/
#define MX 640
#define MY 480
#define NITER 10000
#define STEPITER 100
static float f[MX][MY];
static float df[MX][MY];
/***/
int main( int argc, char **argv )
{
int i, j, n, m;
FILE *fp;
/***/
printf( "Solving heat conduction task on %d by %d grid\n",
MX, MY );
fflush( stdout );
/* Initial conditions: */
for ( i = 0; i < MX; i++ )
{
for ( j = 0; j < MY; j++ )
{
f[i][j] = df[i][j] = 0.0;
if ( (i == 0)
|| (j == 0) ) f[i][j] = 1.0;
else if ( (i == (MX-1))
|| (j == (MY-1)) ) f[i][j] = 0.5;
}
}
/* Iteration loop: */
for ( n = 0; n < NITER; n++ )
{
if ( !(n%STEPITER) ) printf( "Iteration %d\n", n );
/* Step of calculation starts here: */
for ( i = 1; i < (MX-1); i++ )
{
for ( j = 1; j < (MY-1); j++ )
{
df[i][j] = ( f[i][j+1] + f[i][j-1] + f[i-1][j] + f[i+1][j] )
* 0.25 - f[i][j];
}
}
for ( i = 1; i < (MX-1); i++ )
{
for ( j = 1; j < (MY-1); j++ )
{
f[i][j] += df[i][j];
}
}
}
/* Calculation is done, F array is a result: */
fp = fopen( "progrev.dat", "w" );
for ( i = 1; i < (MX-1); i++ )
fwrite( f[i]+1, MY-2, sizeof(f[0][0]), fp );
fclose( fp );
return 0;
}
Продолжение следует.
Примеры.