De Wikipedia, la enciclopedia libre
Ir a navegaciónSaltar a buscar

En la computación paralela , una barrera es un tipo de método de sincronización . 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.

Muchas rutinas colectivas y lenguajes paralelos basados ​​en directivas imponen barreras implícitas. Por ejemplo, no se permitirá que un ciclo do paralelo en Fortran con OpenMP continúe en ningún hilo hasta que se complete la última iteración. Esto es en caso de que el programa se base en el resultado del ciclo 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 bajado . El término pestillo se usa a veces para referirse a una barrera que comienza en el estado elevado y no se puede volver a levantar una vez que está en el estado bajado. 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 un número predeterminado de subprocesos / procesos.

Implementación

La barrera básica tiene principalmente dos variables, una de las cuales registra el estado de paso / parada de la barrera y la otra mantiene el número total de subprocesos que han entrado en la barrera. El estado de barrera se inicializó para ser "detenido" por los primeros subprocesos que entraban en la barrera. Siempre que un hilo ingrese, basado en el número de hilos que ya están en la barrera, solo si es el último, el hilo establece el estado de la barrera en "pasar" para que todos los hilos puedan salir de la barrera. Por otro lado, cuando el hilo entrante no es el último, queda atrapado en la barrera y sigue probando si el estado de la barrera ha cambiado de "detener" a "pasar", y sale solo cuando el estado de la barrera cambia a "pasar". El siguiente código de C ++ demuestra este procedimiento. [1] [2]

estructura  tipo_barrera{ // cuántos procesadores han entrado en la barrera // inicializar a 0 int  reach_counter ; // cuántos procesadores han salido de la barrera // inicializar ap int  dejar_contador ; int  bandera ; std :: bloqueo mutex  ;};// barrera para procesadores p barrera vacía ( tipo_barrera *  b ,  int  p ){ b -> bloquear . bloquear (); si  ( b -> llegada_contador  ==  0 ) { b -> bloquear . desbloquear (); while  ( b -> dejar_contador  ! =  p );  // esperar a que todos se vayan antes de despejar b -> bloquear . bloquear (); b -> bandera  =  0 ;  // el primero en llegar borra la bandera } b -> llegada_contador ++ ; if  ( b -> arrival_counter  ==  p )  // el último en llegar establece la bandera { b -> llegada_contador  =  0 ; b -> dejar_contador  =  0 ; b -> bandera  =  1 ; } b -> bloquear . desbloquear (); while  ( b -> bandera  ==  0 );  // espera la bandera b -> bloquear . bloquear (); b -> dejar_contador ++ ; b -> bloquear . desbloquear ();}

El problema potencial es:

  1. Debido a que todos los subprocesos 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, Combining Tree Barrier. Además, las implementaciones de hardware pueden tener la ventaja de una mayor escalabilidad .

Barrera centralizada de inversión de sentido

En lugar de utilizar el mismo valor para representar paso / parada, las barreras secuenciales utilizan valores opuestos para el estado de paso / parada. Por ejemplo, si la barrera 1 usa 0 para detener los hilos, la barrera 2 usará 1 para detener los hilos y la barrera 3 usará 0 para detener los hilos nuevamente y así sucesivamente. [3] El siguiente código C ++ demuestra esto. [1] [4] [2]

estructura  tipo_barrera{ int  contador ;  // inicializar a 0 int  bandera ;  // inicializar a 0 std :: bloqueo mutex  ;};int  local_sense  =  0 ;  // privado por procesador// barrera para procesadores p barrera vacía ( tipo_barrera *  b ,  int  p ){ sentido_local  =  1  -  sentido_local ; b -> bloquear . bloquear (); b -> contador ++ ; int  llegó  =  b -> contador ; si  ( llegó  ==  p )  // el último en llegar establece la bandera { b -> bloquear . desbloquear (); b -> contador  =  0 ; // valla de memoria para asegurar que el cambio al contador // se ve antes del cambio de bandera b -> bandera  =  sentido_local ; } demás { b -> bloquear . desbloquear (); while  ( b -> bandera  ! =  sentido_local );  // espera la bandera }}

Combinando la barrera de los árboles

Una barrera de árbol combinada es una forma jerárquica de implementar una barrera para resolver la escalabilidad al evitar el caso de que todos los subprocesos estén girando en la misma ubicación. [3]

En k-Tree Barrier, los subprocesos puto se dividen igualmente en subgrupos de k subprocesos y se realizan sincronizaciones de primera ronda 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 primer nivel, los hilos forman nuevos subgrupos de k hilos y se sincronizan dentro de los grupos, enviando un hilo en 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 de nivel final, la señal de liberación se transmite a los niveles superiores y todos los hilos pasan la barrera. [4] [5]

Implementación de barrera de hardware

La barrera de hardware utiliza hardware para implementar el modelo de barrera básico anterior. [1]

La implementación de hardware más simple utiliza cables dedicados para transmitir la señal 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 grandes sistemas multiprocesador, este diseño de hardware puede hacer que la implementación de barreras tenga una alta latencia. La conexión de red entre procesadores es una implementación para reducir la latencia, que es análoga a Combining Tree Barrier. [6]

Ver también

Referencias

  1. ↑ a b c Solihin, Yan (1 de enero de 2015). Fundamentos de la arquitectura multinúcleo paralela (1ª ed.). Chapman y Hall / CRC. ISBN 978-1482211184.
  2. ^ a b "Implementación de barreras" . Universidad de Carnegie mellon.
  3. ↑ a b Culler, David (1998). Arquitectura informática paralela, un enfoque de hardware / software . ISBN 978-1558603431.
  4. ^ a b Nanjegowda, Ramachandra; Hernández, Oscar; Chapman, Barbara; Jin, Haoqiang H. (3 de junio de 2009). Müller, Matthias S .; Supinski, Bronis R. de; Chapman, Barbara M. (eds.). Evolución de OpenMP en una era de paralelismo extremo . Apuntes de conferencias en Ciencias de la Computación. Springer Berlín Heidelberg. págs.  42 –52. doi : 10.1007 / 978-3-642-02303-3_4 . ISBN 9783642022845.
  5. ↑ Nikolopoulos, Dimitrios S .; Papatheodorou, Theodore S. (1 de enero de 1999). Una evaluación arquitectónica cuantitativa de algoritmos y disciplinas de sincronización en sistemas ccNUMA: el caso de la SGI Origin2000 . Actas de la XIII Conferencia Internacional de Supercomputación . ICS '99. Nueva York, NY, EE.UU .: ACM. págs. 319–328. doi : 10.1145 / 305138.305209 . ISBN 978-1581131642. S2CID  6097544 .
  6. ^ NR Adiga, et al. Una descripción general de la supercomputadora BlueGene / L. Actas de la Conferencia sobre redes e informática de alto rendimiento, 2002.

[1]

  1. ^ "Programación en paralelo con sincronización de barrera" . Marzo de 2012.