La computadora abstracta en paralelo síncrono masivo ( BSP ) es un modelo puente para diseñar algoritmos paralelos . Es similar al modelo de máquina de acceso aleatorio paralelo (PRAM), pero a diferencia de PRAM, BSP no da por sentadas la comunicación y la sincronización. De hecho, cuantificar la sincronización y la comunicación necesarias es una parte importante del análisis de un algoritmo BSP.
Historia
El modelo BSP fue desarrollado por Leslie Valiant de la Universidad de Harvard durante la década de 1980. El artículo definitivo se publicó en 1990 [1].
Entre 1990 y 1992, Leslie Valiant y Bill McColl de la Universidad de Oxford trabajaron en ideas para un modelo de programación BSP de memoria distribuida, en Princeton y Harvard. Entre 1992 y 1997, McColl dirigió un gran equipo de investigación en Oxford que desarrolló varias bibliotecas, lenguajes y herramientas de programación BSP, y también numerosos algoritmos BSP masivamente paralelos. Con el interés y el impulso creciendo, McColl dirigió un grupo de Oxford, Harvard, Florida, Princeton, Bell Labs, Columbia y Utrecht que desarrolló y publicó el Estándar BSPlib para la programación BSP en 1996.
Valiant desarrolló una extensión del modelo BSP en la década de 2000, lo que llevó a la publicación del modelo Multi-BSP en 2011. [2]
En 2017, McColl desarrolló una nueva extensión importante del modelo BSP que proporciona tolerancia a fallas y tolerancia de cola para cálculos paralelos a gran escala en IA, análisis y computación de alto rendimiento (HPC). [3]
El modelo BSP
Descripción general
Una computadora BSP consta de:
- Componentes capaces de procesar y / o transacciones de memoria local (es decir, procesadores),
- Una red que enruta mensajes entre pares de dichos componentes, y
- Una instalación de hardware que permite la sincronización de todos o un subconjunto de componentes.
Esto se interpreta comúnmente como un conjunto de procesadores que pueden seguir diferentes hilos de cálculo, con cada procesador equipado con una memoria local rápida e interconectado por una red de comunicación.
Los algoritmos BSP se basan en gran medida en la tercera característica; un cálculo procede en una serie de superpasos globales , que consta de tres componentes:
- Cálculo concurrente: cada procesador participante puede realizar cálculos locales, es decir, cada proceso solo puede hacer uso de valores almacenados en la memoria rápida local del procesador. Los cálculos ocurren de forma asincrónica de todos los demás, pero pueden superponerse con la comunicación.
- Comunicación: los procesos intercambian datos para facilitar el almacenamiento remoto de datos.
- Sincronización de barrera : cuando un proceso alcanza este punto (la barrera ), espera hasta que todos los demás procesos hayan alcanzado la misma barrera.
Las acciones de computación y comunicación no tienen que ser ordenadas a tiempo. La comunicación generalmente toma la forma de llamadas de acceso directo remoto a memoria (RDMA) PUT y GET unilaterales , en lugar de llamadas de envío y recepción de mensajes de dos caras emparejadas .
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/e/ee/Bsp.wiki.fig1.svg/270px-Bsp.wiki.fig1.svg.png)
La sincronización de barrera concluye el superpaso: asegura que todas las comunicaciones unilaterales se concluyan correctamente. Los sistemas basados en la comunicación bilateral incluyen implícitamente este costo de sincronización para cada mensaje enviado. El método de sincronización de barrera se basa en la instalación de hardware de la computadora BSP. En el documento original de Valiant, esta instalación verifica periódicamente si el final del superpaso actual se alcanza a nivel mundial. El período de esta verificación se denota por. [1]
El modelo BSP también es adecuado para la administración automática de memoria para la computación de memoria distribuida a través de la descomposición excesiva del problema y la suscripción excesiva de los procesadores. El cálculo se divide en más procesos lógicos que procesadores físicos, y los procesos se asignan aleatoriamente a los procesadores. Se puede demostrar estadísticamente que esta estrategia conduce a un equilibrio de carga casi perfecto, tanto del trabajo como de la comunicación.
Comunicación
En muchos sistemas de programación paralela, las comunicaciones se consideran a nivel de acciones individuales, como enviar y recibir un mensaje o transferencia de memoria a memoria. Es difícil trabajar con esto ya que hay muchas acciones de comunicación simultáneas en un programa paralelo y sus interacciones son típicamente complejas. En particular, es difícil decir mucho sobre el tiempo que tomará completar una sola acción de comunicación.
El modelo BSP considera acciones de comunicación en masa . Esto tiene el efecto de que se puede dar un límite superior en el tiempo necesario para comunicar un conjunto de datos. BSP considera todas las acciones de comunicación de un superpaso como una unidad y asume que todos los mensajes individuales enviados como parte de esta unidad tienen un tamaño fijo.
El número máximo de mensajes entrantes o salientes para un superpaso se indica mediante . La capacidad de una red de comunicaciones para entregar datos se captura mediante un parámetro, definido de tal manera que lleva tiempo para que un procesador entregue mensajes de tamaño 1.
Un mensaje de extensión obviamente tarda más en enviarse que un mensaje de tamaño 1. Sin embargo, el modelo BSP no distingue entre una longitud de mensaje de o mensajes de longitud 1. En cualquier caso, se dice que el costo es .
El parámetro depende de lo siguiente:
- Los protocolos utilizados para interactuar dentro de la red de comunicaciones.
- Gestión de búfer tanto por los procesadores como por la red de comunicaciones.
- La estrategia de enrutamiento utilizada en la red.
- El sistema de tiempo de ejecución BSP .
En la práctica, se determina empíricamente para cada computadora en paralelo. Tenga en cuenta que no es el tiempo de entrega normalizado de una sola palabra, sino el tiempo de entrega de una sola palabra en condiciones de tráfico continuo.
Barreras
La comunicación unilateral del modelo BSP requiere sincronización de barrera . Las barreras son potencialmente costosas, pero evitan la posibilidad de un punto muerto o un bloqueo activo , ya que las barreras no pueden crear dependencias de datos circulares . Las herramientas para detectarlas y tratarlas son innecesarias. Las barreras también permiten nuevas formas de tolerancia a fallas [ cita requerida ] .
El costo de la sincronización de barreras está influenciado por un par de problemas:
- El costo impuesto por la variación en el tiempo de finalización de los cálculos concurrentes participantes. Tomemos el ejemplo en el que todos menos uno de los procesos han completado su trabajo para este superpaso y están esperando el último proceso, que todavía tiene mucho trabajo por completar. Lo mejor que puede hacer una implementación es asegurarse de que cada proceso funcione aproximadamente con el mismo tamaño de problema.
- El costo de alcanzar un estado globalmente consistente en todos los procesadores. Esto depende de la red de comunicación, pero también de si hay hardware especial disponible para la sincronización y de la forma en que los procesadores manejan las interrupciones.
El costo de una sincronización de barrera se denota por . Tenga en cuenta quesi el mecanismo de sincronización de la computadora BSP es el sugerido por Valiant. [1] En la práctica, un valor de se determina empíricamente.
En las computadoras grandes, las barreras son costosas y esto es cada vez más a gran escala. Existe una gran cantidad de literatura sobre la eliminación de puntos de sincronización de los algoritmos existentes en el contexto de la computación BSP y más allá. Por ejemplo, muchos algoritmos permiten la detección local del final global de un superpaso simplemente comparando la información local con el número de mensajes ya recibidos. Esto lleva a cero el costo de una sincronización global, en comparación con la latencia de comunicación mínima requerida. [4] Sin embargo, también se espera que esta latencia mínima aumente aún más para futuras arquitecturas de supercomputadoras e interconexiones de red; el modelo BSP, junto con otros modelos de cálculo paralelo, requieren una adaptación para hacer frente a esta tendencia. Multi-BSP es una solución basada en BSP. [2]
Costo algorítmico
El costo de un superpaso se determina como la suma de tres términos:
- El costo de la computación local de mayor duración
- El costo de la comunicación global entre los procesadores.
- El costo de la sincronización de la barrera al final del superpaso
Por lo tanto, el costo de un superpaso por procesadores:
dónde es el costo de la computación local en proceso , y es la cantidad de mensajes enviados o recibidos por proceso . Tenga en cuenta que aquí se asumen procesadores homogéneos. Es más común que la expresión se escriba como dónde y son máximos. Entonces, el costo del algoritmo es la suma de los costos de cada superpaso.
dónde es el número de superpasos.
, , y generalmente se modelan como funciones, que varían con el tamaño del problema. Estas tres características de un algoritmo BSP generalmente se describen en términos de notación asintótica , p. Ej..
Extensiones y usos
El interés en BSP se ha disparado, y Google lo adoptó como una tecnología importante para el análisis de gráficos a escala masiva a través de Pregel y MapReduce . Además, con la próxima generación de Hadoop que desacopla el modelo MapReduce del resto de la infraestructura de Hadoop, ahora hay proyectos activos de código abierto para agregar programación BSP explícita, así como otros modelos de programación paralela de alto rendimiento, además de Hadoop. Algunos ejemplos son Apache Hama y Apache Giraph . [5]
BSP ha sido extendido por muchos autores para abordar las preocupaciones sobre la inadecuación de BSP para modelar arquitecturas específicas o paradigmas computacionales. Un ejemplo de esto es el modelo BSP descomponible. El modelo también se ha utilizado en la creación de una serie de nuevos lenguajes de programación e interfaces, como Bulk Synchronous Parallel ML (BSML), BSPLib, [6] Apache Hama , [5] y Pregel. [7]
Implementaciones notables del estándar BSPLib son la biblioteca BSP de la Universidad de Paderborn [8] y el conjunto de herramientas Oxford BSP de Jonathan Hill. [9] Las implementaciones modernas incluyen BSPonMPI [10] (que simula BSP en la parte superior de la interfaz de paso de mensajes ) y MulticoreBSP [11] [12] (una implementación novedosa dirigida a arquitecturas modernas de memoria compartida). MulticoreBSP para C es especialmente notable por su capacidad de iniciar ejecuciones BSP anidadas, lo que permite la programación Multi-BSP explícita.
Ver también
- Exclusión mutua automática
- Apache Hama
- Jirafa apache
- Clúster de computadoras
- Computación concurrente
- Simultaneidad (informática)
- Programación de flujo de datos
- Computación en cuadrícula
- Máquina LogP
- Computación paralela
- Modelo de programación paralela
Referencias
- ^ a b c Leslie G. Valiant, Un modelo puente para el cálculo paralelo, Comunicaciones del ACM, volumen 33 número 8, agosto de 1990 [1]
- ↑ a b Valiant, LG (2011). Un modelo de puente para la computación de múltiples núcleos. Revista de Ciencias de la Computación y Sistemas , 77 (1), 154-166 [2]
- ^ Un modelo puente para computación en la nube de alto rendimiento por Bill McColl en la 18a Conferencia SIAM sobre procesamiento paralelo para computación científica (2018), http://meetings.siam.org/sess/dsp_talk.cfm?p=88973 Archivado el 12 de diciembre de 2019 11 en la Wayback Machine .
- ^ Alpert, R. y Philbin, J. (1997). cBSP: Sincronización de coste cero en un modelo BSP modificado. Instituto de Investigación NEC, 4 Independence Way, Princeton NJ, 8540, [3] .
- ^ a b Apache Hama
- ^ BSPlib
- ^ Pregel
- ^ Biblioteca BSP (PUB) de la Universidad de Paderborn - Diseño, implementación y rendimiento Instituto Heinz Nixdorf, Departamento de Ciencias de la Computación, Universidad de Paderborn, Alemania, informe técnico Archivado 2001-06-05 en Wayback Machine .
- ^ Jonathan Hill: El conjunto de herramientas de Oxford BSP , 1998.
- ^ Wijnand J. Suijlen: BSPonMPI , 2006.
- ^ MulticoreBSP para C: una biblioteca de alto rendimiento para la programación paralela de memoria compartida de AN Yzelman, RH Bisseling, D. Roose y K. Meerbergen en International Journal of Parallel Programming, en prensa (2013), doi: 10.1109 / TPDS. 2013.31 .
- ^ Una biblioteca paralela síncrona masiva orientada a objetos para programación multinúcleo por AN Yzelman y Rob H. Bisseling en Concurrencia y computación: práctica y experiencia 24 (5), págs. 533-553 (2012), doi: 10.1002 / cpe.1843 .
enlaces externos
- DB Skillicorn, Jonathan Hill, WF McColl, Preguntas y respuestas sobre BSP [ enlace muerto permanente ] (1996)
- BSP en todo el mundo
- Documentos relacionados con BSP
- (en francés) Bulk Synchronous Parallel ML ( (en inglés) sitio web oficial )
- Apache Hama
- Jirafa apache
- Biblioteca BSP de la Universidad de Paderborn
- BSPonMPI
- BSP multinúcleo