Código de diseño para caber en la caché de la CPU?

Question

Cuando escribo simulaciones, mi amigo dice que le gusta intentar escribir el programa lo suficientemente pequeño como para caber en la memoria caché. ¿Tiene esto algún significado real? Entiendo que el caché es más rápido que la RAM y la memoria principal. ¿Es posible especificar que desea que el programa se ejecute desde la memoria caché o al menos cargar las variables en la memoria caché? Estamos escribiendo simulaciones para que cualquier ganancia de rendimiento / optimización sea un gran beneficio.

Si conoce algún enlace bueno que explique el almacenamiento en caché de la CPU, apúnteme en esa dirección.

Answer 1

Al menos con una CPU de escritorio típica, no se puede especificar mucho sobre el uso de caché directamente. Sin embargo, aún puede intentar escribir código compatible con caché. En el lado del código, esto a menudo significa que desenrollar bucles (por solo un ejemplo obvio) rara vez es útil: expande el código y una CPU moderna generalmente minimiza la sobrecarga del bucle. En general, puede hacer más en el lado de los datos, para mejorar la localidad de referencia, proteger contra el intercambio falso (por ejemplo, dos piezas de datos de uso frecuente que intentarán usar la misma parte de la memoria caché, mientras que otras partes permanecen sin usar).

Editar (para hacer algunos puntos un poco más explícitos):

Una CPU típica tiene varias memorias caché diferentes. Un procesador de escritorio moderno generalmente tendrá al menos 2 y, a menudo, 3 niveles de caché. Por (al menos casi) acuerdo universal, "nivel 1" es el caché "más cercano" a los elementos de procesamiento, y los números suben desde allí (el nivel 2 es el siguiente, el nivel 3 después de eso, etc.)

En la mayoría de los casos, (al menos) el caché de nivel 1 se divide en dos mitades: un caché de instrucciones y un caché de datos (el Intel 486 es casi la única excepción de la que tengo conocimiento, con un único caché para ambos instrucciones y datos, pero es tan completamente obsoleto que probablemente no merece mucha reflexión).

En la mayoría de los casos, un caché se organiza como un conjunto de "líneas". El contenido de un caché normalmente se lee, se escribe y se rastrea una línea a la vez. En otras palabras, si la CPU va a usar datos de cualquier parte de una línea de caché, esa línea de caché completa se lee desde el siguiente nivel inferior de almacenamiento. Los cachés que están más cerca de la CPU son generalmente más pequeños y tienen líneas de caché más pequeñas.

Esta arquitectura básica conduce a la mayoría de las características de un caché que importan al escribir código. En la medida de lo posible, desea leer algo en la memoria caché una vez, hacer todo lo que quiera y luego pasar a otra cosa.

Esto significa que a medida que procesa datos, generalmente es mejor leer una cantidad relativamente pequeña de datos (lo suficiente como para caber en la memoria caché), procesar tanto como sea posible y luego pasar al siguiente fragmento de datos. Algoritmos como Quicksort que dividen rápidamente grandes cantidades de entrada en partes progresivamente más pequeñas lo hacen de manera más o menos automática, por lo que tienden a ser bastante amigables con la caché, casi independientemente de los detalles precisos de la caché.

Esto también tiene implicaciones sobre cómo se escribe el código. Si tiene un bucle como:

for i = 0 to whatever
   step1(data);
   step2(data);
   step3(data);
end for

Por lo general, es mejor encadenar tantos pasos juntos como sea posible hasta la cantidad que cabe en la memoria caché. En el momento en que desborda el caché, el rendimiento puede / disminuirá drásticamente. Si el código para el paso 3 anterior es lo suficientemente grande como para que no quepa en el caché, generalmente sería mejor dividir el ciclo en dos partes como esta (si es posible):

for i = 0 to whatever
    step1(data);
    step2(data);
end for

for i = 0 to whatever
    step3(data);
end for

El desenrollado de bucle es un tema muy disputado. Por un lado, puede conducir a un código que es mucho más amigable con la CPU, reduciendo la sobrecarga de instrucciones ejecutadas para el propio ciclo. Al mismo tiempo, puede (y generalmente lo hace) aumentar el tamaño del código, por lo que es relativamente poco amigable con la caché. Mi propia experiencia es que en los puntos de referencia sintéticos que tienden a realizar cantidades realmente pequeñas de procesamiento en cantidades realmente grandes de datos, se gana mucho al desenrollar el bucle. En un código más práctico en el que tiendes a tener más procesamiento en un dato individual, ganas mucho menos, y desbordar el caché que conduce a una pérdida de rendimiento grave no es particularmente raro en absoluto.

El caché de datos también tiene un tamaño limitado. Esto significa que generalmente desea que sus datos se empaqueten de la manera más densa posible para que la mayor cantidad posible de datos quepa en la memoria caché. Solo por un ejemplo obvio, una estructura de datos que está vinculada con punteros necesita ganar bastante en términos de complejidad computacional para compensar

Answer 2

Aquí hay un enlace a un paper en cachés / optimización de memoria por Christer Ericsson (de la fama God of War I / II / III). Tiene un par de años pero sigue siendo muy relevante.

Answer 3

Un documento útil que le dirá más de lo que siempre quiso saber sobre las memorias caché es What Every Programmer Debe saber sobre la memoria por Ulrich Drepper. Hennessey lo cubre muy a fondo. Christer y Mike Acton también han escrito un montón de cosas buenas sobre esto.

Creo que debería preocuparse más por el caché de datos que por el caché de instrucciones; en mi experiencia, las fallas de dcache son más frecuentes, más dolorosas y más útiles.

Answer 4

ACTUALIZACIÓN: 13/01/2014 De acuerdo con este diseñador senior de chips, las fallas de caché ahora son EL factor abrumadoramente dominante en el rendimiento del código, por lo que básicamente estamos desde mediados de los 80 y 286 chips rápidos en términos de cuellos de botella de rendimiento relativo de carga, almacenamiento, número entero. aritmética y errores de caché.

Un curso intensivo en hardware moderno por Cliff Click @ Azul . . . . .

--- ahora lo devolvemos a su programa programado regularmente ---

A veces un ejemplo es mejor que una descripción de cómo hacer algo. En ese espíritu, aquí hay un ejemplo particularmente exitoso de cómo cambié un código para usarlo mejor en cachés de chips. Esto se hizo hace algún tiempo en una CPU 486 y luego migró a una CPU Pentium de 1ra generación. El efecto en el rendimiento fue similar.

Ejemplo: asignación de subíndice

Aquí hay un ejemplo de una técnica que utilicé para ajustar datos en el caché del chip que tiene una utilidad de propósito general.

Tenía un vector de doble flotación que tenía 1.250 elementos de largo, que era una curva epidemiológica con colas muy largas. El "interesante" parte de la curva solo tenía alrededor de 200 valores únicos, pero no quería una prueba if () de 2 lados para ensuciar la tubería de la CPU (por lo tanto, las colas largas, que podrían usar como subíndices los valores más extremos del Monte Carlo escupiría el código), y necesitaba la lógica de predicción de bifurcación para una docena de otras pruebas condicionales dentro del '' punto caliente '' en el código.

Me decidí por un esquema en el que utilicé un vector de entradas de 8 bits como subíndice en el vector doble, que acorté a 256 elementos. Todas las pequeñas entradas tenían los mismos valores antes de 128 antes de cero, y 128 después de cero, por lo que, excepto los 256 valores medios, todos apuntaban al primer o último valor en el vector doble.

Esto redujo el requisito de almacenamiento a 2k para los dobles y 1,250 bytes para los subíndices de 8 bits. Esto redujo 10.000 bytes a 3.298. Como el programa pasó el 90% o más de su tiempo en este bucle interno, los 2 vectores nunca fueron expulsados ??del caché de datos de 8k. El programa inmediatamente duplicó su rendimiento. Este código fue alcanzado ~ 100 mil millones de veces en el proceso de calcular un valor de la OEA para más de 1 millón de préstamos hipotecarios.

Dado que las colas de la curva rara vez se tocaban, es muy posible que solo los elementos intermedios 200-300 del pequeño vector int se mantuvieran en caché, junto con 160-240 dobles intermedios que representan 1/8 de porcentajes de interés . Fue un aumento notable en el rendimiento, logrado en una tarde, en un programa que había pasado más de un año optimizando.

Estoy de acuerdo con Jerry, como también ha sido mi experiencia, que inclinar el código hacia la caché de instrucciones no es tan exitoso como optimizar la caché / s de datos. Esta es una razón por la que creo que los cachés comunes de AMD no son tan útiles como los cachés de datos e instrucciones separados de Intel. IE: no quieres instrucciones que acaparen el caché, ya que simplemente no es muy útil. En parte, esto se debe a que los conjuntos de instrucciones CISC se crearon originalmente para compensar la gran diferencia entre las velocidades de CPU y memoria, y a excepción de una aberración a fines de los años 80, eso es casi siempre cierto.

Otra técnica favorita que uso para favorecer la memoria caché de datos, y salvaguardar la memoria caché de instrucciones, es usar muchas entradas de bit en las definiciones de estructura y los tamaños de datos más pequeños posibles en general. Para enmascarar un int de 4 bits para contener el mes del año, o 9 bits para contener el día del año, etc., etc., requiere que la CPU use máscaras para enmascarar los enteros del host que usan los bits, lo que reduce el datos, efectivamente aumenta el tamaño de la caché y el bus, pero requiere más instrucciones. Si bien esta técnica produce código que no funciona tan bien en puntos de referencia sintéticos, en bu

Answer 5

Principalmente esto servirá como marcador de posición hasta que tenga tiempo para hacer justicia a este tema, pero quería compartir lo que considero un hito verdaderamente innovador: la introducción de instrucciones dedicadas de manipulación de bits en el nuevo microprocesador Intel Hazwell.

Se hizo dolorosamente obvio cuando escribí un código aquí en StackOverflow para revertir los bits en una matriz de 4096 bits que más de 30 años después de la introducción de la PC, los microprocesadores simplemente no dedican mucha atención o recursos a los bits, y eso Espero que cambie En particular, me encantaría ver, para empezar, que el tipo bool se convierte en un tipo de datos de bits real en C / C ++, en lugar del byte ridículamente despilfarrador que es actualmente.

ACTUALIZACIÓN: 29/12/2013

Recientemente tuve la oportunidad de optimizar un buffer de anillo que realiza un seguimiento de 512 demandas de usuarios de recursos diferentes en un sistema con granularidad de milisegundos. Hay un temporizador que dispara cada milisegundo que agrega la suma de las solicitudes de recursos del segmento más actual y resta las solicitudes del segmento número 1.000, que comprende las solicitudes de recursos que ahora tienen mil milisegundos de antigüedad.

Los vectores Head, Tail estaban uno al lado del otro en la memoria, excepto cuando primero el Head, y luego el Tail se envolvieron y comenzaron de nuevo al comienzo de la matriz. Sin embargo, el segmento Resumen (rodante) estaba en una matriz fija y estáticamente asignada que no estaba particularmente cerca de ninguno de esos, y ni siquiera estaba asignada desde el montón.

Pensando en esto, y estudiando el código, algunos detalles me llamaron la atención.

1. Las demandas que entraban se agregaron al Encabezado y al segmento Resumen al mismo tiempo, uno al lado del otro en líneas de código adyacentes.

2. Cuando se activó el temporizador, la cola se sustrajo del segmento Resumen y los resultados se dejaron en el segmento Resumen, como era de esperar

3. La segunda función llamada cuando el temporizador disparó avanzó todos los punteros al servicio del anillo. En particular.... La cabeza sobrescribió la cola, ocupando así la misma ubicación de memoria El nuevo Tail ocupó las siguientes 512 ubicaciones de memoria, o envolvió

4. El usuario quería más flexibilidad en la cantidad de demandas que se manejan, de 512 a 4098, o tal vez más. Sentí que la forma más robusta y a prueba de idiotas de hacer esto era asignar los 1,000 segmentos de tiempo y el segmento de resumen todos juntos como un bloque contiguo de memoria para que fuera IMPOSIBLE que el segmento de Resumen terminara en una longitud diferente que los otros 1,000 segmentos de tiempo.

5. Teniendo en cuenta lo anterior, comencé a preguntarme si podría obtener más rendimiento si, en lugar de que el segmento Resumen permaneciera en una ubicación, lo tuviera "deambular". entre la Cabeza y la Cola, por lo que siempre estaba justo al lado de la Cabeza para agregar nuevas demandas, y justo al lado de la Cola cuando se disparó el temporizador y los valores de la Cola tuvieron que restarse del Resumen.

Hice exactamente esto, pero luego encontré un par de optimizaciones adicionales en el proceso. Cambié el código que calculaba el Resumen continuo para que dejara los resultados en la Cola, en lugar del segmento Resumen. ¿Por qué? Porque la siguiente función era realizar un memcpy () para mover el segmento Resumen a la memoria que acaba de ocupar la Cola. (raro pero cierto, la cola lleva la cabeza hasta el final del anillo cuando se envuelve). Al dejar los resultados de la suma en la Cola, no tuve que realizar la memcpy (), solo tuve que asignar pTail a pSummary.

De manera similar, el nuevo Head ocupó la antigua ubicación de memoria del segmento Resumen ahora rancio, así que de nuevo, simplemente asigné pSummary a pHead y puse a cero todos sus valores con un memset a cero.

Liderando el camino hasta el final del ring (realmente un tambor, 512 pistas de ancho) estaba el Tail, pero yo o

Answer 6

La mayoría de los compiladores de C / C ++ prefieren optimizar el tamaño en lugar de la "velocidad". Es decir, el código más pequeño generalmente se ejecuta más rápido que el código desenrollado debido a los efectos de caché.

Answer 7

Si fuera usted, me aseguraría de saber qué partes del código son puntos calientes, que defino como

• un bucle cerrado que no contiene llamadas a funciones, porque si llama a alguna función, entonces la PC pasará la mayor parte de su tiempo en esa función,
• que representa una fracción significativa del tiempo de ejecución (como > = 10%) que puede determinar a partir de un generador de perfiles. (Acabo de probar la pila manualmente).

Si tiene ese punto de acceso, debería caber en el caché. No estoy seguro de cómo decirle que haga eso, pero sospecho que es automático.