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 tiempo determinado. Ha sido una tradición de la informática describir algoritmos en serie en modelos de máquinas abstractas , a menudo la conocida como máquina de acceso aleatorio . De manera similar, muchos investigadores en informática han utilizado la llamada máquina paralela de acceso aleatorio (PRAM) como máquina abstracta paralela (memoria compartida). [1] [2]
Muchos algoritmos paralelos se ejecutan simultáneamente (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.
Los algoritmos varían significativamente en cuanto a su paralelización, desde fácilmente paralelizables hasta completamente incomparables. 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; a estos se les llama problemas vergonzosamente paralelos . Los ejemplos incluyen muchos algoritmos para resolver cubos de Rubik y encontrar valores que resulten en un hash determinado . [ cita necesaria ]
Algunos problemas no se pueden dividir en partes paralelas, ya que requieren los resultados de un paso anterior para continuar efectivamente con el siguiente; estos se llamanProblemas inherentemente seriales .métodos numéricositerativos, comoel método de Newton, soluciones iterativas alproblema de los tres cuerposy la mayoría de los algoritmos disponibles para calcularpi(π).[ cita necesaria ]Algunos algoritmos secuenciales se pueden convertir en algoritmos paralelos mediantela paralelización automática.[3]
Los algoritmos paralelos en dispositivos individuales se han vuelto más comunes desde principios de la década de 2000 debido a mejoras sustanciales en los sistemas multiprocesamiento y el aumento de los procesadores multinúcleo . Hasta finales de 2004, el rendimiento de los procesadores de un solo núcleo aumentó rápidamente mediante el escalado de frecuencia y, por lo tanto, era más fácil construir una computadora con un único núcleo rápido que una con muchos núcleos más lentos con el mismo rendimiento , por lo que los sistemas multinúcleo tenían una utilidad más limitada. usar. Sin embargo, desde 2004, el escalado de frecuencia chocó contra un muro y, por lo tanto, los sistemas multinúcleo se han generalizado, haciendo que los algoritmos paralelos sean de uso más generalizado.
El costo o la complejidad de los algoritmos en serie se estima en términos del espacio (memoria) y el tiempo (ciclos de procesador) que ocupan. Los algoritmos paralelos necesitan optimizar un recurso más, la comunicación entre diferentes procesadores. Hay dos formas en que se comunican los procesadores paralelos: memoria compartida o transmisión de mensajes.
El procesamiento de memoria compartida necesita 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 gastos generales 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 barras transversales 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 procesadores adicionales supera el beneficio de agregar otro procesador, se produce una desaceleración paralela .
Otro problema con los algoritmos paralelos es garantizar que tengan un equilibrio de carga adecuado , asegurando que la carga (trabajo general) esté equilibrada, en lugar de equilibrar el tamaño de entrada. Por ejemplo, verificar la primalidad de todos los números del uno al cien mil es fácil de dividir entre procesadores; sin embargo, si los números simplemente se dividen en partes iguales (1–1000, 1001–2000, etc.), la cantidad de trabajo estará desequilibrada, ya que los números más pequeños son más fáciles de procesar con este algoritmo (más fácil de probar la primalidad), y por lo tanto, algunos procesadores tendrán más trabajo que hacer que otros, que permanecerán inactivos hasta que se completen los procesadores cargados.
Un subtipo de algoritmos paralelos, los algoritmos distribuidos , son algoritmos diseñados para funcionar en entornos informáticos distribuidos y en clústeres , donde es necesario abordar preocupaciones adicionales más allá del alcance de los algoritmos paralelos "clásicos".