Tratando de optimizar el código

Ya casi no tengo mucho tiempo para escribir cosas interesantes :S!

En los siguientes post me gustaria hablar de javascript y Google Maps.

Mi tesis(https://github.com/fedep3/Metaheuriscticas-Data-Clustering) está hecha en C++ y es sobre data clustering  de datos numéricos usando metaheurísticas. Esta enfocada en las imagenes principalmente (las imágenes no son mas que conjuntos de vectores de uno o mas colores).

Actualmente ando investigando y mejorando el código para hacer una poblicacion sobre el algoritmo genético que cree yo con mi companero.

En el código he hecho dos cambios:

  1. Cambiar el generador de numeros aleatorios.
  2. Intentar optimizar la función de la distancia euclideana.

El motivo de l primer cambio era que el generador de numeros aleatorios de C++, es un http://en.wikipedia.org/wiki/Linear_congruential_generator , los cuales son muy eficiente, pero no son tan buenos. Habiendo usado python y ya de hace un tiempo que habia leído del tema decidí colocar el http://en.wikipedia.org/wiki/Mersenne_twister que es de los mejores, por no decir el mejor actualmente. Ahora el reto era buscar que implementecion usar o si hacerla uno mismo. Buscando y probando consegui uno creado por un invetigador de Pixar que hace uso de las instrucciones SSE2 y que es increiblemente eficiente(http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/cpp_sse2.zip).

Al principio no me compilo asi que busqué lo que estaba pasando. Después de como 1 hora de leer y probar di con la solucion. El código hace uso de unos defines o funciones que por lo visto no estan incluidos en el emmintrin.h. Basto con cambiar el código y listo compilo.  Lo arregle para usarlo y la diferencia de tiempo/resultados con lo que tenia antes ni se notaba.

Averiguando todo este, me surgió un interés por esas instrucciones SSE2. Quería ver si podía programar en ellas la distancia euclideana. Encontre una especia de API de ellas (http://software.intel.com/sites/products/documentation/studio/composer/en-us/2011/compiler_c/index.htm#intref_cls/common/intref_sse2_int_load.htm) y leyendo otras cosas(http://fastcpp.blogspot.comhttps://developer.apple.com/hardwaredrivers/ve/sse.html) entendí su funcionamiento. Las intrucciones son capaces(segun leí y entendí) de procesar 4 flotantes a la vez o 2 doubles.

Mi tesis usa floats, asi que programé lo siguiente:

float Metaheuristic::euclideanDistance(float* v1, float* v2)
{
    __m128 sum = _mm_setzero_ps(), square;
    for(register int k = 0; k < M; k+=4){
        square = _mm_sub_ps( _mm_load_ps(v1 + k), _mm_load_ps(v2 +k));
        sum = _mm_add_ps(_mm_mul_ps(square,square), sum);
    }
    sum = _mm_sqrt_ps(sum);
    _mm_store_ps(eDistance, sum);
    return eDistance[0];
}

Surgieron un montón de problemas para lograr que éesto funcionara. El principal fue que los arreglos que usan estas instrucciones deben tener tamaño divisible entre 4, ya que se cargan los 4 flotantes a los registros. Cambie gran parte del codigo para que a la hora de crear los objetos se cumpliera esta condición y probé de no tener leaks o errors en la memoria usando valgrind. Cuando ya no tuve problemas y los resultados de las corridas tenían coherencia, observé los tiempo. Una imagen que me corria antes en 1 – 2 segundos pasó a 10 segundos !

Mi intento por optimizar el codigo fue fallido, pero aprendi algo. Para mi la razón de que no funcionara muy bien es que los arreglo en realidad eran arreglos de tamano 1 o 3 transformados a 4. Más tiempo se perdía en la carga y cálculo que el que ganaba de tener la capacidad de procesar 4 cosas a la vez. Eso que hasta intente tener las cosas aleanadas a 16 bytes y nada ! Por supuesto que es posible que halla hecho algo mal, pero ahora no tengo mucho tiempo para seguir jugando con el código, ando full de otras cosas.

Espero que ésto sea de ayuda

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s