Algoritmos Paralelos

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), entonces pasamos por ejemplo de un procesador Intel® Core™ i3 CPU 2.40 GHz  a un Intel® Core™ i7-4960X Processor Extreme Edition 4.00 Ghz, vemos que ahora nuestro programa con el mismo algoritmo calcula más rapido la data y soporta mucho más datos, pero hay un problema, necesitamos aún más cantidad de datos y el tiempo que tarda nuestro programa no es suficiente y además vemos que físicamente al achicar los transitores dentro del procesador estos disipan mucho calor, la latencia con la memoria no baja y al ser muy chicos empieza el efecto cuántico y los  cálculo se volverian probabilísticos; llegamos a un momento que  ya no podemos mejorar ese tiempo, aquí entra la idea de "paralelizar el problema" y modificando en cierta medida nuestro algoritmo tenemos que ejecutarlo no sólo con 1 solo procesador sino con 2, 4 ó los que hubiere.

 

Ya que se tiene la idea de por qué usar paralelismo, veamos algunas

aplicaciones que motivaron el desarrolo de este enfoque.

 

 

Modelar el clima: Se necesita conocer el cambio climático, modelos

que incluyan la interacción entre la atmósfera, los océanos, la tierra

firme, los polos, etc; para entender como estas intervenciones podrían

afectar el clima global.

 

Por ejemplo, se requiere variables como longitud, latitud, elevación,

tiempo para hallar la temperatura, presion, humedad, etc para un 

tiempo de un dia, una semana, un año o más.

Esto se puede modelar usando dinámica de fluidos computacional

para hallar las ecuaciones de  Navier–Stokes.

 

Plegamiento de proteínas: Se cree que las proteínas mal plegadas

pueden estar implicadas en enfermedades tales como Huntington,

Parkinson, y Alzheimer, pero el analizar esas complejas moléculas 

está limitado por nuestro actual poder computacional.

 

Descubrimiento de fármacos: Hay muchos fármacos que son

ineficaces para una cierta población, es posible que podamos idear

tratamientos alternativos para el análisis de los genomas

de los individuos para los que el tratamiento conocido es ineficaz.

Esto, sin embargo, implicará extenso análisis computacional de

genomas.

                                                                                                                               

Análisis de datos: Entender como la secuencia de nucleótidos del

ADN afecta nuestro desarrollo y cómo puede causar distintas enfermedades requiere un análisis extenso, tanto como, 

los datos generados por el colisionador de partículas LCH en el CERN, imágenes médicas, investigaciones astronómicas, 

motores de búsqueda, etc.

 

Estos y otros problemas no pueden ser resueltos si seguimos con el enfoque secuencial, necesitamos repartir el 

trabajo entre los procesadores, por ende, necesitamos una programación paralela. El siguiente artículo veremos sus principios básicos y conceptos más formales.

 

Referencias

• An introduction to parallel programming, Peter Pacheco, University of San Francisco.

• Curso Algoritmos paralelos, Glen Rodriguez, Universidad Nacional de Ingeniería.