Hispanopedia Wiki
Articulo de referencia

Barrera (informática)

En computación paralela , una barrera es un método de sincronización . [ 1 ] Una barrera para un grupo de hilos o procesos en el código fuente significa que todos los hilos/proc...

Hispanopedia WikiContenido en espanolLectura gratuita

En computación paralela , una barrera es un método de sincronización . [ 1 ] Una barrera para un grupo de hilos o procesos en el código fuente significa que todos los hilos/procesos se detienen en ese punto y no continúan hasta que todos los demás hilos/procesos alcanzan esta barrera. [ 2 ]

Muchas rutinas colectivas y lenguajes paralelos basados ​​en directivas imponen barreras implícitas. Por ejemplo, un dobucle paralelo en Fortran con OpenMP no podrá continuar en ningún hilo hasta que se complete la última iteración. Esto se debe a que el programa depende del resultado del bucle inmediatamente después de su finalización. En el paso de mensajes , cualquier comunicación global (como la reducción o la dispersión) puede implicar una barrera.

En la computación concurrente , una barrera puede estar en estado "elevado" o "descendedo". El término "bloqueo" se usa a veces para referirse a una barrera que comienza en estado elevado y no puede volver a elevarse una vez que está en estado descendido. El término "bloqueo de cuenta regresiva" se usa a veces para referirse a un bloqueo que se desciende automáticamente una vez que ha llegado un número predeterminado de hilos/procesos.

Implementación

Consideremos el siguiente ejemplo de una barrera de hilos. La barrera de hilos requiere una variable para "mantener un registro del número total de hilos que han entrado en la barrera". [ 3 ] Cuando suficientes hilos entran en la barrera, esta se levanta. También se necesita una primitiva de sincronización como un mutex al implementar la barrera de hilos.

Este método de barrera de hilos también se conoce como "barrera centralizada", ya que los hilos esperan ante una "barrera central" hasta que el número esperado de hilos haya alcanzado la barrera antes de que esta se levante.

Esto se puede demostrar con el siguiente ejemplo en C que utiliza hilos POSIX . [ 1 ]

#include <stdio.h> #include <pthread.h>#define TOTAL_THREADS 2 #define THREAD_BARRIERS_NUMBER 3typedef struct Barrera { pthread_mutex_t bloqueo ; int contador_barrera ; int contador_hilo ; } Barrera ;Barrera barrera ;void barrier_init ( ThreadBarrier * bar , pthread_mutexattr_t * attr , int count ) { pthread_mutex_init ( & ( bar- > lock ), attr ); bar- > barrera_count = count ; bar- > thread_count = 0 ; // Inicializar el recuento total de hilos a 0 }void barrier_wait ( Barrier * bar ) { if ( ! pthread_mutex_lock ( & ( bar -> lock ))) { bar -> total_thread ++ ; pthread_mutex_unlock ( & ( bar -> lock )); }while ( bar -> thread_count < bar -> barrier_count ) { // Implementa una barrera de espera activa (no hace nada hasta que lleguen suficientes hilos) }if ( ! pthread_mutex_lock ( & ( bar -> lock ))) { bar -> thread_count -- ; // Disminuir en un hilo al pasar la barrera de hilos pthread_mutex_unlock ( & ( bar -> lock )); } }void barrier_destroy ( Barrier * bar ) { pthread_mutex_destroy ( & ( bar -> lock )); }void * thread_func ([[ maybe_unused ]] void * p ) { printf ( "El hilo con ID %ld está esperando en la barrera, ya que no hay suficientes (%d) hilos en ejecución... \n " , pthread_self (), THREAD_BARRIERS_NUMBER ); thread_barrier_wait ( & barrier ); printf ( "Barrera levantada, el hilo con ID %ld se está ejecutando ahora \n " , pthread_self ()); }int main () { pthread_t thread_ids [ TOTAL_THREADS ];thread_barrier_init ( & barrera , NULL , NÚMERO_DE_BARRERA_DE_INTERRUPTOS ); para ( int i = 0 ; i < TOTAL_DE_INTERRUPTOS ; i ++ ) { pthread_create ( & thread_ids [ i ], NULL , thread_func , NULL ); }// Como pthread_join() bloquea el proceso hasta que todos los hilos especificados hayan terminado, // y no hay suficientes hilos para esperar en la barrera, este proceso se bloquea. for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) { pthread_join ( thread_ids [ i ], NULL ); }thread_barrier_destroy ( & barrier ); printf ( "Barrera de hilos levantada \n " ); // Esta línea no se llamará ya que TOTAL_THREADS < THREAD_BARRIERS_NUMBER }

En este programa, la barrera de subprocesos, struct Barrier, consta de:

  • lock: Un bloqueo mutex de subprocesos POSIX
  • thread_count: Número total de hilos en el proceso
  • barrier_count: Número total de hilos que se espera que entren en la barrera de hilos para que pueda levantarse.

Según la definición de barrera, la implementación requiere una función como thread_barrier_wait()la de este programa que "monitorea" el número total de hilos en el programa para activar la barrera.

En este programa, cada llamada de hilo thread_barrier_wait()se bloqueará hasta que THREAD_BARRIERS_NUMBERlos hilos alcancen la barrera de hilos. Como el hilo principal está bloqueado por no tener tres hilos, la línea "Se levanta la barrera de hilos" nunca se ejecuta. El resultado de ese programa es:

El hilo con ID <thread_id, por ejemplo, 139997337872128> está esperando en la barrera, ya que no hay suficientes 3 hilos en ejecución... El hilo con ID <thread_id, por ejemplo, 139997329479424> está esperando en la barrera, ya que no hay suficientes 3 hilos en ejecución...

Solo se crean dos hilos con thread_func()como manejador de función de hilo, que llama a thread_barrier_wait(&barrier), mientras que la barrera de hilo espera que tres hilos llamen thread_barrier_wait()para poder levantarse.

Al cambiar TOTAL_THREADSa 3, se levanta la barrera del hilo:

El ID de hilo <ID de hilo, por ejemplo, 140453108946688> está esperando en la barrera, ya que no hay suficientes (3) hilos en ejecución... El ID de hilo <ID de hilo, por ejemplo, 140453117339392> está esperando en la barrera, ya que no hay suficientes (3) hilos en ejecución... El ID de hilo <ID de hilo, por ejemplo, 140453100553984> está esperando en la barrera, ya que no hay suficientes (3) hilos en ejecución... Barrera levantada, el ID de hilo <ID de hilo, por ejemplo, 140453108946688> se está ejecutando ahora Barrera levantada, el ID de hilo <ID de hilo, por ejemplo, 140453117339392> se está ejecutando ahora Barrera levantada, el ID de hilo <ID de hilo, por ejemplo, 140453100553984> se está ejecutando ahora Barrera de hilo levantada

Barrera centralizada de inversión de sentidos

Además de disminuir el número total de hilos por cada hilo que supera con éxito la barrera de hilos, las barreras de hilos pueden usar valores opuestos para marcar el estado de cada hilo como pasando o deteniéndose. [ 4 ] Por ejemplo, 0 puede indicar que se detiene en la barrera, mientras que 1 indica que la supera. [ 5 ] Esto se conoce como "inversión de sentido" [ 1 ] , como se demuestra a continuación: [ 3 ] [ 6 ]

#include <stdio.h> #include <pthread.h>#define TOTAL_THREADS 2 #define THREAD_BARRIERS_NUMBER 3typedef struct Barrera { pthread_mutex_t bloqueo ; int contador_barrera ; int contador_hilo ; bool bandera ; } Barrera ;Barrera barrera ;void barrier_init ( Barrier * bar , pthread_mutexattr_t * attr , int count ) { pthread_mutex_init ( & ( bar -> lock ), attr );barra -> recuento_hilos = 0 ; barra -> recuento_barreras = recuento ; barra -> bandera = falso ; }void barrier_wait ( Barrier * barrier ) { thread_local bool local_flag = bar- > flag ; if ( ! pthread_mutex_lock ( & ( bar- > lock ))) { bar- > thread_count ++ ; local_sense = ! local_sense ; if ( bar- > thread_count == bar- > barrier_count ) { bar- > thread_count = 0 ; bar- > flag = local_flag ; pthread_mutex_unlock ( & ( bar- > lock )); } else { pthread_mutex_unlock ( & ( bar- > lock )); while ( bar- > flag != local_flag ) { // esperar a que se active la bandera } } } }void barrier_destroy ( Barrier * bar ) { pthread_mutex_destroy ( & ( bar -> lock )); }void * thread_func ([[ maybe_unused ]] void * p ) { printf ( "El hilo con ID %ld está esperando en la barrera, ya que no hay suficientes (%d) hilos en ejecución... \n " , pthread_self (), THREAD_BARRIERS_NUMBER ); thread_barrier_wait ( & barrier ); printf ( "Barrera levantada, el hilo con ID %ld se está ejecutando ahora \n " , pthread_self ()); }int main () { pthread_t thread_ids [ TOTAL_THREADS ];thread_barrier_init ( & barrera , NULL , NÚMERO_DE_BARRERA_DE_INTERRUPTOS ); para ( int i = 0 ; i < TOTAL_DE_INTERRUPTOS ; i ++ ) { pthread_create ( & thread_ids [ i ], NULL , thread_func , NULL ); }// Como pthread_join() bloquea el proceso hasta que todos los hilos especificados hayan terminado, // y no hay suficientes hilos para esperar en la barrera, este proceso se bloquea. for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) { pthread_join ( thread_ids [ i ], NULL ); }thread_barrier_destroy ( & barrier ); printf ( "Barrera de hilos levantada \n " ); // Esta línea no se llamará ya que TOTAL_THREADS < THREAD_BARRIERS_NUMBER }

Esta versión de la implementación de barrera centralizada anterior introduce dos nuevas variables: [ 1 ]

  • local_flag: Un valor booleano local para cada hilo que permite comprobar si THREAD_BARRIERS_NUMBERlos hilos han llegado a la barrera.
  • flag: Un indicador booleano que struct Barrierseñala si THREAD_BARRIERS_NUMBERlos hilos han llegado a la barrera.

Cuando un hilo se detiene en la barrera, local_flagel valor de se invierte. [ 1 ] Cuando hay menos de THREAD_BARRIERS_NUMBERhilos deteniéndose en la barrera de hilos, esos hilos seguirán esperando con la condición de que barrier.flagno sea igual a local_flag.

Cuando hay exactamente THREAD_BARRIERS_NUMBERhilos que se detienen en la barrera de hilos, thread_countse restablece a 0 y flagse establece en local_flag.

Combinando barrera de árboles

Un problema potencial de la implementación de barrera centralizada es que, debido a que todos los hilos acceden repetidamente a la variable global para pasar/detenerse, el tráfico de comunicación es alto, lo que disminuye la escalabilidad . Este problema se puede resolver reagrupando los hilos y utilizando una barrera multinivel, como una barrera de árbol combinatorio. Las implementaciones de hardware pueden tener mayor escalabilidad. Una barrera de árbol combinatorio es una forma jerárquica de implementar barreras para resolver problemas de escalabilidad evitando que todos los hilos se queden bloqueados en la misma ubicación. [ 4 ]

En unk{\displaystyle k}-barrera de árbol, todos los hilos se dividen por igual en subgrupos dek{\displaystyle k}Los hilos y una primera ronda de sincronizaciones se realizan dentro de estos subgrupos. Una vez que todos los subgrupos han completado la sincronización, el primer hilo de cada subgrupo entra en un segundo nivel para una sincronización adicional. En el segundo nivel, como en el primer nivel, los hilos forman nuevos subgrupos dek{\displaystyle k}Los hilos se sincronizan dentro de los grupos, enviando un hilo de cada subgrupo al siguiente nivel y así sucesivamente, hasta que en el nivel final solo sea necesario sincronizar un subgrupo. Tras alcanzar el nivel final de sincronización, se transmite la señal de liberación a los niveles superiores y todos los hilos superan la barrera. [ 6 ] [ 7 ]

Implementación de barreras de hardware

Una barrera de hardware utiliza hardware para implementar el modelo de barrera básico anterior. [ 3 ]

La implementación de hardware más sencilla utiliza cables dedicados para transmitir señales e implementar una barrera. Este cable dedicado realiza operaciones OR / AND para funcionar como indicadores de paso/bloqueo y contadores de subprocesos. Para sistemas pequeños, este modelo es suficiente y la velocidad de comunicación no es una preocupación importante. En sistemas multiprocesador grandes, este diseño de hardware puede generar una alta latencia en la implementación de la barrera. La conexión de red entre procesadores es una forma de reducir la latencia, de manera análoga al uso de una barrera de árbol combinatorio. [ 8 ]

Funciones de barrera de subprocesos POSIX

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 dicha barrera. [ 2 ] POSIX Threads ofrece tres API principales:

  • pthread_barrier_init(): Inicializa la barrera de hilos con el número de hilos necesarios para esperar en la barrera para levantarla. [ 9 ]
  • pthread_barrier_destroy(): Destruye la barrera del hilo y libera el recurso. [ 9 ]
  • pthread_barrier_wait(): Bloquea el hilo actual hasta que el número de hilos especificado por pthread_barrier_init()las llamadas pthread_barrier_wait()levante la barrera. [ 10 ]

El siguiente ejemplo en C, que utiliza hilos POSIX, emplea barreras de hilos para bloquear todos los hilos del proceso principal, bloqueando así todo el proceso.

#include <stdio.h> #include <pthread.h>#define TOTAL_THREADS 2 #define THREAD_BARRIERS_NUMBER 3barrera_pthread_t ;​void * thread_func ([[ maybe_unused ]] void * p ) { printf ( "Esperando en la barrera ya que no hay suficientes (%d) hilos en ejecución... \n " , THREAD_BARRIERS_NUMBER ); pthread_barrier_wait ( & barrier ); printf ( "Barrera levantada, el hilo con ID %ld se está ejecutando ahora \n " , pthread_self ()); }int main () { pthread_t thread_ids [ TOTAL_THREADS ];pthread_barrier_init ( & barrera , NULL , NÚMERO_DE_BARRERA_DE_INTERRUPTOS ); para ( int i = 0 ; i < TOTAL_DE_INTERRUPTOS ; i ++ ) { pthread_create ( & thread_ids [ i ], NULL , thread_func , NULL ); }// Como pthread_join() bloquea el proceso hasta que todos los hilos especificados hayan terminado, // y no hay suficientes hilos para esperar en la barrera, este proceso se bloquea. for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) { pthread_join ( thread_ids [ i ], NULL ); } pthread_barrier_destroy ( & barrier ); printf ( "Barrera de hilo levantada \n " ); // Esta línea no se llamará ya que TOTAL_THREADS < THREAD_BARRIERS_NUMBER }

Como el proceso principal está bloqueado y nunca se alcanza la línea "Se levanta la barrera del hilo" , el resultado de ese código fuente es:

Esperando en la barrera ya que no hay suficientes (3) hilos en ejecución... Esperando en la barrera ya que no hay suficientes (3) hilos en ejecución...

Solo se crean dos hilos, ambos con thread_func()como manejador de función de hilo, que llama a pthread_barrier_wait(&barrier), mientras que la barrera de hilo espera que tres hilos llamen pthread_barrier_wait()para poder levantarse.

Al cambiar TOTAL_THREADSa 3, se levanta la barrera del hilo:

Esperando en la barrera ya que no hay suficientes (3) hilos en ejecución... Esperando en la barrera ya que no hay suficientes (3) hilos en ejecución... Esperando en la barrera ya que no hay suficientes (3) hilos en ejecución... La barrera se ha levantado, el hilo con ID 140643372406528 se está ejecutando ahora. La barrera se ha levantado, el hilo con ID 140643380799232 se está ejecutando ahora. La barrera se ha levantado, el hilo con ID 140643389191936 se está ejecutando ahora. Barrera de hilos levantada.

Como main()se trata como un hilo (es decir, el hilo "principal" del proceso [ 11 ] ), llamar pthread_barrier_wait()a dentro main()bloqueará todo el proceso hasta que otros hilos alcancen la barrera. El siguiente ejemplo, usando barreras de hilos con pthread_barrier_wait()dentro main()bloquea el hilo principal durante 5 segundos mientras espera a que los dos hilos "recién creados" alcancen la barrera de hilos.

#include <stdio.h> #include <pthreads.h>#define TOTAL_THREADS 2 #define THREAD_BARRIERS_NUMBER 3barrera_pthread_t ;​void * thread_func ([[ maybe_unused ]] void * p ) { printf ( "Esperando en la barrera ya que no hay suficientes (%d) hilos en ejecución... \n " , THREAD_BARRIERS_NUMBER ); sleep ( 5 ); pthread_barrier_wait ( & barrier ); printf ( "Barrera levantada, el hilo con ID %ld se está ejecutando ahora \n " , pthread_self ()); }int main () { pthread_t thread_ids [ TOTAL_THREADS ];pthread_barrier_init ( & barrera , NULL , NÚMERO_DE_BARRERA_DE_INTERRUPTOS ); para ( int i = 0 ; i < TOTAL_DE_INTERRUPTOS ; i ++ ) { pthread_create ( & thread_ids [ i ], NULL , thread_func , NULL ); }pthread_barrier_wait ( & barrera );printf ( "Barrera de subprocesos levantada \n " ); // Esta línea no se llamará ya que TOTAL_THREADS < THREAD_BARRIERS_NUMBER pthread_barrier_destroy ( & barrera ); }

Este ejemplo evita pthread_join()esperar a que los dos hilos "recién creados" finalicen. En su pthread_barrier_wait()interior , llama main()a una función para bloquear el hilo principal, de modo que el proceso se bloquea hasta que los dos hilos terminan su operación tras esperar 5 segundos.

Véase también

Referencias

  1. 1 2 3 4 5 "Implementando barreras" . Universidad Carnegie Mellon. Archivado del original el 20 de enero de 2018. Recuperado el 2 de agosto de 2017 .
  2. 1 2 Sistema Operativo GNU. "Implementación de pthread_barrier" . gnu.org . Consultado el 2 de marzo de 2024 .
  3. 1 2 3 Solihin, Yan (2015-01-01). Fundamentos de la arquitectura multinúcleo paralela (1.ª ed.). Chapman & Hall/CRC. ISBN  978-1482211184.
  4. 1 2 Culler, David (1998). Arquitectura de computadoras paralelas: un enfoque de hardware/software . Gulf Professional. ISBN 978-1558603431.
  5. ↑ Culler, David (1998). Arquitectura de computadoras paralelas: un enfoque de hardware/software . Gulf Professional. ISBN 978-1558603431.
  6. ^ Nanjegowda , Ramachandra; Hernández, Óscar; Chapman, Bárbara ; Jin, Haoqiang H. (3 de junio de 2009). Müller, Matías S.; Supinski, Bronis R. de; Chapman, Barbara M. (eds.). "Evolución de OpenMP en una era de paralelismo extremo" . Apuntes de conferencias sobre informática. Springer Berlín Heidelberg. págs. 42 –52. doi : 10.1007/978-3-642-02303-3_4 . ISBN  9783642022845.
  7. ↑ Nikolopoulos, Dimitrios S.; Papatheodorou, Theodore S. (1999-01-01). "Una evaluación arquitectónica cuantitativa de algoritmos y disciplinas de sincronización en sistemas ccNUMA". Actas de la 13.ª conferencia internacional sobre supercomputación . ICS '99. Nueva York, NY, EE. UU.: ACM. págs. 319–328 . doi : 10.1145/305138.305209 . ISBN  978-1581131642. S2CID 6097544 . Archivado del original el 25-07-2017 . Recuperado el 18-01-2019 . 
  8. ↑ NR Adiga, et al. Una visión general de la supercomputadora BlueGene/L. Actas de la Conferencia sobre Redes y Computación de Alto Rendimiento, 2002.
  9. 1 2 "pthread_barrier_init(), pthread_barrier_destroy()" . Página man de Linux . Consultado el 16 de marzo de 2024 .
  10. ↑ "pthread_barrier_wait()" . Página man de Linux . Consultado el 16 de marzo de 2024 .
  11. ↑ "¿Cómo obtener el número de procesos e hilos en un programa C?" . stackoverflow . Consultado el 16 de marzo de 2024 .

"Programación paralela con sincronización de barrera" . sourceallies.com . Marzo de 2012.

Obtenido de " https://en.wikipedia.org/w/index.php?title=Barrier_(computer_science)&oldid=1348947802 "