Algoritmo paralelo

Algoritmo paralelo

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 paralelelos 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 colar 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.

Véase también

  • Programación paralela
  • Programación concurrente

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Algoritmo de Wang-Landau — Este artículo o sección sobre matemáticas necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 19 de diciembre de 2010. También puedes …   Wikipedia Español

  • Algoritmo determinista — En ciencias de la computación, un algoritmo determinista es un algoritmo que, en términos informales, es completamente predictivo si se conocen sus entradas. Dicho de otra forma, si se conocen las entradas del algoritmo siempre producirá la misma …   Wikipedia Español

  • P-completo — En teoría de la complejidad computacional, la clase de complejidad P completo es un conjunto de problemas de decisión de gran utilidad para identificar los problemas que pueden ser resueltos eficientemente en máquinas paralelas. Un problema de… …   Wikipedia Español

  • Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW …   Wikipedia Español

  • Conexionismo — El conexionismo es un conjunto de enfoques en los ámbitos de la inteligencia artificial, psicología cognitiva, ciencia cognitiva, neurociencia y filosofía de la mente, que presenta los fenómenos de la mente y del comportamiento como procesos que… …   Wikipedia Español

  • Turbo código — Los turbo códigos son una nueva clase de códigos de corrección de errores (FEC), que se introdujeron, junto con un algoritmo de decodificación. La importancia de los turbo códigos es que permiten una comunicación fiable y su eficiencia energética …   Wikipedia Español

  • Bases de datos distribuidas — Saltar a navegación, búsqueda Una base de datos distribuida (BDD) es un conjunto de múltiples bases de datos lógicamente relacionadas las cuales se encuentran distribuidas entre diferentes sitios interconectados por una red de comunicaciones, los …   Wikipedia Español

  • José Francisco Duato Marín — (Alberique, Valencia, 1958) es un profesor e investigador español galardonado con el Premio Nacional de Investigación Julio Rey Pastor en el año 2009, así como el Premio Rey Jaime I a las nuevas tecnologías en el 2006. Su línea de investigación… …   Wikipedia Español

  • DQDB — Saltar a navegación, búsqueda Contenido 1 DQDB (Dual Queue Dual Bus) 2 Orígenes de la DQDB 3 Arquitectura de una DQDB 4 …   Wikipedia Español

  • P (Complejidad computacional) — Saltar a navegación, búsqueda Contenido 1 Introducción 2 La clase P 3 Problemas notables en P 4 Propiedades …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”