cerrar-sesion editar-perfil marker video calendario monitor periodico fax rss twitter facebook google-plus linkedin alarma circulo-derecha abajo derecha izquierda mover-vertical candado usuario email lupa exito mapa email2 telefono etiqueta

400410402. Optimización de Software para Procesadores de Núcleo múltiple

Escrito por Redacción en Tema de portada
no hay comentarios Haz tu comentario
Imagen de logotipo de facebook Imagen de logotipo de Twitter Imagen de Logotipo de Google+ Imagen de logotipo de Linkedin

Por Edwin Verplanke

Con potencial para mejoras significativas en las prestaciones, los procesadores de núcleo múltiple presentan el reto, para los desarrolladores de software, de establecer la mejor forma de validar y optimizar el código. Algunos de estos retos se hicieron evidentes cuando convertimos a Amide, una aplicación Open-Source de Linux, de código de un solo hilo a código de hilos múltiples. En el presente artículo, voy a comentar este proyecto, centrándome en el hilado de la inspección del código, la descomposición y la evaluación.

Amide (amide.sourceforge.net) está diseñado para visualizar, analizar y registrar conjuntos volumétricos de datos de imágenes médicas. Escrito por Philippe Lacroute, Amide soporta características para rotar imágenes, seleccionar capas a visualizar, y fusionar múltiples imágenes; véase la Figura 1. VolPack (graphics.stanford.edu/software/VolPack) es una biblioteca portátil para la reproducción de volumen que es invocada por Amide.

Inspección del código existente

Nuestro primer paso fue inspeccionar el código de la aplicación “de inicio” para entender su paralelismo intrínseco y la eficacia con que usaba los recursos del hardware. Las cuatro tareas siguientes nos ayudaron a entender mejor la estructura de la aplicación antes de portarla a un par de Procesadores Xeon de Intel de doble núcleo LV 2.0 GHz.

Reunión de información sobre el código. Reunimos información sobre el funcionamiento en el momento de ejecución y sobre las características de control del código. Lo primero indica los segmentos de código que se benefician más con la paralelización, y lo segundo identifica las localizaciones para dividir el trabajo. Este análisis pone de relieve el paralelismo intrínseco del código e indica lo bien que los recursos del hardware (como la memoria caché del procesador) gestionan las estructuras de datos.

(Edwin Verplanke es arquitecto de soluciones para plataformas de la División de Procesadores de Infraestructura de Intel. Se puede contactar con él en [edwin.verplanke@intel.com)]

Antes de ponerse con el código en paralelo, conviene empezar con un programa optimizado. Las mayores ventajas proceden de poner en paralelo el código que se ejecuta con mayor frecuencia y que consume la mayor cantidad de tiempo de ejecución. Si, mediante la optimización de un solo hilo, varía el porcentaje de tiempo que se necesita para distintas invocaciones de función, en ese caso la decisión sobre qué funciones poner en paralelo puede que cambie también.

Una vez que se ha optimizado el código para el caso del hilo único, podemos utilizar herramientas de perfil de funcionamiento para establecer cuales son los mejores candidatos para ser puestos en paralelo.

Nuestro análisis de Amide y de VolPack resultaron en el organigrama de datos de la Figura 2. El gráfico refleja el flujo de datos a través de los principales bloques de código y tres bucles, y representa la arquitectura del software de la aplicación.

Reunimos los datos sobre el funcionamiento de Amide, según la medida del tiempo requerido para reproducir una imagen tras la solicitud de los usuarios de visualizar la imagen desde un ángulo nuevo.

Dependiendo del ángulo de la rotación, Amide decide si busca el conjunto de datos de la imagen desde el eje x, y, o el z. Nos dimos cuenta de que el tiempo que se necesitaba para mostrar una imagen dependía del eje que Amide elegía para atravesar. Por ejemplo, una búsqueda por el eje z tiende a ser aproximadamente 3 veces más rápida que por el eje x, ilustrado para 1000 rotaciones en la Figura 3.

Usamos el tiempo de reproducción de imágenes como nuestra medida de funcionamiento para medir la eficacia de nuestra implementación de puesta en paralelo.

Esta variación en el tiempo de reproducción de los ejes z y x se explica por el tramo de memoria de la búsqueda de píxeles de 2 dimensiones. Para el eje z, se accede a los bytes de forma secuencial, con un tramo de cuatro bytes, que es relativamente corto. En otras palabras, Amide lee bloques de datos secuenciales y regulares que encajan muy bien en la memoria caché.

Esta regularidad en los datos permite también que la CPU pueda predecir los datos necesarios par instrucciones futuras. Basándose en esas predicciones, la CPU traslada de forma preventiva datos de la memoria a su caché para ocultar la latencia de memoria. Este proceso, denominado “prerrecolección”, permite que la CPU cargue con antelación su caché en previsión de futuros accesos.

Como contrapunto, la tasa de aciertos de caché para búsquedas en el eje x era de un 26 por ciento; este resultado está asociado con el relativo gran tramo de memoria (976 bytes) Con tramos de acceso a memoria de 1 KB o más, el pre-recolector de datos puede resultar significativamente menos efectivo. La perfección del hardware normalmente se configura en BIOS y puede ser desactivada manualmente.

Indicación de dependencias externas. A continuación, examinamos las dependencias externas que se manifestaron mediante un alto nivel de tiempo de inactividad. Cuando se minimiza el tiempo de inactividad, las funciones que consumen la mayor parte del tiempo tienden a ser trozos del código de computación intensiva.

Si las funciones del código están esperando algo (el disco duro, la red, el input del usuario, o lo que sea) la paralelización no va a acelerar esas interfaces externas. Una vez nos hemos convencido de que el código estaba libre de dependencias externas, que se ejecutaba sin interrupción y que no tenía ninguna interacción con dispositivos periféricos, decidimos que era el mejor candidato para la paralelización.

Identificación de oportunidades para la paralelización. Teníamos que decidirnos por un método para realizar la puesta en paralelo – dividir los datos o dividir el control. En nuestro caso, los datos de la imagen se guardan en una matriz unidimensional. Podíamos dividir o bien según los datos (con cada núcleo responsable del acceso a los píxeles en su cuarta parte de matriz) o según el control (dividiendo uno de los bucles entre sus iteraciones).

Estos métodos son con frecuencia equivalentes, porque la misma iteración del bucle accede a los mismos datos cada vez que se invoca esta función. No obstante, conforme rotamos la imagen, va cambiando el número de iteraciones de bucle, como lo hacen los datos que toca una iteración de bucle concreta.

Decidimos que la división de la computación por datos nos llevaría a grandes desequilibrios de carga porque cada una de las reproducciones no tocan todos los datos, y sólo los bucles más recónditos miran los datos en busca de píxeles que se pueden visualizar. Desde algunos ángulos, sólo uno o dos núcleos estarían activos. Así que dividimos la computación por el control. Cada núcleo era responsable de establecer un cuarto de los píxeles a mostrar por el monitor.

((El nivel siguiente dispara la función Initialize Image que ejecuta New_Pixel_Loop, con un número determinista de iteraciones))

Para dividirlo por el control, teníamos que decidir a qué nivel, para poder poner este código en paralelo. En otras palabras, si el código está anidado, ¿a qué profundidad dentro de la estructura del anidado deberían crearse los hilos Y ¿qué bucle (véase la Figura 2) debería dividirse entre los cuatro núcleos? Estuvimos evaluando tres niveles de anidado correspondientes a los tres bucles (de menor a mayor).

Solid_Pixel_Search_Loop,
New_Pixel_Loop, Image_Loop

El nivel más bajo de hilado contiene la función con la mayor carga de trabajo (compAR11B.c, disponible online; véase www.ddj.com), que ejecuta Solid_Pixel_Search_Loop. Dentro de este bucle, compAR11B.c accede a la matriz principal y comprueba si hay píxeles que contengan datos.

Se detiene cuando encuentra un píxel con datos. Este tipo de bucle no es adecuado para la puesta en paralelo porque, para cualquier ejecución dada, ejecuta para un número indeterminado de iteraciones. Este bucle podría consumir un núcleo mientras los otros núcleos están inactivos, esperando que se produzca un evento de sincronización.

El nivel siguiente dispara la función Initialize Image que ejecuta New_Pixel_Loop, con un número determinista de iteraciones (por ejemplo, mientras no sea un número constante, el número se conoce al comienzo de la ejecución del bucle). Este bucle invoca compAR11B.c durante todas las iteraciones, lo que le convierte en un candidato excelente para la paralelización, porque podemos dividir las iteraciones por el número de hilos y distribuir la carga de trabajo por igual entre los cuatro núcleos.

Otra ventaja de poner en paralelo este FOR LOOP es que, como los hilos invocan a compAR11B.c múltiples veces antes de coordinarse unos con otros, se minimizan los costes extra de la sincronización.

En el nivel más alto, Image_Loop podría ponerse en paralelo para que cada hilo reproduzca una imagen diferente. Amide podría entonces invocar esta función múltiples veces, una vez para cada imagen, mostrando múltiples imágenes a la vez. Esto tiene dos posibles inconvenientes: – Habrá núcleos inactivos siempre que el número de imágenes que se están procesando sea menor que el número de núcleos.
– Cada imagen necesita cantidades de tiempo sustancialmente diferentes a reproducir.

Si un hilo completa su imagen mucho antes que el otro, sólo hay paralelismo una parte del tiempo. Así, el equilibrio de la carga es menos consistente cuando los hilos se dividen en este nivel superior.

Localización de dependencias de datos. La cuarta tarea consistía en examinar las estructuras de los datos para determinar si el paralelismo podía crear dependencias de datos, lo que provocaría una ejecución incorrecta o un impacto negativo en el funcionamiento. Una fuente de dependencias de datos se produce cuando múltiples hilos escriben al mismo elemento de datos.

Sin un código de sincronización adicional, esto puede provocar resultados incorrectos. El código de sincronización y los mecanismos de bloqueo de datos (como los semáforos) pueden conducir a una parada de hilos.

Además de garantizar que múltiples hilos no estén escribiendo al mismo elemento de datos, es importante minimizar cualquier falsa participación conjunta de memoria entre los hilos. La participación falsa ocurre cuando dos o más núcleos están actualizando bytes de memoria distintos, que coinciden en la misma línea de caché.

Técnicamente, los hilos no comparten exactamente la misma localización de memoria, pero como el procesador se encarga de los tamaños de línea de caché de la memoria, los bytes terminan siendo compartidos de todas formas. Como los múltiples núcleos no pueden almacenar en el caché la misma línea de memoria al mismo tiempo, la línea compartida de caché se está enviando constantemente de un núcleo a otro, creando pérdidas de caché y, potencialmente, enormes latencias de memoria.

Amide invoca a VolPack para que reproduzca una imagen de visualización en 2 dimensiones al procesar un conjunto de datos de imágenes. Esto requiere buscar en el conjunto de datos de la imagen, pero nunca cambiándolo, y escribir el resultado como imagen de visualización en 2 dimensiones en un controlador de gráficos para que se muestre en un monitor. Ambas estructuras (el conjunto de datos de imágenes médicas y la imagen de visualización en 2 dimensiones) se almacenan como matrices.

((En nuestra implementación, el Núcleo 1 ejecuta primero el código de serie para cargar la imagen, que precede al flujo de datos))

Cada iteración de bucle corresponde a una posición en la imagen de visualización en 2 dimensiones, y las iteraciones consecutivas escriben a las posiciones vecinas. De esta forma, al dar a cada núcleo un conjunto de iteraciones consecutivas, en lugar de asignar las iteraciones por round robin, los núcleos nunca escriben a la misma posición – y sólo escriben a las posiciones vecinas (falsa participación conjunta) en su iteración primera o última.

Código para descomponer

VolPack realiza la misma operación en cada píxel, y esta característica, combinada con la relativamente simple estructura de datos, ofrece una sencilla estrategia para la paralelización. Utilizamos hilos POSIX para dividir New_Pixel_Loop en cuatro sub-bucles, cada uno ejecutándose en uno de los cuatro núcleos.

En nuestra implementación, el Núcleo 1 ejecuta primero el código de serie para cargar la imagen, que precede al flujo de datos de la Figura 2, mientras los otros tres núcleos están inactivos. A continuación, el núcleo 1 usa hilos POSIX para tejer tres hilos para los núcleos 2 al 4. Nuestros expertos en software tardaron dos días en inspeccionar el código, poner el código en paralelo para la reproducción de imágenes, y comprobar el equilibrio de la carga de trabajo.
Crear los hilos. El Listado número 1 inicializa un hilo por núcleo mediante pthread_create. Cada hilo ejecuta la misma función, vp_thread_task_loop. El Listado número 1 usa una variable NUM_THREADS, que corresponde al número de núcleos del sistema. Como el número de núcleos no está con código protegido, se puede portar fácilmente para que se ejecute en sistemas que tengan cualquier número de núcleos.
Inicio de los hilos. Después de crear los hilos, el núcleo 0 pone a Amide en paralelo en el New_Pixel_Loop para que se ejecute en cuatro núcleos. El Listado número 2 ilustra cómo se consigue. Se le asignan variables a cada núcleo en una matriz global mediante la instrucción:

loop_args(i).kmystart = cur_num;

Un cuarto de los índices de matriz se pasan a cada núcleo para procesar el volumen de la imagen utilizando variable loop_args(i). Los cuatro núcleos se inician asignando primero memoria para datos con:

vp_pthreads_data->inputs(i) = &(loop_args(i))

A continuación, cada núcleo empieza a ejecutar el código LOOP_TASK iniciado por:

vp_pthreads_data->task_number = LOOP_TASK;

Por último, se libera cada núcleo para que empiece a procesar mediante:

pthread_cond_signal
(vp_pthreads_data->task_cond(i)

Evaluación del funcionamiento del código

Antes de examinar los datos generales del funcionamiento, ¿qué es lo que deberíamos esperar? Dado que migramos Amide de un sistema de núcleo simple a uno de cuatro núcleos, lo más que cabe esperar de forma realista es una mejora de cuatro veces el funcionamiento lineal original. Este es un máximo teórico, porque los núcleos comparten recursos como enlaces comunes y memoria, que pueden introducir retrasos en la ejecución.

Hay también un coste asociado con el mantenimiento de la coherencia de datos entre los cachés del sistema. Haciendo un cálculo aproximado, estos factores pueden conducir a una reducción de entre un 10 y un 20 por ciento en el funcionamiento del sistema. Por consiguiente, por término medio, anticipamos que un sistema de cuatro núcleos funciona dentro de una gama de entre 3,2 y 3,6 veces más rápido que un sistema de núcleo simple.

En primer lugar, medimos el funcionamiento de la aplicación en general, con respecto al código original, como se mide al tener en cuenta el tiempo que le llevó a VolPack reproducir las imágenes por los ejes z y x. (Tabla 2) Estas dos rotaciones fueron representadas a partir del mismo conjunto de datos de imágenes en dos ejes diferentes. El resultado de nuestra migración de un sistema de a núcleo sencillo a uno de cuatro núcleos fue una aceleración del funcionamiento de entre 3,2 y 3,4 veces. Estos resultados indican que esta implementación de la puesta en paralelo fue eficaz y se optimizó razonablemente bien.

((Dado que migramos Amide de un sistema de núcleo simple a uno de cuatro núcleos, lo más que cabe esperar de forma realista es una mejora de cuatro veces el funcionamiento lineal original))

A continuación examinamos la tasa de aciertos del caché. La Tabla 2 muestra la tasa de aciertos del caché L2 para las imágenes reproducidas en los ejes z y x ejecutados en un núcleo, dos núcleos y cuatro núcleos. En el eje z, la tasa de aciertos del caché es bastante consistente para uno, dos y cuatro núcleos, y esta entorno a un 76 por ciento. En el eje x, la tasa de caché L2 cae a un 34 por ciento con cuatro núcleos. Esta caída en el número de aciertos del caché L2 puede ser una evidencia más de un tiempo de reproducción más lento, para reproducciones en el eje x de la Tabla 1.

En tercer lugar, examinamos la utilización de la CPU. Durante la reproducción de imágenes, todos los núcleos están funcionando casi a un 100 por cien para las configuraciones: Un núcleo, dos núcleos, y cuatro núcleos. Todos los núcleos disponibles están compartiendo equitativamente la carga de trabajo. La utilización de la CPU se midió con el comando TOP de Linux.

La cuarta medición que hicimos del código fue el coste extra de la sincronización, que nos ofrece una medida de los recursos que no son de computación y que se necesitan para mantener los hilos que, de otra forma, se usarían para acelerar la aplicación. La Figura 4, generada por el Perfilador de Hilos de Intel, muestra el Núcleo 1 cargando la imagen durante 45 segundos, y después tejiendo hilos a los núcleos 2, 3, y 4.

Las zonas verdes de tono más oscuro representan reproducciones individuales de imágenes en las que las reproducciones empiezan entorno a los 46, 48, 56, 59, 62, y 68 segundos.

Los costes extra de la sincronización se muestran en rojo cuando su duración es superior a 30 millonésimas de segundo. La única instancia de sincronización mostrada en la Figura 4 se produce cuando el núcleo 1 crea los hilos para los núcleos 2, 3 y 4 en un tiempo de 46 segundos. Nos sentimos satisfechos con este relativamente bajo nivel de coste extra de sincronización.

((El desarrollo de código paralelo para procesadores de núcleos múltiples requiere un cuidadoso estudio de los métodos de hilado y un profundo análisis del funcionamiento resultante))

Nuestra última medición de código fue el coste extra de la parada de hilos, que nos da la medida del tiempo inactivo de los núcleos porque éstos están esperando los recursos del sistema o asignaciones de trabajo. La Figura 5 muestra que un único hilo se ejecuta durante 66 segundos (CL1); esta es la suma del tiempo que tarda el núcleo 1 en cargar la imagen, o el tiempo de inactividad entre la reproducción de imágenes. Durante el resto del tiempo, se están ejecutando cuatro hilos (CL4), que corresponde a la reproducción de imágenes. Esto significa que tenemos cuatro núcleos funcionando a toda marcha durante la reproducción de imágenes, lo que es una buena cosa.

Hay breves períodos en los que sólo dos o tres hilos están funcionando (CL 2 y CL3), pero son relativamente breves. Los períodos de CL2 y CL3 son mejores que los de CL1 (un hilo), pero no son tan buenos como los de CL4 (cuatro hilos). Los perfiladores de hilos normalmente ofrecen unas visualizaciones más detalladas de las paradas de hilo, y pueden mapear las paradas de hilo al código fuente responsable.

Conclusión

El desarrollo de código paralelo para procesadores de núcleos múltiples requiere un cuidadoso estudio de los métodos de hilado y un profundo análisis del funcionamiento resultante. El método que he descrito aquí se puede aplicar a cualquier aplicación que pase de un único hilado a uno múltiple para sacarle así partido al funcionamiento del procesador de núcleo múltiple. El estudio de este caso de migración de código muestra que es posible tomar una aplicación diseñada para que funciones en un procesador de un solo núcleo y migrarla a un sistema de cuatro núcleos en cuestión de días, a la vez que se consigue un funcionamiento que mejora en más de tres veces. DDJ

Listado 1

//listado 1

vp_begin_threads();
vp_threads_begun = 1;

void vp_begin_threads()

int i;
int mask = 0xf;
vp_pthreads_data = vp_create_thread_data();
if (vp_pthreads_data == NULL)

printf(«Unable to allocate memory for threads.\n»);
return;

for(i=1;i
vp_pthreads_args(i).data = vp_pthreads_data;
vp_pthreads_args(i).id = i;
pthread_create(&(vp_threads(i)), NULL, vp_thread_task_loop,
&(vp_pthreads_args(i)));


//Listado número 1

//listado
vp_thread_big_loop_args loop_args(NUM_THREADS);
int num = (kcount)>>THREAD_SHIFT;
int extras = (kcount)&THREAD_MASK;
int cur_num = kstart;

loop_args(0).vpc = vpc;
loop_args(0).kstart = kstart;
loop_args(0).kinc = kinc;
loop_args(0).icount = icount;
loop_args(0).jcount = jcount;
loop_args(0).kcount = kcount;
loop_args(0).istride = istride;
loop_args(0).jstride = jstride;
loop_args(0).kstride = kstride;
loop_args(0).composite_func = composite_func;

for(i=0;i
loop_args(i) = loop_args(0);
loop_args(i).kmystart = cur_num;
loop_args(i).id = i;
cur_num += (num * kincr);
cur_num += ((i < extras) * kincr); loop_args(i).kstop = cur_num;

vp_pthreads_data->completed_threads = 0;
for(i=1;i
vp_pthreads_data->inputs(i) = &(loop_args(i));
vp_pthreads_data->task_number = LOOP_TASK;
pthread_cond_signal(vp_pthreads_data->task_cond(i));

//Listado número 2

Listado 2
//listado

vp_begin_threads();
vp_threads_begun = 1;

void vp_begin_threads()

int i;
int mask = 0xf;
vp_pthreads_data = vp_create_thread_data();
if (vp_pthreads_data == NULL)

printf(«Unable to allocate memory for threads.\n»);
return;

for(i=1;i
vp_pthreads_args(i).data = vp_pthreads_data;
vp_pthreads_args(i).id = i;
pthread_create(&(vp_threads(i)), NULL, vp_thread_task_loop,
&(vp_pthreads_args(i)));


//Listado número 1

//listado
vp_thread_big_loop_args loop_args(NUM_THREADS);
int num = (kcount)>>THREAD_SHIFT;
int extras = (kcount)&THREAD_MASK;
int cur_num = kstart;

loop_args(0).vpc = vpc;
loop_args(0).kstart = kstart;
loop_args(0).kinc = kinc;
loop_args(0).icount = icount;
loop_args(0).jcount = jcount;
loop_args(0).kcount = kcount;
loop_args(0).istride = istride;
loop_args(0).jstride = jstride;
loop_args(0).kstride = kstride;
loop_args(0).composite_func = composite_func;

for(i=0;i
loop_args(i) = loop_args(0);
loop_args(i).kmystart = cur_num;
loop_args(i).id = i;
cur_num += (num * kincr);
cur_num += ((i < extras) * kincr); loop_args(i).kstop = cur_num;

vp_pthreads_data->completed_threads = 0;
for(i=1;i
vp_pthreads_data->inputs(i) = &(loop_args(i));
vp_pthreads_data->task_number = LOOP_TASK;
pthread_cond_signal(vp_pthreads_data->task_cond(i));

//Listado número 2

Etiquetas

Noticias relacionadas

Comentarios

No hay comentarios.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos necesarios están marcados *

Debes haber iniciado sesión para comentar una noticia.