Paralelo sincrónico masivo

La computadora abstracta de sincronización paralela en masa ( BSP ) es un modelo de 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 sentada 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.

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 en 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, incluidos muchos ejemplos tempranos de algoritmos paralelos de alto rendimiento que evitan la comunicación ^[2] y algoritmos paralelos recursivos "inmortales" que logran el mejor rendimiento posible y compensaciones paramétricas óptimas. ^[3]

Ante el creciente interés y el impulso, McColl dirigió un grupo de Oxford, Harvard, Florida, Princeton, Bell Labs, Columbia y Utrecht que desarrolló y publicó el estándar BSPlib para programación BSP en 1996. ^[4]

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. ^[5]

En 2017, McColl desarrolló una nueva extensión importante del modelo BSP que proporciona tolerancia a fallas y tolerancia a colas para cálculos paralelos a gran escala en IA, análisis y computación de alto rendimiento (HPC). ^[6] Véase también ^[7]

Una computadora BSP consta de lo siguiente:

• Componentes capaces de procesar y/o realizar 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 memoria local rápida e interconectado por una red de comunicación.

Los algoritmos BSP dependen en gran medida de la tercera característica: un cálculo se realiza en una serie de superpasos globales , que constan de tres componentes:

• Computación 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 se realizan de forma asincrónica con respecto a 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 llega a este punto (la barrera ), espera hasta que todos los demás procesos hayan alcanzado la misma barrera.

Las acciones de cálculo y comunicación no tienen por qué estar ordenadas en el tiempo. La comunicación normalmente toma la forma de llamadas de acceso directo a memoria remota (RDMA) PUT y GET unilaterales en lugar de llamadas de envío y recepción de mensajes bilaterales .

La sincronización de barrera concluye el superpaso: garantiza que todas las comunicaciones unilaterales concluyan correctamente. Los sistemas basados ​​en comunicaciones bilaterales incluyen este costo de sincronización implícitamente para cada mensaje enviado. El método de sincronización de barrera se basa en la función de hardware de la computadora BSP. En el artículo original de Valiant, esta función verifica periódicamente si se alcanza el final del superpaso actual de manera global. El período de esta verificación se denota por . ^[1]${\estilo de visualización L}$

El modelo BSP también es adecuado para la gestión automática de memoria para computación con memoria distribuida mediante la descomposición excesiva del problema y la sobresuscripción de 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 de trabajo como de 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 una transferencia de memoria a memoria. Esto es difícil de manejar, ya que hay muchas acciones de comunicación simultáneas en un programa paralelo y sus interacciones suelen ser complejas. En particular, es difícil decir mucho sobre el tiempo que tardará en completarse una sola acción de comunicación.

El modelo BSP considera las acciones de comunicación en masa . Esto tiene el efecto de que se puede dar un límite superior al tiempo que lleva comunicar un conjunto de datos. BSP considera todas las acciones de comunicación de un superpaso como una unidad y supone 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 denota por . La capacidad de una red de comunicación para entregar datos se captura mediante un parámetro , definido de modo que un procesador tarde un tiempo en entregar mensajes de tamaño 1. ${\estilo de visualización h}$${\estilo de visualización g}$${\estilo de visualización hg}$${\estilo de visualización h}$

Obviamente, un mensaje de longitud tarda más en enviarse que un mensaje de tamaño 1. Sin embargo, el modelo BSP no hace distinción entre una longitud de mensaje de o mensajes de longitud 1. En cualquier caso, se dice que el coste es . ${\estilo de visualización m}$${\estilo de visualización m}$${\estilo de visualización m}$${\estilo de visualización mg}$

El parámetro depende de lo siguiente: ${\estilo de visualización g}$

• Los protocolos utilizados para interactuar dentro de la red de comunicación.
• Gestión de buffer tanto por los procesadores como por la red de comunicación.
• 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 paralela. Nótese que no es el tiempo de entrega de una sola palabra normalizado, sino el tiempo de entrega de una sola palabra en condiciones de tráfico continuo. ${\estilo de visualización g}$${\estilo de visualización g}$

La comunicación unilateral del modelo BSP requiere sincronización de barreras . Las barreras son potencialmente costosas, pero evitan la posibilidad de bloqueos o interbloqueos, ya que 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 cuestiones:

• El costo impuesto por la variación en el tiempo de finalización de los cálculos concurrentes que participan. Tomemos el ejemplo en el que todos los procesos, menos uno, han completado su trabajo para este superpaso y están esperando al último proceso, que todavía tiene mucho trabajo por completar. Lo mejor que puede hacer una implementación es garantizar que cada proceso trabaje con un tamaño de problema aproximadamente similar.
• 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 . Nótese que si el mecanismo de sincronización de la computadora BSP es como lo sugiere Valiant. ^[1] En la práctica, un valor de se determina empíricamente. ${\estilo de visualización l}$${\displaystyle l<L}$${\estilo de visualización l}$

En los ordenadores de gran tamaño, las barreras son caras, y esto es cada vez más así en las grandes escalas. 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 la cantidad de mensajes ya recibidos. Esto reduce a cero el costo de la sincronización global, en comparación con la latencia mínima requerida de la comunicación. ^[8] Sin embargo, también se espera que esta latencia mínima aumente aún más para las futuras arquitecturas de supercomputadoras e interconexiones de red; el modelo BSP, junto con otros modelos para computación paralela, requieren una adaptación para hacer frente a esta tendencia. Multi-BSP es una solución basada en BSP. ^[5]

El coste de un superpaso se determina como la suma de tres términos:

• El costo del cálculo local de mayor duración
• El coste de la comunicación global entre los procesadores
• El costo de la sincronización de la barrera al final del superpaso

Así, el coste de un superpaso para los procesadores: ${\estilo de visualización p}$

${\displaystyle máx_{i=1}^{p}(w_{i})+máx_{i=1}^{p}(h_{i}g)+l}$ donde es el costo del cómputo local en el proceso y es la cantidad de mensajes enviados o recibidos por el proceso . Tenga en cuenta que aquí se suponen procesadores homogéneos. Es más común que la expresión se escriba como donde y son máximos. El costo de un algoritmo BSP completo es la suma del costo de cada superpaso. $estilo de visualización w_{i}}$${\estilo de visualización i}$$estilo de visualización h_{i}}$${\estilo de visualización i}$${\displaystyle w+hg+l}$${\estilo de visualización w}$${\estilo de visualización h}$

${\displaystyle W+Hg+Sl=\suma _{s=1}^{S}w_{s}+g\suma _{s=1}^{S}h_{s}+Sl}$ ¿Dónde está el número de superpasos? ${\estilo de visualización S}$

${\estilo de visualización W}$, , y se modelan habitualmente como funciones que varían con el tamaño del problema. Estas tres características de un algoritmo BSP se describen habitualmente en términos de notación asintótica , p. ej., . ${\estilo de visualización H}$${\estilo de visualización S}$${\displaystyle H\in O(n/p)}$

El interés en BSP se ha disparado, y Google lo ha adoptado como una tecnología importante para el análisis de gráficos a gran escala 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 de código abierto activos para agregar programación BSP explícita, así como otros modelos de programación paralela de alto rendimiento, sobre Hadoop. Algunos ejemplos son Apache Hama y Apache Giraph . ^[9]

Muchos autores han ampliado el BSP para abordar las preocupaciones sobre su inadecuación 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, Apache Hama [ ^{9] y Pregel [10]} .

Las implementaciones notables del estándar BSPLib son la biblioteca BSP de la Universidad de Paderborn ^[11] y el conjunto de herramientas BSP de Oxford de Jonathan Hill. ^[12] Las implementaciones modernas incluyen BSPonMPI ^[13] (que simula BSP sobre la interfaz de paso de mensajes ) y MulticoreBSP ^{[14] [15]} (una implementación novedosa dirigida a las arquitecturas modernas de memoria compartida). MulticoreBSP para C es especialmente notable por su capacidad de iniciar ejecuciones BSP anidadas, lo que permite una programación Multi-BSP explícita.

• Exclusión mutua automática
• Apache Hama
• Jirafa apache
• Clúster de ordenadores
• Computación concurrente
• Concurrencia (informática)
• Programación de flujo de datos
• Computación en red
• Máquina LogP
• Computación paralela
• Modelo de programación paralela

• 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) ML paralelo sincrónico masivo ( sitio web oficial)
• Apache Hama
• Jirafa apache
• Biblioteca BSP de la Universidad de Paderborn
• BSPonMPI
• BSP multinúcleo