¿Por qué computación paralela?
En palabras sencillas la computación paralela es el uso simultáneo de más de un procesador para resolver un problema.
Pero, por qué usar necesariamente más de un procesador para resoverlo?, aqui viene la idea del tema. Daremos un ejemplo particular, cuando un problema es resuelto con un algoritmo secuencial y en un tiempo razonable está todo correcto!, para mejorar ese tiempo buscamos un algoritmo más eficiente, usamos dinamic programming, greedy, etc , y listo!, pero que pasa cuando dicho problema trabaja con miles o millones de datos?, pues pensamos rápidamente en mejorar la velocidad de nuestro procesador (seguimos en el enfoque secuencial),
¿Qué es computación paralela?
Tianhe-2 , la supercomputadora más rápida del mundo, desarrollada por la University of Defense Technology de China. Según ww.top500.org, 2013.
Veamos un ejemplo
El hecho de añadir más procesadores no es siempre sinónimo de mejora en el rendimiento de nuestro programa, ya que muchos programas secuenciales fueron escritos para correr en un solo procesador, este es el caso de la versión recursiva del algoritmo para calcular el factorial de un número o el de fibonacci, los cuales no se pueden paralelizar (claro, f(n) depende de un valor o más anteriores, f(n-1), f(n-2), etc), el rendimiento que se logra al correr estos algoritmos en un solo procesador o en múltiples procesadores es el mismo. Veamos un ejemplo paralelizable.
Queremos calcular n valores y sumalor, entonces
suma = 0;
for (i = 0; i < n; i++) {
x = calcularSiguienteValor(. . .);
suma += x;
}
Principios Básicos
Aplicación I
Programación dinámica aplicado al problema de la mochila 0/1 con enfoque paralelo
La primera aplicación trata de paralelizar el problema de la mochila, conocido como el Knapsack problem 0/1, que trata de maximizar una función enlazada a ciertos parámetros. Básicamente se pide llenar un contenedor (como una mochila) de objetos que tienen un peso w y un valor de v , de tal manera que se maximice el valor dentro del contenedor sin sobrepasar su peso maximo W. Gráficamente se puede observar asi :
Problema de la mochila 0/1
Aplicación II
Resolviendo el problema de Poisson usando el método de S.O.R en paralelo
En esta ocasión se trata de expresar de manera discreta la ecuacion diferencial de Poisson, luego solucionar el sistema de ecuaciones lineales en cada punto de la malla que resulta de expresar dicha ecuación usando métodos finitos. En palabras simples, se necesita hallar un punto en una malla de nxn como se muestra a continuación :
