En informática , un algoritmo paralelo , a diferencia de un algoritmo serial tradicional , es un algoritmo que puede realizar múltiples operaciones en un momento dado. Ha sido una tradición de las ciencias de la computación 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). [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 se denominan a menudo " algoritmos secuenciales ", en contraste con los algoritmos concurrentes.
Los algoritmos varían significativamente en cuanto a cuán paralelizables son, desde fácilmente paralelizables hasta completamente no paralelizables. 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; estos se llaman problemas vergonzosamente paralelos . Los ejemplos incluyen muchos algoritmos para resolver cubos de Rubik y encontrar valores que dan como resultado un hash determinado . [ cita requerida ]
Algunos problemas no se pueden dividir en partes paralelas, ya que requieren los resultados de un paso anterior para continuar de manera efectiva con el siguiente paso; estos se denominan problemas inherentemente seriales .Los ejemplos incluyenmétodos numéricos, comoel método de Newton, soluciones iterativas al problema de lostres cuerposy la mayoría de los algoritmos disponibles para calcularpi(π).[ cita requerida ]Algunos algoritmos secuenciales se pueden convertir en algoritmos paralelos usandoparalelizació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 las mejoras sustanciales en los sistemas de multiprocesamiento y al auge de los procesadores de varios núcleos . Hasta finales de 2004, el rendimiento del procesador de un solo núcleo aumentaba rápidamente a través del escalado 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.