Algoritmo paralelo

En informática, un algoritmo paralelo, a diferencia de un algoritmo en serie tradicional, es un algoritmo que puede realizar múltiples operaciones en un momento dado. Ha sido una tradición de la informática describir algoritmos en serie en modelos de máquinas abstractas, a menudo las conocidas como máquinas de acceso aleatorio. De manera similar, muchos investigadores de ciencias de la computación han utilizado una máquina paralela de acceso aleatorio (PRAM) como una máquina abstracta paralela (memoria compartida).

Muchos algoritmos paralelos se ejecutan al mismo tiempo, aunque, en general, los algoritmos concurrentes son un concepto distinto, y por lo tanto estos conceptos a menudo se combinan, sin distinguir claramente qué aspecto de un algoritmo es paralelo y cuál es concurrente. Además, los algoritmos no paralelos y no concurrentes a menudo se denominan "algoritmos secuenciales", en contraste con los algoritmos concurrentes.

Paralelizabilidad

Los algoritmos varían significativamente en cuanto a cuán paralelizables son, desde fácilmente paralelizables hasta completamente imposibles de paralelizar. Además, un problema dado puede acomodar diferentes algoritmos, que pueden ser más o menos paralelizables.

Algunos problemas son fáciles de dividir en partes de esta manera; se denominan problemas vergonzosamente paralelos. Los ejemplos incluyen muchos algoritmos para resolver cubos de Rubik y encontrar valores que dan como resultado un problema dado. picadillo.

Algunos problemas no se pueden dividir en partes paralelas, ya que requieren los resultados de un paso anterior para continuar efectivamente con el siguiente paso; se denominan problema inherentemente serials. Los ejemplos incluyen métodos numéricos iterativos, como el método de Newton, soluciones iterativas al problema de los tres cuerpos y la mayoría de los algoritmos disponibles para calcular pi (π). Algunos algoritmos secuenciales se pueden convertir en algoritmos paralelos mediante la paralelización automática.

Motivación

Los algoritmos paralelos en dispositivos individuales se han vuelto más comunes desde principios de la década de 2000 debido a las mejoras sustanciales en los sistemas de multiprocesamiento y al auge de los procesadores de varios núcleos. Hasta finales de 2004, el rendimiento de los procesadores de un solo núcleo aumentó rápidamente a través de la escala de frecuencia y, por lo tanto, era más fácil construir una computadora con un solo núcleo rápido que una con muchos núcleos más lentos con el mismo rendimiento, por lo que los sistemas multinúcleo eran más limitados. usar. Sin embargo, desde 2004, la escala de frecuencia chocó contra un muro y, por lo tanto, los sistemas multinúcleo se han generalizado más, lo que hace que los algoritmos paralelos sean de uso más general.

Problemas

Comunicación

El costo o la complejidad de los algoritmos en serie se estima en términos del espacio (memoria) y el tiempo (ciclos del procesador) que ocupan. Los algoritmos paralelos necesitan optimizar un recurso más, la comunicación entre diferentes procesadores. Hay dos formas en que los procesadores paralelos se comunican, memoria compartida o paso de mensajes.

El procesamiento de memoria compartida necesita un bloqueo adicional para los datos, impone la sobrecarga de ciclos de bus y procesador adicionales, y también serializa una parte del algoritmo.

El procesamiento de paso de mensajes utiliza canales y cuadros de mensajes, pero esta comunicación agrega sobrecarga de transferencia en el bus, necesidad de memoria adicional para colas y cuadros de mensajes y latencia en los mensajes. Los diseños de procesadores paralelos utilizan buses especiales como barra transversal para que la sobrecarga de comunicación sea pequeña, pero es el algoritmo paralelo el que decide el volumen del tráfico.

Si la sobrecarga de comunicación de los procesadores adicionales supera el beneficio de agregar otro procesador, se encuentra con una ralentización paralela.

Equilibrio de carga

Otro problema con los algoritmos paralelos es asegurarse de que tengan un balance de carga adecuado, asegurando que la carga (trabajo general) esté balanceada, en lugar de que el tamaño de la entrada esté balanceado. Por ejemplo, verificar la primalidad de todos los números del uno al cien mil es fácil de dividir entre los procesadores; sin embargo, si los números simplemente se dividen en partes iguales (1 a 1000, 1001 a 2000, etc.), la cantidad de trabajo se desequilibrará, ya que los números más pequeños son más fáciles de procesar con este algoritmo (es más fácil probar la primalidad) y por lo tanto, algunos procesadores tendrán más trabajo que otros, que permanecerán inactivos hasta que los procesadores cargados se completen.

Algoritmos distribuidos

Un subtipo de algoritmos paralelos, los algoritmos distribuidos, son algoritmos diseñados para funcionar en entornos de computación en clúster y de computación distribuida, donde las preocupaciones adicionales van más allá del alcance de "clásico" es necesario abordar los algoritmos paralelos.