Использование локальных данных для уменьшения объема синхронизации

Скачать статью Use Thread-local Storage to Reduce Synchronization [Eng., PDF 241KB]

Аннотация

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

Введение

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

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

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

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

 

int count=0;
#pragma omp parallel shared(count)
{
 . . .
 if (event_happened) {
#pragma omp atomic
 count++;
}
. . .
}

 

В данной программе каждый раз, когда происходит событие, появляются некоторые издержки, потому что необходима синхронизация для гарантии того, что за раз только один поток увеличивает переменную count. То есть каждое событие вызывает синхронизацию. Удаление синхронизации позволит программе работать быстрее. Одним из способов ее удаления является включение в каждый поток локального счетчика событий, который работает в параллельной области кода, а затем суммирование всех счетчиков. Этот метод продемонстрирован в следующем примере:

 

int count=0;
int tcount=0;
#pragma omp threadprivate(tcount)

omp_set_dynamic(0);

#pragma omp parallel 
{
. . .
 if (event_happened) {
 tcount++;
 }
 . . .
}
#pragma omp parallel shared(count)
{
#pragma omp atomic
 count += tcount;
}

 

Здесь используется переменная tcount, локальная для каждого потока, которая хранит данные счетчика. Когда в первой параллельной секции рассчитаны все локальные события, на следующем параллельном участке все счетчики складываются в один общий. Данный метод изменил синхронизацию на каждом событии на синхронизацию на каждом потоке. Производительность повысится в том случае, если количество событий намного больше количества потоков. Отметим, что в программе подразумевается, что обе параллельные области работают с одинаковым числом потоков. Вызов функции omp_set_dynamic(0) гарантирует, что количество потоков будет ровно таким, как требуется программе.

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

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

 

#include 

pthread_key_t tsd_key;
 value;


if( pthread_key_create(&tsd_key, NULL) ) err_abort(status, “Error creating key”);
if( pthread_setspecific( tsd_key, value)) 
 err_abort(status, “Error in pthread_setspecific”);
. . .
value = ()pthread_getspecific( tsd_key );


With Windows threads, the operation is very similar. The programmer allocates a TLS index with TlsAlloc, then uses that index to set a thread-local value. For example:

DWORD tls_index;
LPVOID value;

tls_index = TlsAlloc();
if (tls_index == TLS_OUT_OF_INDEXES) err_abort( tls_index, “Error in TlsAlloc”);
status = TlsSetValue( tls_index, value );
if ( status == 0 ) err_abort( status, “Error in TlsSetValue”);
 . . .
value = TlsGetValue( tls_index );

 

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

Рекомендации

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

Рассмотрим следующий код, в котором потоки пишут данные в общий буфер:

 

int buffer[NENTRIES];

main() {

 . . .

#pragma omp parallel
{
 . . .
 update_log(time, value1, value2);
 . . .
}

 . . . 
}
void update_log(time, value1, value2)
{
 #pragma omp critical
 {
 if (current_ptr + 3 > NENTRIES) { print_buffer_overflow_message(); }

 buffer[current_ptr] = time;
 buffer[current_ptr+1] = value1;
 buffer[current_ptr+2] = value2;
 current_ptr += 3;
 }
}

 

Предположим, что time является монотонно возрастающей величиной и единственным реальным требованием к буферу является то, что он, отсортированный по времени, иногда сохраняется в файл. Синхронизацию в процедуре update_logможно отменить с помощью применения локальных буферов потоков. Каждый поток создает себе локальную копию tpbuffer и tpcurrent_ptr. Это позволяет убрать критическую секцию в update_log. Содержимое локальных буферов можно объединить позднее, согласно значениям времени, в некритичной ко времени выполнения части программы.

Метод использования

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

  • Во-первых, определите, действительно ли синхронизация так сильно тормозит выполнение программы. Для проверки всех частей кода на присутствие проблем производительности можно использовать Intel® Parallel Amplifier и/или Intel® VTune ™ Performance Analyzer.
  • Во-вторых, определите, является ли упорядочение операций во времени важным для работы программы. Если нет, то синхронизацию можно убрать, как в примере со счетчиком событий. Если упорядочение во времени необходимо, то можно ли порядок восстановить позднее?
  • В-третьих, проверьте, не приведёт ли перемещение точки синхронизации к аналогичным проблемам на новом месте. Один из способов проверки – показать, что на новом месте объём синхронизации будет существенно меньше (как в приведенном примере со счетчиком событий).

Дополнительные материалы

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