Moviendo partículas y binarizando imágenes

[Intentemos mejorar éste desempeño.]{.Apple-style-span style="font-size: large;"} Mirando el código fuente vemos que la interacción entre partículas se calcula todas entre todas. Lo interesante es que el resultado de la interacción de una partícula p con una partícula q es la misma pero de signo contrario a la interacción de la partícula q con la partícula p. Entonces podemos hacer los cálculos una sola vez entre dos partículas cualquiera.

Por otro lado, la interacción entre partículas es basada en la distancia entre ellas. Si la distancia es cero, no hay interacción. Entonces una partícula no interactúa con si misma.

Desde el punto de vista del hardware y el paralelismo, podemos utilizar la máxima cantidad e hilos posibles para cada caso.  Definitivamente ésto va a traer acarreado mayor tiempo de ejecución en los casos de pocas partículas, pero debería ser mejor a medida que el número de partículas aumenta.

~~**Nota:** debido a que el código fuente original no estipula una licencia y por ende se debe interpretar como "todos los derechos reservados", no hago públicas las modificaciones del código.~~ **Actualización 18/11/2011:** le escribí a [Vasily Volkov](http://www.cs.berkeley.edu/~volkov/), responsable del sitio y código de Berkeley arriba linkeado, y tuvo la gentileza de reponderme diciéndome que la licencia en BSD modificada. En el [repositorio del código](http://dumbledore.com.ar/gitweb/?p=hpc/particulas.git;a=summary) incluyo el mail (en formato [mbox](http://en.wikipedia.org/wiki/Mbox)) y la licencia propiamente dicha. ¡Gracias Vasily!

Veamos entonces los resultados, empezando por el caso serial.

Aquí también se puede observar el costo que tiene utilizar muchos threads con pocos datos. En éste caso se hace notoria la mejora de rendimiento entre las dos versiones de PThreads en Cardumen. No puede faltar un gráfico con todos los resultados: -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  Todos los resultados juntos. -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

[¿Podemos mejorar aún mas el algoritmo?]{.Apple-style-span style="font-size: large;"} Si, y (teóricamente) mucho. El "truco" está en reducir la complejidad del algoritmo lo mas posible. Para eso hay que detectar el cuello de botella, que no es otro que el cálculo de las fuerzas entre cada partícula. Dijimos que la interacción entre las mismas es una relación de la distancia. Pero lo que no nombramos es que, luego de una cierta distancia *r*, ya no interactúan entre ellas. Debemos entonces encontrar una forma de que cada partícula solo calcule la fuerza que podrían llegar a ofrecerles posibles partículas aledañas. Una posible solución sería dividir el espacio bidimensional en una matriz donde cada casillero sea de tamaño *r*x*r*. Cada vez que se mueve una partícula se la ubica en el casillero correspondiente a su zona final. Luego basta considerar sólo las fuerzas que aplican las partículas en el mismo casillero y en los casilleros aledaños. Si bien suena sencillo, se hace necesario sincronizar el acceso a cada partícula entre los hilos y sus propiedades. Yo no llegué a implementarlo, pero [MorningCoffee si lo ha hecho](https://github.com/Morningcoffee/ID1217--Parallelize-Particle-Simulation). Lamentablemente tampoco lo llegué a probar :-( [Haciendo trabajar a Cardumen]{.Apple-style-span style="font-size: large;"} Ahora la idea no es analizar el algoritmo sino como responde el servidor con ése algoritmo ante distintas cargas y números de threads.  En el caso de OpenMP podemos ver como se va incrementando el costo fijo de generar una cantidad determinada de threads.  Podemos ver que, para muy pocas partículas (hasta \~20), tener un **solo hilo** de OpenMP (que debería ser el mismo caso que el algoritmo totalmente serial) tiene un overhead. También se puede observar que dada una cierta cantidad de partículas realmente vale la pena usar paralelización.  El mismo análisis se puede hacer para PThreads.  Y, por supuesto, podemos ver todos los resultados juntos. Las referencias corresponden a la simulación serial, luego las de OpenMP terminando con las de PThreads. Veamos ahora el speedup de cada caso:  Puede verse que la performance de PThreads es similar.  Resulta posible observar que en ambos casos el speedup se aproxima al teórico para cada número de threads. ¿Y que pasaría si tuviésemos una cantidad **fija** de threads para utilizar?  [¿Tenés los resultados a mano?]{.Apple-style-span style="font-size: large;"} Si, pueden obtenerlos [acá](http://dumbledore.com.ar/gitweb/?p=hpc/resultados_particulas.git;a=summary). [Binarizando imágenes]{.Apple-style-span style="font-size: x-large;"} La idea de la segunda parte del TP es binarizar dos juegos de 100 imágenes de 360 y 1080 pixeles cada uno. Primero resolver el problema de forma serial y luego paralelizarlo. Visto gráficamente, la idea es pasar de una imagen como: ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  \(c\) copyright 2008, Blender Foundation / www.bigbuckbunny.org. Bajo licencia CC-BY 3.0. ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- A una imagen con solo dos tonos: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------  \(c\) copyright 2008, Blender Foundation / www.bigbuckbunny.org. Bajo licencia CC-BY 3.0. Modificado por mi código :-) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Para lograr ésto usé [Qt](http://en.wikipedia.org/wiki/Qt_(framework)). no lo hice la manera mas eficiente, ya que utilicé QImage::pixel() y QImage::setPixel(). Podría haber utilizado los métodos de QImage para acceder a los pixeles como vecotres de datos. Pero bueno, para el propósito de éste TP, alcanza. Aproveché el envión que llevo de aprender [CMake](http://en.wikipedia.org/wiki/CMake) y lo usé para compilar. Se los recomiendo. El código fuente lo pueden encontrar [acá](http://dumbledore.com.ar/gitweb/?p=hpc/binarizacion.git;a=summary). [La estrategia]{.Apple-style-span style="font-size: large;"} Tan sencilla como hacer que cada hilo se ocupe de procesar una imagen. No hay interdependencia entre ellas, por lo que no es necesario sincronizar los threads. Dicho de otra manera, no hay necesidad de procesar las imágenes en ningún orden en particular. [Los gráficos obtenidos]{.Apple-style-span style="font-size: large;"} Podemos ver el tiempo de ejecución vs. el número de threads:  Es interesante ver la meseta que se forma entre los \~8 y \~20 threads.  En éste caso, la meseta no aparece. Y también podemos medir el speedup. En amarillo, el speedup teórico ideal.   Realmente me sorpendió lo bajo del speedup :-/ Como nota al margen, Cardumen empezó a dar "Bus error" al momento de correr los algoritmos (entre ejecución y ejecución). Es posible que haya un problema de hardware en el mismo. [¿Y los resultados?]{.Apple-style-span style="font-size: large;"} También están disponibles [acá](http://dumbledore.com.ar/gitweb/?p=hpc/resultados_binarizacion.git;a=summary). [Algunas conclusiones]{.Apple-style-span style="font-size: x-large;"} - OpenMP hace la vida de un programador mucho mas sencilla que PThreads por poca o nada de diferencia en tiempo de ejecución. - Esperaba que el Sparc tuviese un mejor rendimiento. Mi sospecha es que no se trata de un servidor diseñado para procesar datos de punto flotante (posee una sola FPU por core, es decir, una FPU por cada 8 hilos). - Estaría bueno poder decirle a OpenMP/Sistema Operativo que ponga un hilo por core. hasta donde sé, pueden crearse 8 hilos pero no hay ninguna garantía de que cada uno corra en un core. Ésto serviría para reducir el tiempo en cálculos con mucho uso de FPU.