Compiladores y más: gloptimizaciones - Calendae | Informática, Electrónica, CMS, Ciberseguridad

Compiladores y más: gloptimizaciones

Hola otra vez. Te escribe Simón Sánchez y en esta ocasión te voy a hablar sobre Compiladores y más: gloptimizaciones

En mi última columna, hablé de las mejoras de rendimiento en uno de los puntos de referencia de punto flotante SPEC CPU2000, 172.mgrid, entre 1999 y 2006, e introduje una optimización (que llamamos Eliminación de redundancia transportada por bucle) que mejora significativamente mgrid. El comité de CPU de SPEC ha sido bastante cuidadoso con las pruebas comparativas sensibles al compilador. El conjunto de pruebas de referencia SPEC ’89 original incluía 030.matrix300 (multiplicación de matriz densa). Dado que la multiplicación de matrices es parte de un conjunto de operaciones fundamentales realizadas en muchas aplicaciones numéricas, se consideró un buen candidato para un punto de referencia. Pero, para citar a Reinhold Weicker de Boletín SPEC (diciembre de 1995): «Sin embargo, si un programa se convierte en un punto de referencia, el compilador

En este caso, los compiladores se han modificado para enlosar agresivamente los bucles; en cada tarjeta, el programa realiza una multiplicación de submatriz donde las submatrices se almacenan en caché, mejorando el rendimiento total hasta en un factor de ocho. (El término «mosaico de bucle» o «mosaico de espacio de iteración» fue sugerido por mi esposa en 1986; estaba buscando un término mejor para usar en un artículo, ella estaba mirando el piso de la cocina). Como esta optimización tenía un impacto y no se aplicó a los otros puntos de referencia, el comité SPEC decidió que no era una contribución justa a una métrica de desempeño general, y matrix300 se retiró en 1992.

La última vez me di cuenta de que Dell había lanzado una SPEC CPU2000 en noviembre de 1999 en una estación de trabajo Pentium III Precision 420 de 733 MHz y otra en octubre de 2006 en una estación de trabajo Core 2 Extreme Precision 390 de 2.66 GHz. eligió comparar estas dos ejecuciones simplemente porque provenían del mismo proveedor con siete años de diferencia. La base CFP2000 resultó ser de 242 a 2679, un factor de poco más de 11. El gran ganador fue 179.art, que mejoró de una relación de 313 a 9306, casi un factor de 30 velocidades. ¿Qué explica este factor de 30? ¿Podemos esperar mejoras similares para cualquier otro programa?

Una forma de conseguir una gran aceleración es hacer que el caso base sea muy lento; por lo tanto, incluso las optimizaciones simples pueden proporcionar una buena mejora. A veces, el programa está escrito de una manera que parece intencionalmente dirigida a hacerlo funcionar lentamente. Un caso de este tipo aparece en ART.

El punto de referencia ART (Adaptive Resonance Theory Neural Network for Image Ecognition) está escrito en C y el ciclo crítico es:

    struct
double *I; double W, X, V, U, P, Q, R;
* f1_layer;
double **bus;
....
for( tj = 0; tj Y[tj].y = 0;
if( !Y[tj].reset )
for( ti = 0; ti Y[tj].y += f1_layer[ti].P * bus[ti][tj];
}

Este ciclo aparece en diferentes lugares del programa y la mayor parte del tiempo se dedica a él; acelere este ciclo y el programa se ejecutará rápidamente.

Sin embargo, aquí hay varios problemas. La estructura f1_layer tiene 8 miembros, cada uno de 8 bytes de longitud (asumiendo punteros de 64 bits). Esto significa que cada elemento de f1_layer ocupa una fila completa de caché de 64 bytes. Entonces, mientras atravesamos la matriz f1_layer en el ciclo interno, solo usamos un valor en cada fila de caché. Peor aún, el bus de matriz bidimensional se asigna dinámicamente y estamos atravesando las columnas; esto significa dos accesos a la memoria (para obtener el bus de puntero de fila[ti], luego el valor del bus[ti][tj]). En ambos casos, el programa abusa del ancho de banda de la memoria en el bucle interno, a menos que todo el conjunto de datos encaje en la caché.

Algunos comentarios más: resulta que el bucle interno tiene un recuento de viajes de alrededor de 10,000, mientras que el bucle externo tiene solo 6 iteraciones y el condicional alrededor del bucle interno nunca se dispara (el reinicio es siempre 0), al menos no en el punto de referencia conjunto de datos, por lo que el bucle interno siempre se ejecuta. Sin embargo, estos hechos solo se conocen en tiempo de ejecución.

He visto tres formas de hacer que este ciclo sea mucho más rápido. Algunos compiladores implementan lo que se ha llamado truco ART, reorganizando los datos para la estructura f1_layer. La matriz de estructura se reorganiza para convertirse en una estructura de matriz. Ocupa la misma cantidad de espacio, pero ahora cada elemento f1_layer[ti].P se convierte en f1_layer.P[ti], por lo que los elementos consecutivos son adyacentes en la caché, y el rendimiento de la caché y de todo el programa mejora significativamente.

    struct
double **I; double *W, *X, *V, *U, *P, *Q, *R;
f1_layer;
double **bus;
....
for( tj = 0; tj Y[tj].y = 0;
if( !Y[tj].reset )
for( ti = 0; ti Y[tj].y += f1_layer.P[ti] * bus[ti][tj];
}

Hice esto a mano en un Intel EM64T Xeon más antiguo de 3.4GHz, usando compiladores PGI y medí una mejora del rendimiento del 49%. Puede imaginarse qué tipo de análisis de todo el programa permitiría o no esta reorganización, y muy pocas veces es factible. Sin embargo, este punto de referencia es tan importante que algunos compiladores dan este paso. Aquí hay una optimización (para usar mal el término) que nunca se habría inventado si no hubiera sido por este punto de referencia en particular.

Un truco diferente consiste en intercambiar los dos bucles. El problema a resolver son los accesos al bus del arreglo, que no son adyacentes, no tienen localidad y requieren dos cargas por iteración, problemas que desaparecen si se intercambian los dos bucles. Sin embargo, después del intercambio, el nuevo ciclo interno tiene un recuento de viajes muy corto (aunque el compilador probablemente no lo sepa). El otro problema más serio es que el intercambio de los bucles trae el condicional dentro de ambos bucles.

    struct
double *I; double W, X, V, U, P, Q, R;
* f1_layer;
double **bus;
....
for( tj = 0; tj Y[tj].y = 0;
for( ti = 0; ti for( tj = 0; tj if( !Y[tj].reset )
Y[tj].y += f1_layer[ti].P * bus[ti][tj];
}

En el propio Xeon, medí un aumento de velocidad de 2,33. Sin embargo, esto es bastante peligroso, desde el punto de vista del desempeño; en lugar de las pruebas condicionales «numf2s», ahora hay pruebas «numf1s * numf2s». Si la prueba no se activa, la versión editada puede funcionar un poco más lenta que la original. Sin embargo, al menos un compilador lo implementa y obtiene más de un factor de dos mejoras en todo el programa, principalmente debido a esta transformación de bucle.

El tercer truco, no implementado por ningún compilador (que yo sepa aún), es dejar los bucles como están y transponer el bus de matriz (y una matriz de acceso similar, tds). Resulta que estas matrices se asignan dinámicamente, pero se accede a ellas en el tamaño incorrecto. Si transponemos las dimensiones, el rendimiento de este bucle y todo el programa realmente grita. En ese mismo Xeon, medí un aumento de velocidad de 4.3.

Este último es un poco más difícil de implementar automáticamente. El problema más serio es que C realmente no tiene matrices bidimensionales; para obtener una matriz dinámica bidimensional, el programa primero debe asignar un vector unidimensional de punteros. Para transponer una matriz, el programa debe asignar un vector de diferente tamaño. Los puristas sostienen que el programa modificado puede asignar más espacio y, por lo tanto, puede quedarse sin memoria para algunos conjuntos de datos grandes.

Además, las mejoras de rendimiento no son muy estables. Las aceleraciones que medí en el EM64T fueron 1,49 para la reorganización de la matriz de estructura, 2,3 para el intercambio de bucles y 4,3 para la transposición de la matriz. El mes pasado, comparé el rendimiento con un Intel Pentium III de 733 MHz más antiguo y un Intel Core 2 Extreme de 2.66 GHz. Las aceleraciones para estas tres optimizaciones en estas dos máquinas (y la EM64T) se resumen aquí:

EM64T PIII Core2
1,49 1,64 1,08 Reorganización de matriz de estructura
2,33 1,00 1,03 intercambio de bucle
4.34 1.19 1.48 transposición de matrices

Supongo que estas optimizaciones tienen un efecto mucho menor en el último Core 2 porque todos los datos encajan en el caché mucho más grande.

Entonces, el mes pasado hablé de ajustar el compilador para 172.mgrid, donde una nueva optimización ha mejorado su rendimiento en aproximadamente un 20%; Afortunadamente, descubrimos que esta nueva característica también se aplica a muchas otras aplicaciones de usuario. Este mes presenté la optimización del compilador para 179.art, donde la optimización agresiva puede mejorar el rendimiento en función de factores (en algunas máquinas). No entraré en hacks, trucos y otros ajustes para los otros puntos de referencia de SPEC CPU2000; el número de trucos del compilador está relacionado linealmente con el número de evaluaciones comparativas.

Con la importancia cada vez mayor del rendimiento de referencia, se anima a los equipos de desarrollo de compiladores a realizar esfuerzos agresivos (o incluso heroicos) para optimizar el rendimiento en estos programas. La única razón por la que hacen esto es que los proveedores y usuarios (y los gerentes de producto de los compiladores) otorgan una importancia artificial a ciertos resultados de referencia. Sin embargo, estas optimizaciones, aunque impresionantes, pueden tener poco o ningún valor, o incluso tener un valor negativo en el dominio de usuario más general, o incluso en el mismo programa con diferentes entradas. Como se muestra aquí para ART, el valor de optimización puede disminuir a esencialmente cero a medida que avanza la arquitectura.

Por lo tanto, en el espíritu del Golden Raspberry Award (http://www.razzies.com/) y los premios Ig Nobel (http://www.improbable.com/ig), Propongo honrar la optimización más escandalosa y específica de referencia con un premio propio, el Gloptimization Award, o Gloppy para abreviar. El premio en sí sería un montón de glops (o representaciones de los mismos), definido en mi American Heritage Dictionary como “n. 1. Una mezcla sucia, como comida. 2. Algo, como escribir, que no tiene valor. v. 1. Cubra con glop. 2. Ponerse glop. «La recompensa, al menos, es apropiada. Se debe otorgar más crédito a una optimización que se aplica a un único punto de referencia; crédito adicional si ralentiza considerablemente otros puntos de referencia o aplicaciones. Puede proponer recompensas póstumas para optimizaciones que realmente se eliminan. por los compiladores cuando se retiran los puntos de referencia específicos. Las optimizaciones anteriores sin duda serían candidatas para un Gloppy, aunque tal vez no gane.

La lección para los clientes es que los puntos de referencia estándar son herramientas valiosas, pero no deberían ser el único o principal medio de comparar el rendimiento del sistema. La mejor medida es siempre el rendimiento de sus aplicaciones, para las cuales los sistemas y el software que los acompaña no están específicamente adaptados.

SPEC (R) es una marca registrada de Standard Performance Evaluation Corporation (http://www.spec.org/).

—–

Michael Wolfe ha estado desarrollando compiladores durante más de 30 años tanto en el ámbito académico como en la industria, y ahora es ingeniero senior de compilación en The Portland Group, Inc. (www.pgroup.com), una subsidiaria de propiedad absoluta de STMicroelectronics, Inc. Las opiniones expresadas en este documento son las de

Recuerda compartir en tus redes sociales para que tus colegas lo consulten

??? ? ? ???

Comparte