Барьер (информатика)
В параллельных вычислениях барьер — это тип метода синхронизации . [1] Барьер для группы потоков или процессов в исходном коде означает, что любой поток/процесс должен остановиться в этой точке и не может продолжить работу, пока все другие потоки/процессы не достигнут этого барьера. [2]
Многие коллективные процедуры и параллельные языки, основанные на директивах, накладывают неявные барьеры. Например, параллельный цикл do в Фортране с OpenMP не сможет продолжаться ни в одном потоке, пока не будет завершена последняя итерация. [ нужна цитата ] Это на тот случай, если программа полагается на результат цикла сразу после его завершения. При передаче сообщений любая глобальная коммуникация (например, сокращение или разброс) может подразумевать барьер.
При параллельных вычислениях барьер может находиться в поднятом или опущенном состоянии . Термин « защелка» иногда используется для обозначения барьера, который начинается в поднятом состоянии и не может быть повторно поднят, когда он находится в опущенном состоянии. Термин «защелка обратного отсчета» иногда используется для обозначения защелки, которая автоматически снижается после прибытия заранее определенного количества потоков/процессов.
Реализация [ править ]
Возьмем, к примеру, поток, известный как барьер потока . Барьеру потоков нужна переменная, чтобы отслеживать общее количество потоков, вошедших в барьер . [3] Как только в барьер войдет достаточно нитей, он поднимется. такой Примитив синхронизации, как мьютекс, также необходим при реализации барьера потока.
Этот метод барьера потоков также известен как централизованный барьер , поскольку потоки должны ждать перед «центральным барьером», пока ожидаемое количество потоков не достигнет барьера, прежде чем он будет снят.
Следующий код C, реализующий барьер потоков с помощью потоков POSIX, демонстрирует эту процедуру: [1]
#include <stdio.h>
#include <pthread.h>
#define TOTAL_THREADS 2
#define THREAD_BARRIERS_NUMBER 3
#define PTHREAD_BARRIER_ATTR NULL // атрибут барьера pthread
typedef struct _thread_barrier
{
int thread_barrier_number ;
pthread_mutex_t блокировка ;
ИНТ Total_thread ;
} поток_барьер ;
thread_barrier барьер ;
void thread_barrier_init ( thread_barrier * барьер , pthread_mutexattr_t * mutex_attr , int thread_barrier_number ) {
pthread_mutex_init ( & ( барьер -> блокировка ), mutex_attr );
барьер -> номер_барьера_нити = номер_барьера_нити ;
барьер -> total_thread = 0 ; // Инициализируем общий поток равным 0
}
void thread_barrier_wait ( thread_barrier * барьер ){
if ( ! pthread_mutex_lock ( & ( барьер -> блокировка ))) {
барьер -> total_thread += 1 ;
pthread_mutex_unlock ( & ( барьер -> блокировка ));
}
while ( barrier -> total_thread < barrier -> thread_barrier_number );
if ( ! pthread_mutex_lock ( & ( барьер -> блокировка ))) {
барьер -> total_thread -= 1 ; // Уменьшаем один поток, поскольку он прошел барьер потока
pthread_mutex_unlock ( & ( барьер -> блокировка ));
}
}
void thread_barrier_destroy ( thread_barrier * барьер ) {
pthread_mutex_destroy ( & ( барьер -> замок ));
}
void * thread_func ( void * ptr ){
printf ( "поток с идентификатором %ld ожидает у барьера, так как запущено недостаточно %d потоков... \n " , pthread_self (), THREAD_BARRIERS_NUMBER );
thread_barrier_wait ( & барьер );
printf ( "Барьер снят, поток с идентификатором %ld сейчас запущен \n " , pthread_self ());
}
Int Main ()
{
pthread_t thread_id [ TOTAL_THREADS ];
thread_barrier_init ( & барьер , PTHREAD_BARRIER_ATTR , THREAD_BARRIERS_NUMBER );
for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) {
pthread_create ( & thread_id [ i ], NULL , thread_func , NULL );
}
// Поскольку pthread_join() будет блокировать процесс до тех пор, пока все указанные им потоки не завершатся,
// и у барьера не будет достаточно потоков, чтобы ждать, поэтому этот процесс блокируется
на ( int i = 0 ; i < TOTAL_THREADS ; я ++ ) {
pthread_join ( thread_id [ i ], NULL );
}
thread_barrier_destroy ( & барьер );
printf ( "Потоковый барьер снят \n " ); // Эта строка не будет называться TOTAL_THREADS < THREAD_BARRIERS_NUMBER
}
В этой программе барьер потока определяется как структура struct _thread_barrier, которая включает в себя:
- total_thread: общее количество потоков в процессе.
- thread_barrier_number : общее количество потоков, которые, как ожидается, войдут в барьер потоков, чтобы его можно было снять.
- lock : блокировка мьютекса потока POSIX.
Основываясь на определении барьера, нам нужно реализовать в этой программе такую функцию, как thread_barrier_wait() , которая будет «отслеживать» общее количество потоков в программе, чтобы обеспечить работоспособность барьера.
В этой программе каждый поток, вызывающий thread_barrier_wait(), будет заблокирован до тех пор, пока потоки THREAD_BARRIERS_NUMBER не достигнут барьера потока.
Результатом этой программы является:
идентификатор потока <thread_id, например 139997337872128> ожидает на барьере, так как запущено недостаточно трех потоков...
идентификатор потока <thread_id, например 139997329479424> ожидает на барьере, поскольку запущено недостаточно трех потоков...
// (основной процесс заблокирован из-за недостаточного количества трех потоков)
// Строка printf("Барьер потока снят\n") не будет достигнута
Как мы видим из программы, всего создается всего 2 потока. Оба этих потока имеют thread_func(), как обработчик функции потока, который вызывает thread_barrier_wait(&barrier), в то время как потоковый барьер ожидал вызова 3 потоков thread_barrier_wait ( THREAD_BARRIERS_NUMBER = 3), чтобы его подняли.
Измените TOTAL_THREADS на 3, и барьер потока будет снят:
идентификатор потока <идентификатор потока, например 140453108946688> ожидает на барьере, поскольку запущено недостаточно трех потоков...
идентификатор потока <идентификатор потока, например 140453117339392> ожидает на барьере, поскольку запущено недостаточно трех потоков...
идентификатор потока <идентификатор потока, например 140453100553984> ожидает у барьера, так как запущено недостаточно 3 потоков...
Барьер снят, идентификатор потока <идентификатор потока, например 140453108946688> выполняется сейчас
Барьер снят, идентификатор потока < Идентификатор потока, например 140453117339392>, сейчас выполняется.
Барьер снят, идентификатор потока <идентификатор потока, например, 140453100553984> выполняется сейчас.
Барьер потока снят.
смысла изменения Централизованный барьер
Помимо уменьшения общего числа потоков на единицу для каждого потока, успешно проходящего барьер потока, барьер потока может использовать противоположные значения, чтобы пометить каждое состояние потока как прохождение или остановку. [4] Например, поток 1 со значением состояния 0 означает, что он останавливается у барьера, поток 2 со значением состояния 1 означает, что он прошел барьер, значение состояния потока 3 = 0 означает, что он останавливается у барьера и так далее. [5] Это известно как изменение смысла. [1]
Следующий код C демонстрирует это: [3] [6]
#include <stdio.h>
#include <stdbool.h>
#include <pthread.h>
#define TOTAL_THREADS 2
#define THREAD_BARRIERS_NUMBER 3
#define PTHREAD_BARRIER_ATTR NULL // атрибут барьера pthread
typedef struct _thread_barrier
{
int thread_barrier_number ;
ИНТ Total_thread ;
pthread_mutex_t блокировка ;
логический флаг ;
} поток_барьер ;
thread_barrier барьер ;
void thread_barrier_init ( thread_barrier * барьер , pthread_mutexattr_t * mutex_attr , int thread_barrier_number ) {
pthread_mutex_init ( & ( барьер -> блокировка ), mutex_attr );
барьер -> total_thread = 0 ;
барьер -> номер_барьера_нити = номер_барьера_нити ;
барьер -> флаг = ложь ;
}
void thread_barrier_wait ( thread_barrier * барьер ) {
bool local_sense = барьер -> флаг ;
if ( ! pthread_mutex_lock ( & ( барьер -> блокировка ))) {
барьер -> total_thread += 1 ;
local_sense = ! локальный_смысл ;
if ( барьер -> total_thread == барьер -> номер_барьера потока ) {
барьер -> total_thread = 0 ;
барьер -> флаг = local_sense ;
pthread_mutex_unlock ( & ( барьер -> блокировка ));
} else {
pthread_mutex_unlock ( & ( барьер -> блокировка ));
while ( барьер -> флаг != local_sense ); // ждем флага
}
}
}
void thread_barrier_destroy ( thread_barrier * барьер ) {
pthread_mutex_destroy ( & ( барьер -> блокировка ));
}
void * thread_func ( void * ptr ){
printf ( "поток с идентификатором %ld ожидает у барьера, так как запущено недостаточно %d потоков... \n " , pthread_self (), THREAD_BARRIERS_NUMBER );
thread_barrier_wait ( & барьер );
printf ( "Барьер снят, поток с идентификатором %ld сейчас запущен \n " , pthread_self ());
}
Int Main ()
{
pthread_t thread_id [ TOTAL_THREADS ];
thread_barrier_init ( & барьер , PTHREAD_BARRIER_ATTR , THREAD_BARRIERS_NUMBER );
for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) {
pthread_create ( & thread_id [ i ], NULL , thread_func , NULL );
}
// Поскольку pthread_join() будет блокировать процесс до тех пор, пока все указанные им потоки не завершатся,
// и у барьера не будет достаточно потоков, чтобы ждать, поэтому этот процесс блокируется
на ( int i = 0 ; i < TOTAL_THREADS ; я ++ ) {
pthread_join ( thread_id [ i ], NULL );
}
thread_barrier_destroy ( & барьер );
printf ( "Потоковый барьер снят \n " ); // Эта строка не будет называться TOTAL_THREADS < THREAD_BARRIERS_NUMBER
}
Эта программа имеет все функции, аналогичные предыдущему исходному коду Centralized Barrier . Просто он реализуется по-другому, используя две новые переменные: [1]
- local_sense : локальная логическая переменная потока, проверяющая, достиг ли барьер THREAD_BARRIERS_NUMBER.
- флаг : логический член структуры _thread_barrier , указывающий, достигли ли THREAD_BARRIERS_NUMBER барьера.
Когда поток останавливается на барьере, значение local_sense переключается. [1] Если на барьере потока останавливается менее THREAD_BARRIERS_NUMBER потоков, эти потоки будут продолжать ждать с условием, что флаг член- структуры struct _thread_barrier не равен частному local_sense переменная.
Когда ровно THREAD_BARRIERS_NUMBER потоков останавливается на барьере потоков, общее количество потоков сбрасывается до 0, а флаг устанавливается в значение local_sense.
Объединение барьера из дерева [ править ]
Потенциальная проблема с централизованным барьером заключается в том, что из-за того, что все потоки неоднократно обращаются к глобальной переменной для прохода/остановки, коммуникационный трафик довольно высок, что снижает масштабируемость .
Эту проблему можно решить, перегруппировав потоки и используя многоуровневый барьер, например, комбинированный барьер дерева. Также аппаратные реализации могут иметь преимущество более высокой масштабируемости .
Барьер комбинированного дерева — это иерархический способ реализации барьера для решения проблемы масштабируемости , позволяющий избежать случая, когда все потоки вращаются в одном и том же месте. [4]
В k-Tree Barrier все потоки поровну делятся на подгруппы по k потоков, и внутри этих подгрупп выполняется синхронизация первого раунда. После того как все подгруппы выполнили синхронизацию, первый поток в каждой подгруппе переходит на второй уровень для дальнейшей синхронизации. На втором уровне, как и на первом, потоки образуют новые подгруппы из k потоков и синхронизируются внутри групп, отправляя по одному потоку из каждой подгруппы на следующий уровень и так далее. В конце концов, на последнем уровне синхронизируется только одна подгруппа. После синхронизации последнего уровня сигнал освобождения передается на верхние уровни, и все потоки преодолевают барьер. [6] [7]
аппаратного Реализация барьера
Аппаратный барьер использует аппаратное обеспечение для реализации описанной выше базовой модели барьера. [3]
В простейшей аппаратной реализации для передачи сигнала для реализации барьера используются выделенные провода. Этот выделенный провод выполняет операцию ИЛИ/И, действуя как флаги пропуска/блокировки и счетчик потоков. Для небольших систем такая модель работает, и скорость связи не является серьезной проблемой. В больших многопроцессорных системах такая аппаратная конструкция может привести к тому, что реализация барьера будет иметь большую задержку. Сетевое соединение между процессорами — это одна из реализаций снижения задержки, аналогичная объединению барьера дерева. [8]
Функции барьера потоков POSIX [ править ]
Стандарт POSIX Threads напрямую поддерживает функции барьера потоков , которые можно использовать для блокировки указанных потоков или всего процесса на барьере до тех пор, пока другие потоки не достигнут этого барьера . [2] POSIX поддерживает три основных API-интерфейса для реализации барьеров потоков:
pthread_barrier_init()- Инициализируйте барьер потоков с количеством потоков, необходимых для ожидания у барьера, чтобы поднять его. [9]
pthread_barrier_destroy()- Уничтожьте барьер потока, чтобы вернуть ресурс. [9]
pthread_barrier_wait()- Вызов этой функции заблокирует текущий поток до тех пор, пока количество потоков, указанное в
pthread_barrier_init()вызовpthread_barrier_wait()чтобы поднять барьер. [10]
В следующем примере (реализованном на C с помощью API pthread) будет использоваться барьер потоков для блокировки всех потоков основного процесса и, следовательно, для блокировки всего процесса:
#include <stdio.h>
#include <pthread.h>
#define TOTAL_THREADS 2
#define THREAD_BARRIERS_NUMBER 3
#define PTHREAD_BARRIER_ATTR NULL // атрибут барьера pthread
pthread_barrier_t барьер ;
void * thread_func ( void * ptr ){
printf ( «Ожидание у барьера, так как запущено недостаточно %d потоков... \n » , THREAD_BARRIERS_NUMBER );
pthread_barrier_wait ( & барьер );
printf ( "Барьер снят, поток с идентификатором %ld сейчас запущен \n " , pthread_self ());
}
Int Main ()
{
pthread_t thread_id [ TOTAL_THREADS ];
pthread_barrier_init ( & барьер , PTHREAD_BARRIER_ATTR , THREAD_BARRIERS_NUMBER );
for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) {
pthread_create ( & thread_id [ i ], NULL , thread_func , NULL );
}
// Так как pthread_join() будет блокировать процесс до тех пор, пока все указанные им потоки не завершатся,
// и у барьера не будет достаточно потоков, чтобы ждать, поэтому этот процесс блокируется
на ( int i = 0 ; i < TOTAL_THREADS ; я ++ ) {
pthread_join ( thread_id [ i ], NULL );
}
pthread_barrier_destroy ( & барьер );
printf ( "Потоковый барьер снят \n " ); // Эта строка не будет называться TOTAL_THREADS < THREAD_BARRIERS_NUMBER
}
Результат этого исходного кода:
Ожидание у барьера, так как запущено недостаточно трех потоков...
Ожидание у барьера, так как запущено недостаточно трех потоков...
// (основной процесс заблокирован из-за недостаточного количества трех потоков)
// Строка printf("Барьер потока снят\n") не будет достигнут
Как мы видим из исходного кода, создается всего два потока. Оба этих потока имеют thread_func() в качестве обработчика функции потока, который вызывает pthread_barrier_wait(&barrier), в то время как потоковый барьер ожидал вызова 3 потоков pthread_barrier_wait ( THREAD_BARRIERS_NUMBER = 3), чтобы его подняли.
Измените TOTAL_THREADS на 3, и барьер потока будет снят:
Ожидание у барьера, поскольку запущено недостаточно 3 потоков...
Ожидание у барьера, так как запущено недостаточно 3 потоков...
Ожидание у барьера, так как запущено недостаточно 3 потоков...
Барьер снят, идентификатор потока 140643372406528 Барьер
Барьер снят, идентификатор потока 140643380799232 работает сейчас
снят, идентификатор потока 140643389191936 работает сейчас
Барьер потока снят
Поскольку main() рассматривается как поток , то есть «основной» поток процесса, [11] звоню pthread_barrier_wait() внутри main()заблокирует весь процесс до тех пор, пока другие потоки не достигнут барьера. В следующем примере будет использоваться барьер потока, при этом pthread_barrier_wait() внутри main(), чтобы заблокировать процесс/основной поток на 5 секунд в ожидании достижения 2-м «вновь созданным» потоком барьера потока:
#define TOTAL_THREADS 2
#define THREAD_BARRIERS_NUMBER 3
#define PTHREAD_BARRIER_ATTR NULL // атрибут барьера pthread
pthread_barrier_t барьер ;
void * thread_func ( void * ptr ){
printf ( «Ожидание у барьера, так как запущено недостаточно %d потоков... \n » , THREAD_BARRIERS_NUMBER );
спать ( 5 );
pthread_barrier_wait ( & барьер );
printf ( "Барьер снят, поток с идентификатором %ld сейчас запущен \n " , pthread_self ());
}
Int Main ()
{
pthread_t thread_id [ TOTAL_THREADS ];
pthread_barrier_init ( & барьер , PTHREAD_BARRIER_ATTR , THREAD_BARRIERS_NUMBER );
for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) {
pthread_create ( & thread_id [ i ], NULL , thread_func , NULL );
}
pthread_barrier_wait ( & барьер );
printf ( "Потоковый барьер снят \n " ); // Эта строка не будет называться TOTAL_THREADS < THREAD_BARRIERS_NUMBER
pthread_barrier_destroy ( & барьер );
}
В этом примере не используется pthread_join()дождаться завершения двух «вновь созданных» потоков. Он вызывает pthread_barrier_wait() внутри main(), чтобы заблокировать основной поток, чтобы процесс был заблокирован до тех пор, пока 2 потока не завершат свою работу после 5-секундного ожидания (строка 9 - sleep(5)).
См. также [ править ]
Ссылки [ править ]
- ^ Перейти обратно: а б с д Это «Внедрение барьеров» . Университет Карнеги Меллон.
- ^ Перейти обратно: а б Операционная система GNU. «Реализация pthread_barrier» . gnu.org . Проверено 2 марта 2024 г.
- ^ Перейти обратно: а б с Солихин, Ян (01 января 2015 г.). Основы параллельной многоядерной архитектуры (1-е изд.). Чепмен и Холл/CRC. ISBN 978-1482211184 .
- ^ Перейти обратно: а б Каллер, Дэвид (1998). Параллельная компьютерная архитектура: аппаратно-программный подход . Галф Профессионал. ISBN 978-1558603431 .
- ^ Каллер, Дэвид (1998). Параллельная компьютерная архитектура: аппаратно-программный подход . Галф Профессионал. ISBN 978-1558603431 .
- ^ Перейти обратно: а б Нанджегоуда, Рамачандра; Эрнандес, Оскар; Чепмен, Барбара; Цзинь, Хаоцян Х. (3 июня 2009 г.). Мюллер, Матиас С.; Супинский, Бронис Р. де; Чепмен, Барбара М. (ред.). Развитие OpenMP в эпоху крайнего параллелизма . Конспекты лекций по информатике. Шпрингер Берлин Гейдельберг. стр. 42–52 . дои : 10.1007/978-3-642-02303-3_4 . ISBN 9783642022845 .
- ^ Николопулос, Димитриос С.; Папатеодору, Теодор С. (1 января 1999 г.). «Количественная архитектурная оценка алгоритмов и дисциплин синхронизации в системах ccNUMA». Материалы 13-й международной конференции по суперкомпьютингу . ИКС '99. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 319–328. дои : 10.1145/305138.305209 . ISBN 978-1581131642 . S2CID 6097544 . Архивировано из оригинала 25 июля 2017 г. Проверено 18 января 2019 г.
- ^ Н. Р. Адига и др. Обзор суперкомпьютера BlueGene/L. Материалы конференции по высокопроизводительным сетям и вычислениям, 2002 г.
- ^ Перейти обратно: а б «pthread_barrier_init(), pthread_barrier_destroy()» . Справочная страница Linux . Проверено 16 марта 2024 г.
- ^ «pthread_barrier_wait()» . Справочная страница Linux . Проверено 16 марта 2024 г.
- ^ «Как получить количество процессов и потоков в программе на C?» . переполнение стека . Проверено 16 марта 2024 г.
Внешние ссылки [ править ]
«Параллельное программирование с барьерной синхронизацией» . sourceallies.com . Март 2012.
