¡Muy buenas!

Con esta entrada quiero presentar los beneficios principales de la programación en paralelo. Como no es oro todo lo que reluce, también veremos el coste que implica esta práctica y sus desventajas.

Primera pregunta: ¿Por qué?

Respuesta: Si tu programa secuencial tarda mucho, como por ejemplo 5 segundos.. Sí, 5 segundos para algunos usuarios puede ser una eternidad. Puede ser buena idea para que vaya más rápido sí se fragmenta su procesamiento entre varios hilos de ejecución, ¡al menos para que el usuario que use tu programa no se canse de esperar!

Actualmente, no hay ordenador que no tenga al menos dos CPU y unos cuantos Sockets para ejecutar programas concurrentemente. ¡Por lo que sólo falta que nos pongamos a ello!

Aplicación

Nos centraremos en el código que podamos controlar, por ejemplo si lo costoso de nuestro código es una llamada Web Service externa, pues es un tiempo que normalmente tendrás que asumir si no hay alternativas.

Para mi, la mejor forma de explicar un concepto es con un ejemplo:

Nuestro código de ejemplo es un programa que te busca una solución para un sudoku. Podemos contar que este programa es un NP-Completo (FYI: http://es.wikipedia.org/wiki/NP-completo), por lo que es muy costoso. Ya que no se ha encontrado mejor solución que buscar las (9!)^9 posibles soluciones (en el caso que sea un sudoku estándar de 9×9) y coger la que cumpla las condiciones.

Nuestro sudoku de entrada es el siguiente:

El recorrido del programa es recorrer las columnas para cada fila. Es decir, el primer elemento que coge el programa es el que está resaltado en la imagen y luego el de su derecha. Cuando acabara la fila continua por la fila de abajo desde su elemento más a la izquierda y así sucesivamente hasta el final.

La idea del programa es que escoge un camino hasta que encuentra una solución o encuentra un error en alguna condición. Si ocurre el error vuelve atrás hasta la última decisión hecha y escoge otra. Este procedimiento es conocido como ‘BackTracking’.

Para empezar nuestro programa mirará para la posición (1,1), la que está resaltada en la imagen. Los únicos números que son posibles son el 1, el 3, el 7, el 8 y el 9. El programa escoge uno de estos números y va a la siguiente posición haciendo el mismo procedimiento. Por ejemplo se ha escogido el número 1, y, después de avanzar haciendo el sudoku, se ha comprobado que no hay solución con un 1 en la primera posición. Por lo que se deshace el camino para cambiar el 1 por la siguiente decisión, que sería el 3.. Y, ¡vuelta a empezar! ¡Dependiendo de lo vacío que esté el tablero del sudoku puede tardar horas en encontrar una solución!

Propongo dividir el problema, como la expresión que me gusta mucho: ‘Divide & Conquer’. Si se ejecuta en secuencial (con un solo proceso) como hemos visto primero calculamos todas las posibilidades con 1, luego con el 3, 7, 8 y, finalmente, con el 9. Pero, si lo ejecutamos en paralelo (con N procesos) nos podemos ahorrar mucho tiempo! Que tal si un proceso calcula las opciones con 1, otro con el 3 y sucesivamente. Solo con este mínimo paralelismo podemos lograr que nuestro programa vaya aproximadamente 5 veces más rápido ya que los cálculos de 1,3,7,8 y 9 se harían a la vez.

Como se ve en el ejemplo, hay mucho que ganar con un poco de esfuerzo. Aunque también hay que destacar los problemas a la hora de paralelizar:

  • Muchas veces no es trivial saber si se puede paralelizar una parte de tu código que es costoso. Y, se puede llegar a una mala paralelización que tarde más que tu programa en secuencial.
  • Puede existir dependencias entre tareas en tu código paralelo que has de cumplir.
  • Se ha de intentar que la carga de trabajo entre procesos esté lo más balanceada posible para obtener un mejor paralelismo.
  • No todos los lenguajes de programación te permite programar en paralelo.
  • Hay que contar que, a veces, es necesario que los procesos se pasen información entre ellos y es un coste de tiempo adicional (overhead).
  • Se ha de sumar el tiempo de creación y finalización de procesos.

Si estáis interesados en el tema, recomiendo la librería de OpenMP para C/C++ y Fortran. Te permite el desarrollo de código paralelo con el paradigma fork/join y threads:

http://openmp.org/wp/

También os dejo una presentación que hice sobre el tema:

https://prezi.com/yrnf6lfx_vwh/paralelismo/?utm_campaign=share&utm_medium=copy

¡Saludos!


Leave a Reply

Your email address will not be published. Required fields are marked *