Algoritmo paralelo

En informática , un algoritmo paralelo , a diferencia de un algoritmo serial tradicional , es un algoritmo que puede realizar múltiples operaciones en un tiempo determinado. Ha sido una tradición en informática describir los algoritmos seriales en modelos de máquinas abstractas , a menudo conocidas como máquinas de acceso aleatorio . De manera similar, muchos investigadores informáticos han utilizado una denominada máquina de acceso aleatorio paralela (PRAM) como una máquina abstracta paralela (memoria compartida). ^[1]^[2]

Muchos algoritmos paralelos se ejecutan de forma concurrente (aunque, en general, los algoritmos concurrentes son un concepto distinto) y, por lo tanto, estos conceptos suelen confundirse, sin que se pueda distinguir claramente qué aspecto de un algoritmo es paralelo y cuál es concurrente. Además, los algoritmos no paralelos y no concurrentes suelen denominarse " algoritmos secuenciales ", en contraste con los algoritmos concurrentes.

Paralelización

Los algoritmos varían significativamente en cuanto a su grado de paralelización, desde los que son fácilmente paralelizables hasta los que no lo son en absoluto. Además, un problema determinado puede dar cabida a distintos algoritmos, que pueden ser más o menos paralelizables.

Algunos problemas se pueden dividir fácilmente en partes de esta manera; se los llama problemas vergonzosamente paralelos . Algunos ejemplos incluyen muchos algoritmos para resolver cubos de Rubik y encontrar valores que resulten en 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 eficazmente con el siguiente paso; estos se denominanproblemas inherentemente seriales . Los ejemplos incluyen 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 requerida ]}Algunos algoritmos secuenciales se pueden convertir en algoritmos paralelos utilizandoparalelización automática.^[3]

En muchos casos, el desarrollo de un algoritmo paralelo eficaz para la solución de una determinada tarea requiere la incorporación de nuevas ideas y métodos en comparación con la creación de una versión secuencial del algoritmo. Se trata, por ejemplo, de problemas de importancia práctica como la búsqueda de un elemento objetivo en estructuras de datos, la evaluación de una expresión algebraica, etc. ^[4]

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 multinúcleo . Hasta fines 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 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 tenían un uso más limitado. Sin embargo, desde 2004, el escalado de frecuencia se topó con un muro y, por lo tanto, los sistemas multinúcleo se han vuelto más comunes, lo que hace que los algoritmos paralelos sean de uso más general.

Asuntos

Comunicación

El coste o complejidad de los algoritmos seriales se estima en función del espacio (memoria) y tiempo (ciclos de procesador) que ocupan. Los algoritmos paralelos necesitan optimizar un recurso más, la comunicación entre procesadores diferentes. Existen dos formas de comunicación entre procesadores paralelos, 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 crossbar 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 produce una desaceleración paralela .

Equilibrio de carga

Otro problema con los algoritmos paralelos es asegurar que estén adecuadamente balanceados en cuanto a carga , al asegurar que la carga (trabajo total) esté balanceada, en lugar de que el tamaño de entrada esté balanceado. Por ejemplo, verificar la primalidad de todos los números desde uno hasta cien mil es fácil de dividir entre procesadores; sin embargo, si los números simplemente se dividen de manera uniforme (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 por este algoritmo (es más fácil probar la primalidad), y por lo tanto algunos procesadores tendrán más trabajo que hacer que los otros, que permanecerán inactivos hasta que los procesadores cargados 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 computación distribuida , donde es necesario abordar cuestiones adicionales que van más allá del alcance de los algoritmos paralelos "clásicos".

Véase también

Referencias

^ Blelloch, Guy E.; Maggs, Bruce M. "Algoritmos paralelos" (PDF) . EE. UU.: Facultad de Ciencias de la Computación, Universidad Carnegie Mellon . Consultado el 27 de julio de 2015 .
^ Vishkin, Uzi (2009). "Pensar en paralelo: algunos algoritmos y técnicas básicas de datos paralelos, 104 páginas" (PDF) . Apuntes de clases de cursos sobre algoritmos paralelos impartidos desde 1992 en la Universidad de Maryland, College Park, la Universidad de Tel Aviv y el Technion.
^ Megson GM; Chen Xian (4 de enero de 1997). Paralelización automática para una clase de cálculos regulares. World Scientific. ISBN 978-981-4498-41-8.
^ Kurgalin, Sergei; Borzunov, Sergei (2020). El libro de ejercicios de matemáticas discretas: un manual complementario que utiliza Python . Textos en informática (2.ª ed.). Cham, Suiza: Springer Naturel. ISBN 978-3-030-42220-2.

Enlaces externos

Diseño y construcción de programas paralelos, Laboratorio Nacional Argonne de EE. UU.

[1] Blelloch, Guy E.; Maggs, Bruce M. "Algoritmos paralelos" (PDF) . EE. UU.: Facultad de Ciencias de la Computación, Universidad Carnegie Mellon . Consultado el 27 de julio de 2015 .

[2] Vishkin, Uzi (2009). "Pensar en paralelo: algunos algoritmos y técnicas básicas de datos paralelos, 104 páginas" (PDF) . Apuntes de clases de cursos sobre algoritmos paralelos impartidos desde 1992 en la Universidad de Maryland, College Park, la Universidad de Tel Aviv y el Technion.

[MXian1997-3] Megson GM; Chen Xian (4 de enero de 1997). Paralelización automática para una clase de cálculos regulares. World Scientific. ISBN 978-981-4498-41-8.

[4] Kurgalin, Sergei; Borzunov, Sergei (2020). El libro de ejercicios de matemáticas discretas: un manual complementario que utiliza Python . Textos en informática (2.ª ed.). Cham, Suiza: Springer Naturel. ISBN 978-3-030-42220-2.