En las ciencias de la computación, un algoritmo paralelo, en oposición a los algoritmos clásicos o algoritmos secuenciales, es un algoritmo que puede ser ejecutado por partes en el mismo instante de tiempo por varias unidades de procesamiento, para finalmente unir todas las partes y obtener el resultado correcto.
Algunos algoritmos son fácilmente divisibles en partes; como por ejemplo, un algoritmo que calcule todos los números primos entre 1 y 100, donde se podría dividir los números originales en subconjuntos y calcular los primos para cada uno de los subconjuntos de los números originales; al final, uniríamos todos los resultados y tendríamos la solución final del algoritmo. Otro ejemplo, puede ser el cálculo de Pi en paralelo.
Por el contrario, a veces los problemas no son tan fácilmente paralelizables, de ahí que estos problemas se conozcan como problemas inherentemente secuenciales. Como ejemplo de estos métodos tendríamos los métodos numéricos iterativos como el método de Newton o el problema de los tres cuerpos. Por otro lado, algunos problemas son difícilmente paralelizables, aunque tengan una estructura recursiva. Como ejemplo de esto último tendríamos la búsqueda primero en profundidad en un grafo.
Los algoritmos paralelos son importantes porque es más rápido tratar grandes tareas de computación mediante la paralelización que mediante técnicas secuenciales. Esta es la forma en que se trabaja en el desarrollo de los procesadores modernos, ya que es más difícil incrementar la capacidad de procesamiento con un único procesador que aumentar su capacidad de cómputo mediante la inclusión de unidades en paralelo, logrando así la ejecución de varios flujos de instrucciones dentro del procesador. Pero hay que ser cauto con la excesiva paralelización de los algoritmos ya que cada algoritmo paralelo tiene una parte secuencial y debido a esto, los algoritmos paralelos puedes llegar a un punto de saturación (ver Ley de Amdahl). Por todo esto, a partir de cierto nivel de paralelismo, añadir más unidades de procesamiento puede sólo incrementar el coste y la disipación de calor.
El coste o complejidad de los algoritmos secuenciales se estima en términos del espacio (memoria) y tiempo (ciclos de procesador) que requiera. Los algoritmos paralelos también necesitan optimizar la comunicación entre diferentes unidades de procesamiento. Esto se consigue mediante la aplicación de dos paradigmas de programación y diseño de procesadores distintos: memoria compartida o paso de mensajes.
La técnica memoria compartida necesita del uso de cerrojos en los datos para impedir que se modifique simultáneamente por dos procesadores, por lo que se produce un coste extra en ciclos de CPU desperdiciados y ciclos de bus. También obliga a serializar alguna parte del algoritmo.
La técnica paso de mensajes usa canales y mensajes pero esta comunicación añade un coste al bus, memoria adicional para las colas y los mensajes y latencia en el mensaje. Los diseñadores de procesadores paralelos usan buses especiales para que el coste de la comunicación sea pequeño pero siendo el algoritmo paralelo el que decide el volumen del tráfico.
Finalmente, una subclase de los algoritmos paralelos, los algoritmos distribuidos son algoritmos diseñados para trabajar en entornos tipo clusters y de computación distribuida, donde se usan otras técnicas, fuera del alcance de los algoritmos paralelos clásicos.
Evaluación de técnicas de detección de errores en programas concurrentes, Frati, Fernando Emmanuel. 1 de abril de 2014, 51 páginas.
Datos:Q1087987
Agosto 10, 2021
algoritmo, paralelo, ciencias, computación, algoritmo, paralelo, oposición, algoritmos, clásicos, algoritmos, secuenciales, algoritmo, puede, ejecutado, partes, mismo, instante, tiempo, varias, unidades, procesamiento, para, finalmente, unir, todas, partes, ob. En las ciencias de la computacion un algoritmo paralelo en oposicion a los algoritmos clasicos o algoritmos secuenciales es un algoritmo que puede ser ejecutado por partes en el mismo instante de tiempo por varias unidades de procesamiento para finalmente unir todas las partes y obtener el resultado correcto Algunos algoritmos son facilmente divisibles en partes como por ejemplo un algoritmo que calcule todos los numeros primos entre 1 y 100 donde se podria dividir los numeros originales en subconjuntos y calcular los primos para cada uno de los subconjuntos de los numeros originales al final uniriamos todos los resultados y tendriamos la solucion final del algoritmo Otro ejemplo puede ser el calculo de Pi en paralelo Por el contrario a veces los problemas no son tan facilmente paralelizables de ahi que estos problemas se conozcan como problemas inherentemente secuenciales Como ejemplo de estos metodos tendriamos los metodos numericos iterativos como el metodo de Newton o el problema de los tres cuerpos Por otro lado algunos problemas son dificilmente paralelizables aunque tengan una estructura recursiva Como ejemplo de esto ultimo tendriamos la busqueda primero en profundidad en un grafo Los algoritmos paralelos son importantes porque es mas rapido tratar grandes tareas de computacion mediante la paralelizacion que mediante tecnicas secuenciales Esta es la forma en que se trabaja en el desarrollo de los procesadores modernos ya que es mas dificil incrementar la capacidad de procesamiento con un unico procesador que aumentar su capacidad de computo mediante la inclusion de unidades en paralelo logrando asi la ejecucion de varios flujos de instrucciones dentro del procesador Pero hay que ser cauto con la excesiva paralelizacion de los algoritmos ya que cada algoritmo paralelo tiene una parte secuencial y debido a esto los algoritmos paralelos puedes llegar a un punto de saturacion ver Ley de Amdahl Por todo esto a partir de cierto nivel de paralelismo anadir mas unidades de procesamiento puede solo incrementar el coste y la disipacion de calor El coste o complejidad de los algoritmos secuenciales se estima en terminos del espacio memoria y tiempo ciclos de procesador que requiera Los algoritmos paralelos tambien necesitan optimizar la comunicacion entre diferentes unidades de procesamiento Esto se consigue mediante la aplicacion de dos paradigmas de programacion y diseno de procesadores distintos memoria compartida o paso de mensajes La tecnica memoria compartida necesita del uso de cerrojos en los datos para impedir que se modifique simultaneamente por dos procesadores por lo que se produce un coste extra en ciclos de CPU desperdiciados y ciclos de bus Tambien obliga a serializar alguna parte del algoritmo La tecnica paso de mensajes usa canales y mensajes pero esta comunicacion anade un coste al bus memoria adicional para las colas y los mensajes y latencia en el mensaje Los disenadores de procesadores paralelos usan buses especiales para que el coste de la comunicacion sea pequeno pero siendo el algoritmo paralelo el que decide el volumen del trafico Finalmente una subclase de los algoritmos paralelos los algoritmos distribuidos son algoritmos disenados para trabajar en entornos tipo clusters y de computacion distribuida donde se usan otras tecnicas fuera del alcance de los algoritmos paralelos clasicos Vease tambien EditarProgramacion paralela Programacion concurrenteEnlaces externos EditarEvaluacion de tecnicas de deteccion de errores en programas concurrentes Frati Fernando Emmanuel 1 de abril de 2014 51 paginas Datos Q1087987Obtenido de https es wikipedia org w index php title Algoritmo paralelo amp oldid 117854190, wikipedia, wiki, leyendo, leer, libro, biblioteca,
