¿Qué es importante al optimizar el caché de la CPU (en C)?

13

Al leer estas dos preguntas , veo que comprender el comportamiento del almacenamiento en caché de la CPU puede ser importante cuando se trata de grandes cantidades de datos en la memoria. Me gustaría entender la forma en que funciona el almacenamiento en caché para agregar otra herramienta a mi caja de herramientas de optimización.

¿Cuáles son los puntos centrales sobre la forma en que funciona el caché de la CPU para que pueda escribir código que lo use con sensatez? En relación con esto, ¿hay alguna forma de crear un perfil del código para ver si el uso deficiente de la memoria caché está ralentizando las cosas?

Timothy Jones
fuente
Los cachés no son iguales en todas partes; obviamente, varían en tamaño. No espere aprender secretos profundos, solo buenas prácticas (como el consejo de Michael Borgwardt).
David Thornley

Respuestas:

17
  • Mantenga sus datos pequeños si es posible
  • Mantenga las cosas a las que se accederá juntas (o justo después de otra) una al lado de la otra en la memoria
  • Aprenda sobre los parámetros de optimización de su compilador
  • Lea lo que todo programador debe saber sobre la memoria para obtener más detalles de los que pueda desear.
Michael Borgwardt
fuente
+1 para "Mantenga las cosas a las que se accederá juntas una al lado de la otra"; ese es el que es fácil de olvidar.
Donal Fellows
Y dile al compilador que optimice.
derecha el
@WTP: derecha - agregado.
Michael Borgwardt
Además, mantenga mutexes bien separados. Cambiar un mutex (debería) vaciar todas las líneas de caché en las que se encuentra, en todas las CPU. Esto puede ser un gran éxito de rendimiento si ha logrado obtener 2-3 mutexes en una sola línea de caché.
Vatine
12

La complejidad de este problema ha ido más allá de la comprensión humana en estos días. (Ha sido así desde los últimos 5 años). Combine eso con el paralelismo de vectores cortos (SIMD) y tendrá la sensación de que la optimización del código a mano ya no es económicamente factible, no es que no sea posible, pero sí lo sería. Ya no será rentable.

El enfoque actual es confiar en enseñar a las computadoras cómo optimizar, haciendo variaciones de código que computan las mismas respuestas con diferentes estructuras (bucles, estructura de datos, algoritmos) y evaluando automáticamente el rendimiento. Las reglas para las transformaciones de código se especifican con un modelo matemático muy riguroso, por lo que es algo que tanto los científicos informáticos pueden entender como las computadoras pueden ejecutar.

El siguiente es un enlace publicado por Larry OBrien en una de sus respuestas .

http://onward-conference.org/2011/images/Pueschel_2011_AutomaticPerformanceProgramming_Onward11.pdf

rwong
fuente
2
la implementación BLAS más rápida (GotoBLAS) utiliza código optimizado a mano para garantizar el uso máximo de caché para la multiplicación de matrices
quant_dev
2

Es muy posible entender y optimizar para cachés. Comienza con la comprensión del hardware y continúa con el control del sistema. Cuanto menos control tenga sobre el sistema, menos probabilidades tendrá de tener éxito. Linux o Windows ejecutan un montón de aplicaciones / hilos que no están inactivos.

La mayoría de las cachés son algo similares en sus propiedades, usan alguna parte del campo de dirección para buscar aciertos, tienen una profundidad (formas) y un ancho (línea de caché). Algunos tienen búferes de escritura, algunos se pueden configurar para escribir o omitir el caché en escrituras, etc.

Debe ser muy consciente de todas las transacciones de memoria que están ocurriendo y que están llegando a ese caché (algunos sistemas tienen instrucciones independientes y cachés de datos que facilitan la tarea).

Puede hacer que un caché sea inútil fácilmente al no administrar cuidadosamente su memoria. Por ejemplo, si tiene varios bloques de datos que está procesando, con la esperanza de mantenerlos en caché, pero están en la memoria en direcciones que son incluso múltiplos en relación con la verificación de aciertos / errores de cachés, digamos 0x10000 0x20000 0x30000, y tiene más de De esta manera, en el caché, puede terminar rápidamente haciendo algo que funciona bastante lento con el caché encendido, más lento de lo que lo haría con el caché apagado. Pero cambie eso a quizás 0x10000, 0x21000, 0x32000 y eso podría ser suficiente para aprovechar al máximo el caché, reduciendo los desalojos.

En pocas palabras, la clave para optimizar un caché (bueno, aparte de conocer el sistema bastante bien) es mantener todas las cosas para las que necesita rendimiento en el caché al mismo tiempo, organizando esos datos de manera que sea posible tenerlos. todo en el caché a la vez. Y evitando que cosas como la ejecución de código, las interrupciones y otros eventos regulares o aleatorios desalojen porciones significativas de estos datos que está utilizando.

Lo mismo vale para el código. Sin embargo, es un poco más difícil ya que necesita controlar las ubicaciones donde vive el código para evitar colisiones con otro código que desea mantener en la memoria caché. Mientras prueba / perfila cualquier código que pasa por un caché que agrega una sola línea de código aquí y allá o incluso un solo nop, cualquier cosa que cambie o cambie las direcciones donde vive el código de una compilación a otra para el mismo código, cambia donde las líneas de caché caen dentro de ese código y cambian lo que se desaloja y lo que no para las secciones críticas.

viejo contador de tiempo
fuente
1

Las respuestas de nwong y Michael Borgwardt dan buenos consejos.

Además, confíe primero en las optimizaciones del compilador en estos temas.

Si usa un compilador GCC reciente, puede usar (con parsimony) su __builtin_prefetchfunción. Vea esta respuesta en stackoverflow.

Basile Starynkevitch
fuente