Optimizaciones en paralelo (II)

La programación paralela, esa gran desconocida... Muchos de nosotros ya tenemos ordenadores, o incluso teléfonos móviles y tablets con capacidad para ejecutar varias instrucciones a la vez. Hacer un programa que aproveche este potencial no es muy difícil en la mayoría de los casos.

Los procesadores de hoy en día nos permiten paralelizar programas mediante dos mecanismos:

• Multinúcleo o multihebra. Dos procesos se pueden ejecutar simultáneamente en el mismo procesador, cada uno en un núcleo.
• Instrucciones SIMD. Single Instruction, Multiple Data. Se trata de instrucciones que se aplican a varios datos a la vez.

La primera tecnología es más conocida: procesadores como los Intel Core Duo llevan dos núcleos, incluso algunos de ellos utilizan HyperThreading, que brinda dos hebras por cada núcleo físico, el sistema operativo ve dos procesadores donde hay sólo uno, y entrega las tareas de dos en dos, ganando un poco de velocidad extra.

Son muchas las herramientas que tenemos para crear programas multihebra: Java, .NET Framework, Qt y POSIX son bibliotecas que permiten crear hebras una a una, son más flexibles pero la programación es un poco más costosa. Además tenemos OpenMP, que permite multihebrar código mediante sencillas directivas #pragma en C/C++, automatiza creación y destrucción de hebras, así como distribución de bucles for y secciones en paralelo. La interfaz OpenMP es soportada por compiladores como GCC, Visual Studio y el compilador de Intel.

En cuanto a la técnica SIMD, escribí un post hace unos meses para demostrar que podemos aumentar la velocidad si empaquetamos varios datos en una estructura y los sumamos a la vez. Los procesadores de Intel, desde el Pentium 4, incluyen instrucciones que permiten hacer esto, mediante registros de memoria más grandes e instrucciones máquina SSE2.

Y todo lo que tenemos que hacer para utilizar esta tecnología es conocer qué variables podemos procesar en paralelo (teniendo en cuenta que estas operaciones se hacen de 128 en 128 bits) y dar la pista al compilador. En este artículo de Wikipedia nos explican cómo escribir bucles para que el compilador los empaquete.

La mejora es abismal: Usando OpenMP conseguimos que el programa funcione aproximadamente 4x más rápido, pero combinando OpenMP con SSE2 obtenemos una aceleración de hasta 40x. Merece la pena, ¿no? En el siguiente enlace encontraréis el programa que he escrito para comprobarlo, se incluyen instrucciones de compilación en los comentarios:

    >> Descargar parallel.c <<

Experimentos

En la siguiente gráfica aparecen los tiempos de ejecución medios para cuatro compilaciones:

• Sin optimizar: /arch:IA32 en Visual Studio y -mno-sse en GCC.
• Optimizando: /arch:IA32 /Ox en Visual Studio y -Ofast -mno-sse en GCC.
• Sólo OpenMP: /arch:IA32 /Ox /openmp en Visual Studio y -Ofast -mno-sse -fopenmp en GCC
• OpenMP + SSE2: /arch:SSE2 /Ox /openmp en Visual Studio y -O3 -msse2 -fopenmp en GCC.

En Linux es más difícil compilarlo, porque SSE2 se utiliza por defecto y hay que compilar la función run() aparte sin SSE ni SSE2, y además clock() suma ticks por cada una de las hebras, haciendo necesario el uso de omp_get_wtime().

La siguiente gráfica ilustra los tiempos de ejecución en ambos compiladores:

Tiempo de ejecución en un Intel Core i7 2670QM.

Si comparamos el tiempo que tarda el mismo programa funcionando secuencialmente y utilizando OpenMP y SSE2, entenderemos la necesidad de hacer programas que aprovechen las nuevas tecnologías de programación. Y como podemos ver en el código de ejemplo, es bastante fácil adaptar un programa que ya tenemos para que funcione mucho más rápido.