En computación paralela , una barrera es un tipo de método de sincronización . [1] Una barrera para un grupo de subprocesos o procesos en el código fuente significa que cualquier subproceso/proceso debe detenerse en este punto y no puede continuar hasta que todos los demás subprocesos/procesos alcancen esta barrera. [2]
Muchas rutinas colectivas y lenguajes paralelos basados en directivas imponen barreras implícitas. Por ejemplo, no se permitirá que un bucle do paralelo en Fortran con OpenMP continúe en ningún hilo hasta que se complete la última iteración. [ cita requerida ] Esto es en caso de que el programa dependa del resultado del bucle inmediatamente después de su finalización. En el paso de mensajes , cualquier comunicación global (como reducción o dispersión) puede implicar una barrera.
En computación concurrente , una barrera puede estar en un estado elevado o reducido . El término pestillo se utiliza a veces para referirse a una barrera que comienza en el estado elevado y no se puede volver a elevar una vez que está en el estado reducido. El término pestillo de cuenta regresiva se utiliza a veces para referirse a un pestillo que se baja automáticamente una vez que ha llegado una cantidad predeterminada de subprocesos/procesos.
Tomemos como ejemplo un subproceso, conocido como barrera de subprocesos . La barrera de subprocesos necesita una variable para realizar un seguimiento del número total de subprocesos que han entrado en la barrera . [3] Siempre que haya suficientes subprocesos que entren en la barrera, esta se levantará. También se necesita una primitiva de sincronización como mutex al implementar la barrera de subprocesos.
Este método de barrera de hilos también se conoce como barrera centralizada , ya que los hilos tienen que esperar delante de una "barrera central" hasta que la cantidad esperada de hilos haya alcanzado la barrera antes de que se levante.
El siguiente código C, que implementó la barrera de subprocesos mediante subprocesos POSIX, demostrará este procedimiento: [1]
#incluir <stdio.h> #include <pthread.h> #define TOTAL_HILOS 2#define BARRERAS DE HILO NÚMERO 3#define PTHREAD_BARRIER_ATTR NULL // atributo de barrera pthreadestructura de tipo definido _thread_barrier { int numero_de_barrera_de_hilo ; pthread_mutex_t bloqueo ; int total_hilo ; } barrera_de_hilo ; barrera_hilo barrera ; void thread_barrier_init ( barrera_de_hilo * barrera , pthread_mutexattr_t * mutex_attr , int número_de_barrera_de_hilo ){ pthread_mutex_init ( & ( barrera -> bloqueo ), mutex_attr ); barrera -> numero_de_barrera_de_hilo = numero_de_barrera_de_hilo ; barrera -> total_thread = 0 ; // Inicializar el total de subprocesos para que sea 0 }void thread_barrier_wait ( barrera_hilo * barrera ){ si ( ! pthread_mutex_lock ( & ( barrera -> bloqueo ))){ barrera -> total_thread += 1 ; pthread_mutex_unlock ( & ( barrera -> bloqueo )); } mientras ( barrera -> hilo_total < barrera -> hilo_barrera_numero ); si ( ! pthread_mutex_lock ( & ( barrera -> bloqueo ))){ barrera -> total_thread -= 1 ; // Disminuye un hilo a medida que pasa la barrera de hilos pthread_mutex_unlock ( & ( barrera -> bloqueo )); }}void thread_barrier_destroy ( thread_barrier * barrera ){ pthread_mutex_destroy ( & ( barrera -> bloqueo ));}vacío * función_hilo ( vacío * ptr ){ printf ( "el hilo id %ld está esperando en la barrera, ya que no hay suficientes %d hilos ejecutándose... \n " , pthread_self (), THREAD_BARRIERS_NUMBER ); thread_barrier_wait ( & barrera ); printf ( "La barrera se ha levantado, el hilo id %ld se está ejecutando ahora \n " , pthread_self ()); }int principal () { pthread_t id_hilo [ TOTAL_HILOS ]; thread_barrier_init ( & barrera , PTHREAD_BARRIER_ATTR , THREAD_BARRIERS_NUMBER ); para ( int i = 0 ; i < TOTAL_HILOS ; i ++ ){ pthread_create ( & id_hilo [ i ], NULL , función_hilo , NULL ); } // Como pthread_join() bloqueará el proceso hasta que todos los hilos que especificó hayan finalizado, // y no hay suficiente hilo para esperar en la barrera, por lo que este proceso está bloqueado para ( int i = 0 ; i < TOTAL_HILOS ; i ++ ){ pthread_join ( id_hilo [ i ], NULL ); } thread_barrier_destroy ( & barrera ); printf ( "La barrera de subprocesos se ha levantado \n " ); // Esta línea no se llamará ya que TOTAL_THREADS < THREAD_BARRIERS_NUMBER }En este programa, la barrera de hilo se define como una estructura, struct _thread_barrier, que incluye:
Basándonos en la definición de barrera, necesitamos implementar una función como thread_barrier_wait() en este programa que "monitoreará" el número total de subprocesos en el programa para levantar la barrera.
En este programa, cada hilo que llama a thread_barrier_wait() se bloqueará hasta que THREAD_BARRIERS_NUMBER hilos alcancen la barrera de hilos.
El resultado de ese programa es:
El id del subproceso <thread_id, p. ej. 139997337872128> está esperando en la barrera, ya que no se están ejecutando 3 subprocesos suficientes... El id del subproceso <thread_id, p. ej. 139997329479424> está esperando en la barrera, ya que no se están ejecutando 3 subprocesos suficientes... // (el proceso principal está bloqueado por no tener 3 subprocesos suficientes) // No se alcanzará la línea printf("Se levantó la barrera de subprocesos\n")Como podemos ver en el programa, solo se crean 2 subprocesos. Ambos subprocesos tienen , como controlador de función de subproceso, que llama a , mientras que la barrera de subprocesos esperaba que 3 subprocesos llamaran a ( ) para poder levantarse. Cambie TOTAL_THREADS a 3 y se levantará la barrera de subprocesos:thread_func()thread_barrier_wait(&barrier)thread_barrier_waitTHREAD_BARRIERS_NUMBER = 3
El hilo id <ID del hilo, p. ej., 140453108946688> está esperando en la barrera, ya que no se están ejecutando 3 hilos suficientes... El hilo id <ID del hilo, p. ej., 140453117339392> está esperando en la barrera, ya que no se están ejecutando 3 hilos suficientes... El hilo id <ID del hilo, p. ej., 140453100553984> está esperando en la barrera, ya que no se están ejecutando 3 hilos suficientes... La barrera se levanta, el hilo id <ID del hilo, p. ej., 140453108946688> se está ejecutando ahora La barrera se levanta, el hilo id <ID del hilo, p. ej., 140453117339392> se está ejecutando ahora La barrera se levanta, el hilo id <ID del hilo, p. ej., 140453100553984> se está ejecutando ahora La barrera del hilo se levantaAdemás de disminuir el número total de subprocesos en uno por cada subproceso que pasa con éxito la barrera de subprocesos, la barrera de subprocesos puede usar valores opuestos para marcar cada estado de subproceso como que pasa o se detiene. [4] Por ejemplo, el subproceso 1 con valor de estado es 0 significa que se detiene en la barrera, el subproceso 2 con valor de estado es 1 significa que ha pasado la barrera, el valor de estado del subproceso 3 = 0 significa que se detiene en la barrera y así sucesivamente. [5] Esto se conoce como inversión de sentido. [1]
El siguiente código C demuestra esto: [3] [6]
#incluir <stdio.h> #include <stdbool.h> #include <pthread.h> #define TOTAL_HILOS 2#define BARRERAS DE HILO NÚMERO 3#define PTHREAD_BARRIER_ATTR NULL // atributo de barrera pthreadestructura de tipo definido _thread_barrier { int numero_de_barrera_de_hilo ; int total_hilo ; pthread_mutex_t bloqueo ; bandera bool ; } barrera_de_hilo ; barrera_hilo barrera ; void thread_barrier_init ( barrera_de_hilo * barrera , pthread_mutexattr_t * mutex_attr , int número_de_barrera_de_hilo ){ pthread_mutex_init ( & ( barrera -> bloqueo ), mutex_attr ); barrera -> total_thread = 0 ; barrera -> numero_de_barrera_de_hilo = numero_de_barrera_de_hilo ; barrera -> bandera = falso ; }void thread_barrier_wait ( barrera_hilo * barrera ){ bool local_sense = barrera -> bandera ; si ( ! pthread_mutex_lock ( & ( barrera -> bloqueo ))){ barrera -> total_thread += 1 ; sentido_local = ! sentido_local ; si ( barrera -> hilo_total == barrera -> hilo_barrera_numero ){ barrera -> total_thread = 0 ; barrera -> bandera = sentido_local ; pthread_mutex_unlock ( & ( barrera -> bloqueo )); } demás { pthread_mutex_unlock ( & ( barrera -> bloqueo )); mientras ( barrera -> bandera != local_sense ); // esperar la bandera } }}void thread_barrier_destroy ( thread_barrier * barrera ){ pthread_mutex_destroy ( & ( barrera -> bloqueo ));}vacío * función_hilo ( vacío * ptr ){ printf ( "el hilo id %ld está esperando en la barrera, ya que no hay suficientes %d hilos ejecutándose... \n " , pthread_self (), THREAD_BARRIERS_NUMBER ); thread_barrier_wait ( & barrera ); printf ( "La barrera se ha levantado, el hilo id %ld se está ejecutando ahora \n " , pthread_self ()); }int principal () { pthread_t id_hilo [ TOTAL_HILOS ]; thread_barrier_init ( & barrera , PTHREAD_BARRIER_ATTR , THREAD_BARRIERS_NUMBER ); para ( int i = 0 ; i < TOTAL_HILOS ; i ++ ){ pthread_create ( & id_hilo [ i ], NULL , función_hilo , NULL ); } // Como pthread_join() bloqueará el proceso hasta que todos los hilos que especificó hayan finalizado, // y no hay suficiente hilo para esperar en la barrera, por lo que este proceso está bloqueado para ( int i = 0 ; i < TOTAL_HILOS ; i ++ ){ pthread_join ( id_hilo [ i ], NULL ); } thread_barrier_destroy ( & barrera ); printf ( "La barrera de subprocesos se ha levantado \n " ); // Esta línea no se llamará ya que TOTAL_THREADS < THREAD_BARRIERS_NUMBER }Este programa tiene todas las características similares al código fuente de Centralized Barrier anterior . Solo que se implementa de una manera diferente mediante el uso de 2 nuevas variables: [1]
Cuando un hilo se detiene en la barrera, el valor de local_sense se alterna. [1] Cuando hay menos de THREAD_BARRIERS_NUMBER hilos que se detienen en la barrera de hilos, esos hilos seguirán esperando con la condición de que el miembro de bandera de struct _thread_barrier no sea igual a la local_sensevariable privada.
Cuando hay exactamente THREAD_BARRIERS_NUMBER subprocesos que se detienen en la barrera de subprocesos, el número total de subprocesos se restablece a 0 y el indicador se establece en local_sense.
El problema potencial con la barrera centralizada es que, debido a que todos los hilos acceden repetidamente a la variable global para pasar/detener, el tráfico de comunicación es bastante alto, lo que disminuye la escalabilidad .
Este problema se puede resolver reagrupando los subprocesos y utilizando una barrera de varios niveles, por ejemplo, la barrera de árbol de combinación. Además, las implementaciones de hardware pueden tener la ventaja de una mayor escalabilidad .
Una barrera de árbol combinado es una forma jerárquica de implementar una barrera para resolver la escalabilidad evitando el caso de que todos los hilos estén girando en la misma ubicación. [4]
En la barrera de k-árbol, todos los subprocesos se dividen equitativamente en subgrupos de k subprocesos y se realiza una primera ronda de sincronizaciones dentro de estos subgrupos. Una vez que todos los subgrupos han realizado sus sincronizaciones, el primer subproceso de cada subgrupo ingresa al segundo nivel para una mayor sincronización. En el segundo nivel, como en el primero, los subprocesos forman nuevos subgrupos de k subprocesos y se sincronizan dentro de los grupos, enviando un subproceso de cada subgrupo al siguiente nivel y así sucesivamente. Finalmente, en el nivel final solo hay un subgrupo para sincronizar. Después de la sincronización del nivel final, la señal de liberación se transmite a los niveles superiores y todos los subprocesos pasan la barrera. [6] [7]
La barrera de hardware utiliza hardware para implementar el modelo de barrera básico mencionado anteriormente. [3]
La implementación de hardware más simple utiliza cables dedicados para transmitir señales para implementar la barrera. Este cable dedicado realiza la operación OR/AND para actuar como indicadores de paso/bloqueo y contador de subprocesos. Para sistemas pequeños, este modelo funciona y la velocidad de comunicación no es una preocupación importante. En sistemas multiprocesador grandes, este diseño de hardware puede hacer que la implementación de la barrera tenga una latencia alta. La conexión de red entre procesadores es una implementación para reducir la latencia, que es análoga a la barrera de árbol de combinación. [8]
El estándar POSIX Threads admite directamente funciones de barrera de subprocesos que se pueden usar para bloquear los subprocesos especificados o todo el proceso en la barrera hasta que otros subprocesos alcancen esa barrera . [2] Las 3 API principales compatibles con POSIX para implementar barreras de subprocesos son:
pthread_barrier_init()pthread_barrier_destroy()pthread_barrier_wait()pthread_barrier_init()la llamada pthread_barrier_wait()para levantar la barrera. [10]El siguiente ejemplo (implementado en C con la API pthread) utilizará la barrera de subprocesos para bloquear todos los subprocesos del proceso principal y, por lo tanto, bloquear todo el proceso:
#incluir <stdio.h> #include <pthread.h> #define TOTAL_HILOS 2#define BARRERAS DE HILO NÚMERO 3#define PTHREAD_BARRIER_ATTR NULL // atributo de barrera pthreadpthread_barrier_t barrera ; vacío * función_hilo ( vacío * ptr ){ printf ( "Esperando en la barrera porque no hay suficientes %d subprocesos ejecutándose... \n " , THREAD_BARRIERS_NUMBER ); pthread_barrier_wait ( & barrera ); printf ( "La barrera se ha levantado, el hilo id %ld se está ejecutando ahora \n " , pthread_self ()); }int principal () { pthread_t id_hilo [ TOTAL_HILOS ]; pthread_barrier_init ( & barrera , PTHREAD_BARRIER_ATTR , NÚMERO_BARRERAS_DE_HILO ); para ( int i = 0 ; i < TOTAL_HILOS ; i ++ ){ pthread_create ( & id_hilo [ i ], NULL , función_hilo , NULL ); } // Como pthread_join() bloqueará el proceso hasta que todos los hilos que especifica hayan finalizado, // y no hay suficiente hilo para esperar en la barrera, por lo que este proceso está bloqueado para ( int i = 0 ; i < TOTAL_HILOS ; i ++ ){ pthread_join ( id_hilo [ i ], NULL ); } pthread_barrier_destroy ( & barrera ); printf ( "La barrera de subprocesos se ha levantado \n " ); // Esta línea no se llamará ya que TOTAL_THREADS < THREAD_BARRIERS_NUMBER }El resultado de ese código fuente es:
Esperando en la barrera ya que no se están ejecutando 3 subprocesos suficientes... Esperando en la barrera ya que no se están ejecutando 3 subprocesos suficientes... // (el proceso principal está bloqueado por no tener 3 subprocesos suficientes) // No se alcanzará la línea printf("La barrera de subprocesos se ha levantado\n")Como podemos ver en el código fuente, solo se crean dos subprocesos. Ambos subprocesos tienen thread_func() como controlador de función de subproceso, que llama a , mientras que la barrera de subprocesos espera que 3 subprocesos llamen a ( ) para poder levantarse. Cambie TOTAL_THREADS a 3 y la barrera de subprocesos se levanta:pthread_barrier_wait(&barrier)pthread_barrier_waitTHREAD_BARRIERS_NUMBER = 3
Esperando en la barrera ya que no se están ejecutando 3 subprocesos suficientes... Esperando en la barrera ya que no se están ejecutando 3 subprocesos suficientes... Esperando en la barrera ya que no se están ejecutando 3 subprocesos suficientes... La barrera se ha levantado, el id del subproceso 140643372406528 se está ejecutando ahora La barrera se ha levantado, el id del subproceso 140643380799232 se está ejecutando ahora La barrera se ha levantado, el id del subproceso 140643389191936 se está ejecutando ahora La barrera del subproceso se ha levantadoComo main() se trata como un subproceso , es decir, el subproceso "principal" del proceso, [11] al llamar pthread_barrier_wait()a inside main()se bloqueará todo el proceso hasta que otros subprocesos alcancen la barrera. El siguiente ejemplo utilizará la barrera del subproceso, con pthread_barrier_wait()inside main(), para bloquear el proceso/subproceso principal durante 5 segundos mientras se espera que los 2 subprocesos "recién creados" alcancen la barrera del subproceso:
#define TOTAL_HILOS 2#define BARRERAS DE HILO NÚMERO 3#define PTHREAD_BARRIER_ATTR NULL // atributo de barrera pthreadpthread_barrier_t barrera ; vacío * función_hilo ( vacío * ptr ){ printf ( "Esperando en la barrera porque no hay suficientes %d subprocesos ejecutándose... \n " , THREAD_BARRIERS_NUMBER ); dormir ( 5 ); pthread_barrier_wait ( & barrera ); printf ( "La barrera se ha levantado, el hilo id %ld se está ejecutando ahora \n " , pthread_self ()); }int principal () { pthread_t id_hilo [ TOTAL_HILOS ]; pthread_barrier_init ( & barrera , PTHREAD_BARRIER_ATTR , NÚMERO_BARRERAS_DE_HILO ); para ( int i = 0 ; i < TOTAL_HILOS ; i ++ ){ pthread_create ( & id_hilo [ i ], NULL , función_hilo , NULL ); }pthread_barrier_wait ( & barrera ); printf ( "La barrera de subprocesos se ha levantado \n " ); // Esta línea no se llamará ya que TOTAL_THREADS < THREAD_BARRIERS_NUMBER pthread_barrier_destroy ( & barrera );}Este ejemplo no suele pthread_join()esperar a que se completen 2 subprocesos "recién creados". Se llama pthread_barrier_wait()dentro de main(), para bloquear el subproceso principal, de modo que el proceso se bloquee hasta que 2 subprocesos finalicen su operación después de 5 segundos de espera (línea 9 - sleep(5)).
"Programación paralela con sincronización de barrera". sourceallies.com . Marzo de 2012.