Hispanopedia WikiEn informática , un algoritmo paralelo , a diferencia de un algoritmo serial tradicional , es aquel que puede realizar múltiples operaciones en un tiempo determinado. Tradicionalmente, la informática ha descrito los algoritmos seriales mediante 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 denominada máquina de acceso aleatorio paralela (PRAM) como una máquina abstracta paralela (memoria compartida). [ 1 ] [ 2 ]
Muchos algoritmos paralelos se ejecutan simultáneamente —aunque, en general, los algoritmos concurrentes constituyen un concepto distinto—, por lo que a menudo se confunden, sin que se distinga 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 contraposición a los algoritmos concurrentes.
Paralelización
Los algoritmos varían significativamente en su grado de paralelización, desde aquellos que se paralelizan fácilmente hasta los que no. Además, un mismo problema puede admitir diferentes algoritmos, que pueden ser más o menos paralelizable.
Algunos problemas se pueden dividir fácilmente en partes de esta manera; se les llama problemas fácilmente paralelizados . Algunos ejemplos incluyen muchos algoritmos para resolver cubos de Rubik y encontrar valores que den como resultado un hash dado .
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 llamanproblemas inherentemente seriales . Ejemplos de ello son los métodos numéricositerativos, comoel método de Newton, las soluciones iterativas alproblema de los tres cuerposy la mayoría de los algoritmos disponibles para calcularpi(π).Algunos algoritmos secuenciales pueden convertirse en algoritmos paralelos medianteparalelización automática. [ 3 ]
En muchos casos, desarrollar un algoritmo paralelo eficaz para resolver una tarea requiere desarrollar nuevas ideas y métodos que no son necesarios en el diseño de un algoritmo secuencial para resolver el mismo problema. Ejemplos de estos casos incluyen problemas de gran importancia práctica como la búsqueda de un elemento objetivo en una estructura de datos y la evaluación de una expresión algebraica. [ 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 finales de 2004, el rendimiento de los procesadores de un solo núcleo aumentó rápidamente mediante el escalado de frecuencia , por lo que era más fácil construir una computadora con un solo núcleo rápido que con muchos núcleos más lentos con el mismo rendimiento ; por lo tanto, los sistemas multinúcleo tenían un uso más limitado. Sin embargo, desde 2004, el escalado de frecuencia alcanzó su límite, y por lo tanto los sistemas multinúcleo se han generalizado, lo que ha hecho que los algoritmos paralelos sean de uso más general.
Asuntos
Comunicación
El costo o la complejidad de los algoritmos seriales se estima en función del espacio (memoria) y el tiempo (ciclos de procesador) que consumen. Los algoritmos paralelos necesitan optimizar un recurso adicional: la comunicación entre los distintos procesadores. Existen dos formas en que los procesadores paralelos se comunican: mediante memoria compartida o paso de mensajes.
El procesamiento en memoria compartida requiere un bloqueo adicional para los datos, impone la sobrecarga de ciclos adicionales de procesador y bus, y también serializa una parte del algoritmo.
El procesamiento de paso de mensajes utiliza canales y buzones de mensajes, pero esta comunicación añade sobrecarga de transferencia en el bus, requiere memoria adicional para las colas y los buzones, y genera latencia en los mensajes. Los diseños de procesadores paralelos utilizan buses especiales , como la interconexión de barras cruzadas , para minimizar la sobrecarga de comunicación; sin embargo, es el algoritmo paralelo el que determina el volumen de tráfico.
Si la sobrecarga de comunicación de los procesadores adicionales supera el beneficio de agregar otro procesador, se produce una ralentización en paralelo .
Balanceo de carga
Otro problema con los algoritmos paralelos es asegurar que la carga de trabajo esté equilibrada , es decir, que la carga total (trabajo general) esté equilibrada, en lugar de que lo esté el tamaño de los datos de entrada. Por ejemplo, comprobar si un número es primol entre todos los números del uno al cien mil es fácil de repartir entre los procesadores; sin embargo, si los números se dividen simplemente de forma equitativa (del 1 al 1000, del 1001 al 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 (más fáciles de comprobar si son primol), y por lo tanto, algunos procesadores tendrán más trabajo que otros, que permanecerán inactivos hasta que los procesadores con carga de trabajo terminen.
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".
Los algoritmos distribuidos están diseñados para ejecutarse en una red de computadoras interconectadas que se comunican mediante memoria compartida o paso de mensajes. A diferencia de los algoritmos paralelos tradicionales, deben operar bajo restricciones adicionales, como conocimiento local limitado, retrasos en la comunicación, la falta de un estado global y la posibilidad de fallas en los nodos.
El enfoque de los algoritmos distribuidos se centra en los problemas de coordinación que surgen en los sistemas distribuidos, incluyendo la elección de líder , la exclusión mutua y el consenso (informática) . Estos problemas se estudian bajo diferentes modelos de sistema con diversas suposiciones, como si el sistema es síncrono o asíncrono y si existen fallos, como fallos por caída del sistema o fallos bizantinos . [ 5 ]
Los algoritmos distribuidos tienen muchas aplicaciones prácticas en bases de datos distribuidas, sistemas tolerantes a fallos y aplicaciones de red a gran escala.
Véase también
Referencias
- ↑ Blelloch, Guy E.; Maggs, Bruce M. "Algoritmos paralelos" (PDF) . EE. UU.: Escuela de Ciencias de la Computación, Universidad Carnegie Mellon . Recuperado el 27 de julio de 2015 .
- ↑ Vishkin, Uzi (2009). "Pensando en paralelo: algunos algoritmos y técnicas básicas de procesamiento paralelo de datos, 104 páginas" (PDF) . Apuntes de clase 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 cuaderno de ejercicios de matemáticas discretas: un manual complementario que utiliza Python . Textos en Ciencias de la Computación (2.ª ed.). Cham, Suiza: Springer Naturel. ISBN 978-3-030-42220-2.
- ↑ Hagit Attiya y Jennifer Welch. Computación distribuida: fundamentos, simulaciones y temas avanzados . 2.ª ed., Wiley, 2004.
Enlaces externos
- Diseño y construcción de programas paralelos , Laboratorio Nacional Argonne de EE. UU.
- Computación paralela
- Algoritmos concurrentes
- Algoritmos distribuidos
