Эффективное распределение нагрузки между потоками с помощью OpenMP*

Краткое содержание

Как известно, OpenMP* представляет собой многофункциональный набор прагм, с помощью которых можно распараллелить циклы. Однако применение OpenMP этим не ограничивается: например, если использование конструкции "parallel for" не совсем подходит, можно воспользоваться дополнительными прагмами, конструкциями и вызовами функций OpenMP.

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

Конструкция Parallel

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

#pragma omp parallel for 
for (i=0; i<x; i++)     
fn1(); 
#pragma omp parallel for 
// adds unnecessary overhead
for (i=0; i<y; i++) 
fn2(); 

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

#pragma omp parallel  
{ 
#pragma omp for  
for (i=0; i<x; i++) 
fn1(); 
#pragma omp for  
for (i=0; i<y; i++)  
fn2();
} 

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

Конструкция Sections

Конструкция sections используется для объявления разделов программного кода, выполнение которых необходимо распределить между несколькими потоками. Рассмотрим пример, в котором организовано распределение циклов и нециклических разделов кода между потоками:

#pragma omp parallel     
{ 
#pragma omp for 
for (i=0; i<x; 
i++)
Fn1(); 
#pragma omp sections  
{ 
#pragma omp section  
{  
TaskA(); 
}  
#pragma omp section 
{ 
TaskB(); 
} 
#pragma omp section 
{ 
TaskC();  
} 
} 

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

Барьеры и оператор Nowait

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

#pragma omp parallel
{ 
#pragma omp for nowait 
for (i=0; i<100; i++) 
compute_something();
#pragma omp for
for (j=0; j<500; j++) 
more_computations(); 
} 

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

Допустима и обратная ситуация – организация барьера (см. ниже):

#pragma omp parallel 
{ 
// A bunch of work...  
#pragma omp barrier 
//Additional work...  
} 

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

Главный поток и дополнительные потоки

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

#pragma omp parallel 
{ 
do_multiple_times();
// every thread calls this function 
#pragma omp for 
for (i=0; i<100;
i++) 
// this loop is divided among the threads 
fn1(); 
// implicit barrier at the end of the above loop  
// will cause all thread to synchronize here  
#pragma omp master 
fn_for_master_only();  
// only the master thread calls this function  
#pragma omp for nowait 
for (i=0; i<100;  
i++)  
// again, loop is divided among threads 
fn2();
// The above loop does not have a barrier, and 
// threads will not wait for each other. One thread,
// hopefully the first one done with the above loop, 
// will continue and execute the code below. 
#pragma omp single 
one_time_any_thread(); 
// any thread will execute this  
} 

Атомарные операции

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

a[i] += x; // may be interrupted half-complete

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

#pragma omp atomic
a[i] += x; // never interrupted because defined
//atomic

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

Expr1++++expr1
Expr1----Expr1
Expr1 += expr2Expr1 -= expr2
Expr1 *= expr2Expr1 /= expr2
Expr1 <<= expr2Expr1 >>= expr2
Expr1 &= expr2Expr1 ^=expr2
Expr1 |= expr2

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

Критические секции

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

#pragma omp critical 
{ 
if (max < new_value) 
max = new_value 
}

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

#pragma omp critical(maxvalue) 
{
if (max < new_value)  
max = new_value  
} 

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

Операторы FirstPrivate и Last Private

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

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

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

for (row=0; row<height; row++) 
{  
for (col=0; col<width; col++) 
{  
pGray[col] = (BYTE) 
(pRGB[row].red * 0.299 + 
pRGB[row].green * 0.587 + 
pRGB[row].blue * 0.114); 
} 
pGray += GrayStride; 
pRGB += RGBStride;  
} 

Как переместить указатели в нужное место внутри растрового изображения? Одним из способов является вычисление адреса для каждой итерации:

pDestLoc = pGray + col + row * GrayStride; 
pSrcLoc = pRGB + col + row * RGBStride; 

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

BOOL FirstTime=TRUE; 
#pragma omp parallel for private (col) 
firstprivate(FirstTime, pGray, pRGB) 
for (row=0; row<height; row++) 
{ 
if (FirstTime == TRUE)  
{  
FirstTime = FALSE; 
pRGB += (row * RGBStride); 
pGray += (row * GrayStride); 
} 
for (col=0; col<width; col++) 
{ 
pGray[col] = (BYTE) (pRGB[row].red * 0.299 + 
pRGB[row].green * 0.587 +  
pRGB[row].blue * 0.114);
} 
pGray += GrayStride; 
pRGB += RGBStride; 
}
} 

Маленькие хитрости

Вопрос: Чем отличаются результаты выполнения циклов, коды которых приведены ниже?

Цикл 1 (с прагмой parallel for):

int i; 
#pragma omp parallel for 
for (i='a'; i<='z'; i++) 
printf ("%c", i);  

Цикл 2 (с прагмой parallel):

int i; 
#pragma omp parallel 
for (i='a'; i<='z'; i++)  
printf ("%c", i); 

Ответ: При выполнении первого цикла на экран однократно будет выведен английский алфавит, а при выполнении второго цикла алфавит будет выведен неопределенное число раз (или столько раз, сколько организовано потоков, если переменная i была объявлена индивидуальной.

Выводы

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

Ссылки

Начало работы с OpenMP*
Программирование OpenMP* для опытных разработчиков (eng)
Спецификация OpenMP: http://www.openmp.org*

Дополнительная информация

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