The license mess with serial port Qt-based libs

I am currently working on a Qt-based app that needs to communicate through the serial port. Apart from all the benefits that a normal lib with a serial port implementation will bring in this case, having a Qt-based serial port lib would make even more sense, as it should be as multiplatform as possible and use the signal/slot mechanism. Also it should have a DFSG-compatible license, so I can package it for Debian, of course :-)

So I have found two libs which seemed to have the above mentioned features: QExtSerialPort and QSerialPort.

QExtSerialPort seems to be the most recommended lib in the web. It features polled and signal-based functionality; it uses Qt's standard types inheriting QIODevice. But it does not states the license in any file within the source code. The original project page at SourceForge says it's in public domain. And the newer project page at Google code says it's under the new BSD license. I have asked in the mailing list for a clarification. So far nothing has changed (although in further threads the authors showed some willing to change this). And then I got to the point of finding a bug, but I don't want to spend time to track it down and make a patch without a clear license.

QSerialPort it's another lib with more or less the same features as QExtSerialPort. It's main LICENSE file says it's under the LGPL2, but licensecheck will say that the present files are LGPL3. Also, on reviewing the code, I found some minor stuff that could be improved. Well, I could contact the author and see if [s]he would receive the patches... but his site seems down. And I could not find a real-person's name in the code so far :-/

So I made a last attempt to try to get QExtSerialPort in a suitable license. If it doesn't suceed, I think I'll have to start writing one myself. The downside: I only use Linux, so there will be no multiplatform features unless someone else contributes it. Of course, if you have another option or any idea to share, I'll be happy to know it :-)

By the way, this should be my first post on Planet Debian in english, so hello planet!

¿Que pasa si instalo todos los discos de Debian?

Hay algunos que quizás abran las ojos "como dos de oro" por ésta pregunta, pero no es la primera vez que la leo ni que me la hacen, así que vá la respuesta:

Si instalás todos los DVDs/CDs de Debian, vas a tener mucho espacio en disco rígido ocupado. Muy posiblemente, de gusto.

Tener todos los discos a mano sirve si no tenés una buena conexión a internet. Con eso sabés que la gran mayoría de las cosas las tenés disponibles en cualquier momento. Pero no instales todo, solo lo que vos necesites, aunque solo sea del primer medio. Dejá que apt se haga cargo del resto :-)

Si tenés un contraejemplo... sabés lo que estás haciendo y no necesitás que te lo explique =)

Seguimos moviendo partículas, ésta vez con OpenCL

Y ahora le toca el turno al segundo trabajo práctico de HPC@UNS. Ésta vez vamos a seguir moviendo partículas, pero con mayor grado de paralelización, ya que vamos a usar OpenCL sobre una placa nVidia GeForce 8800 GTS 512 (rev a2) y Debian.

Cada punto del gráfico es el promedio de 5 corridas del mismo algoritmo con los mismos parámetros.

Por si solo no nos dice mas que el algoritmo tiene una dependencia O(n²) con el número de partículas. Ésto es natural ya que se trata del mismo código serial que en el práctico anterior, ésta vez convertido a OpenCL.

Nota: el código original está bajo la licencia BSD modificada (¡Gracias Vasily Volkov!). El código modificado mantiene la licencia.

Como en el caso del práctico anterior, se pueden tomar otras estrategias para reducir el orden de complejidad del código... pero no es lo que nos intereza ahora. La idea es comparar estos resultados con los ya obtenidos. Pero antes...

Nota importante: el código de OpenCL utiliza floats en vez de doubles para los cálculos. Ésto es debido a que la placa gráfica no soporta éste último tipo. Ésto llevó a la necesidad de aumentar la masa de la partícula, ya que el valor original producía errores numéricos que producían que las partículas se aceleraran.

Lo primero que podemos observar es que el tiempo de cálculo requerido para un número de partículas menor a ~[64 128] (según la implementación y el host) es menor para el caso serial que para el caso con OpenCL. Ésto era de esperarse, ya que se consume un tiempo importante en pasar datos hacia y desde la placa de video al host. Es decir, vale la pena implementar éstas soluciones si el número de datos a procesar es grande.

Es interesante notar como OpenMP sobre Luna (AMD Athlon (tm) 64 X2 Dual core processor 5000+) presenta mejor tiempo de cálculo que OpenCL para menos de 1024 partículas. A su vez, la implementación de OpenMP en cardumen (UltraSparc T2 (Niagara2)) es mas lenta. A medida que el volumen de datos aumenta, OpenCL comienza a ser mas eficiente.

Las comparaciones para PThreads son bastante similares a las anteriores. Tarea para el lector :-)

Notas y conclusiones

• OpenCL tiene muy buen desempeño para volumenes de datos grandes, aunque vale la salvedad de que se utilizaron floats en vez de doubles. Quizás si algún dia pongo mis manos en una placa con soporte para doubles pruebe a ver que pasa.
• OpenCL es un estándar, pero sólo provee los headers (API). Las implementaciones dependen de cada fabricantes, y no son software libre, al menos por ahora. Ésto atenta contra la portabilidad del código.
• QtOpenCL está genial :-)

Moviendo partículas y binarizando imágenes

Como parte de la entrega del trabajo práctico Nº 1 de la materia HPC@UNS era requerido hacer una página web con los resultados. Me pareció mas práctico usar mi blog... y acá estamos.

Partículas en movimiento

La primera parte del TP era ir a un sitio de Berkeley y bajar el código para simular la interacción entre partículas usando un algoritmo totalmente serial, otro utilizando PThreads y otro OpenMP. Lo primero que hice fué hacer unas corridas y ver los resultados que obtenía.

Nota: cada punto del gráfico es el promedio de 5 corridas del mismo algoritmo con los mismos parámetros. -Esto es válido para todos los gráficos de éste blog post, pero en los datos usados para generar los primeros solo se encuentran los valores ya promediadios.

Respuesta en tiempo al número de partículas de cada implementación  en un servidor Sparc T2 (Niágara2) de 8 cores con 8 hilos livianos cad uno.

Respuesta en tiempo al número de partículas de cada implementación  en una máquina AMD Athlon 64 X2 Dual Core processor 5000+.

Notemos que el número de threads de OpenMP no está definido, sino que se toma el de la instalación por defecto (Debian Wheezy en ambas máquinas).

Enseguida podemos notar varias cosas:

• Los algoritmos son O(n²). Nada raro si uno mira el código fuente, los ciclos for anidados saltan a la vista.
• Paralelizar el algoritmo vale la pena a partir de una cierta cantidad de datos. Se podría pensar en ~256 como un buen número de threshold, aunque seguramente es dependiente del hardware y del problema/implementación del algoritmo.
• Crear hilos tiene un costo mínimo asociado. En el caso del Sparc, el costo es mayor, aunque es notable como mejora el rendimiento con OpenMP.

Intentemos mejorar éste desempeño.

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, 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 incluyo el mail (en formato mbox) y la licencia propiamente dicha. ¡Gracias Vasily!

Veamos entonces los resultados, empezando por el caso serial.

Comparación del algoritmo original (1.0.1) con el algoritmo modificado 1.1.6 para el caso serial.

En éste caso vemos que tanto para Cardumen (Sparc) como para Luna (AMD Athlon) los cambios generaron una reducción del tiempo de ejecución. A su vez, podemos comparar el desempeño de ambos procesadores.

Comparación del algoritmo original (1.0.1) con el algoritmo modificado 1.1.6 para el caso con OpenMP.

En el caso de OpenMP resalta claramente como influye utilizar una excesiva cantidad de hilos en Cardumen para muy pocos datos. Notar que lso tiempos tienden a ser levemente menores para mas de ~4000 partículas.

Comparación del algoritmo original (1.0.1) con el algoritmo modificado 1.1.6 para el caso con PThreads.

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?

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 rxr. 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. Lamentablemente tampoco lo llegué a probar :-(

Haciendo trabajar a Cardumen

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?

Si, pueden obtenerlos acá.

Binarizando imágenes

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. 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 y lo usé para compilar. Se los recomiendo. El código fuente lo pueden encontrar acá.

La estrategia

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

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?

También están disponibles acá.

Algunas conclusiones

• 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.

Desarrollador de Debian

Ésta madrugada recibí el mail que confirma la creación de mi cuenta en los servidores de Debian. En otras palabras ¡soy DD! Tengo una alegría enorme :)

Por supuesto, no llegué hasta acá sin el invalorable esfuerzo de otras personas. Mi seguramente incompleta lista de agradecimientos va a (en orden cronológico) Marga Manterola y la muchachada entera del LugFI, Ana Guerrero,  el equipo Qt-KDE, Hauke Rahm que fué mi AM, Telma, mi novia, que me conoció y aceptó como debianita con todo lo que eso implica y a un montón de gente mas que me acompaña desde hace años.

A todos ustedes muchas gracias. Espero poder seguir siendo útil en la tarea de lograr el mejor Sistema Operativo Universal.

A veces a uno le falta teoría...

Antes que nada, no tengo formación teórica-pura de Programación Orientada a Objetos (POO). Lo que sé lo aprendí de libros varios que apuntan a enseñar programación orientada a objetos para un cierto lenguaje. Y tampoco tengo un conocimiento de compiladores+assembler lo suficiente bueno como para no estar preguntandome ésto. El lado bueno: al menos se me ocurre pensarlo :-)

Veamos éste caso:

class PublicFoo {
public:
  int mFoo;
}

Si, justo lo que no debiese hacerse en POO. Pero suponiendo que ya instancié un objeto con ésta clase y éste tuviese un valor, podría accederlo como:

PublicFoo data = new PublicFoo();
// De alguna manera se carga un dato...
int valor = data.mFoo;

Desde el punto de vista de acceso, debería ser inmediato. Si ahora usamos:

class PrivateFoo {
public:
  int foo() { return mFoo; };
  void setFoo(int foo) { mFoo = foo; };
private:
  int mFoo
}

Para obtener el valor de foo haríamos:

PrivateFoo data = new PrivateFoo();
// De alguna manera se carga un dato...
int valor = data.foo();

Lo que puede llegar a implicar que el compilador genere código para entrar en el método foo(), haciendo mas lento el acceso al valor.

Ahora, en éste otro caso:

class PrivateInlineFoo {
public:
  inline int foo() { return mFoo; };
private:
  int mFoo
}

Un acceso quizás sea tan rápido como en el primero, ya que se me ocurre que el compilador tenga el hint del inline para mejorar el acceso.

Seguramente me estoy perdiendo *mucho* a causa de mi ignorancia. Pero les cuento a que vino todo ésto: se me ocurrió pensar que pasaría si existiese una propiedad de visivilidad que permita que cualquiera acceda al valor de la propiedad de la clase para lectura, pero sólo la clase pueda modificar dicho valor. ¿sería mas "sencillo" programar?

En fin, nada mas mostrándole al mundo mis dudas e ignorancia :-)

Una mandarina en Debian

Hace unos 16 dias (tarde me vengo a avivar.. ¿será porque lo compilé de fuentes?) Clementine, el reproductor de música multiplataforma insipirado en Amarok 1.4, está disponible en Debian.

El trabajo necesario para empaquetarlo fué mucho, y por eso agradezco a Thomas Pierson por eso :-)

Sugiero que no dejen de probarlo. Sabe mejor con una mandarina en mano ;-)

La imagen fué tomada de la Wikipedia.