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

Question

Al escribir 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 por lo que cualquier ganancia de rendimiento/optimización es un gran beneficio.

Si conoce algún buen enlace 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, realmente no se puede especificar mucho sobre el uso de la memoria caché. Sin embargo, aún puedes intentar escribir un código de caché. Por el lado del código, esto a menudo significa que los bucles de desenrollado (solo por un ejemplo obvio) raramente son útiles: expande el código, y una CPU moderna normalmente minimiza la sobrecarga de los bucles. En general, puede hacer más por el lado de los datos, para mejorar la localidad de referencia, proteger contra el uso compartido falso (por ejemplo, dos datos de uso frecuente que intentarán usar la misma parte del caché, mientras que otras partes no se utilizarán).

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

Una CPU típico tiene un número de diferentes cachés. 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í (nivel 2 es siguiente, nivel 3 después de eso, etc.)

In 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é tanto para instrucciones como para datos). -pero es tan completamente obsoleto que probablemente no merezca una gran cantidad de pensamiento).

En la mayoría de los casos, un caché está organizado como un conjunto de "líneas". El contenido de un caché normalmente se lee, escribe y 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é, toda esa línea de caché se lee desde el siguiente nivel de almacenamiento más bajo. Las cachés que están más cerca de la CPU generalmente son más pequeñas 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 el caché una vez, hacer todo lo que esté a mano 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 suficientemente pequeños como para caber en la memoria caché), hacer todo el procesamiento de esos datos como sea posible, luego pasar a el siguiente fragmento de datos. Algoritmos como Quicksort que rápidamente rompen grandes cantidades de entrada en piezas progresivamente más pequeñas hacen esto de forma más o menos automática, por lo que tienden a ser bastante compatibles con el caché, casi independientemente de los detalles precisos de la memoria caché.

Esto también tiene implicaciones para la forma de escribir el código. Si usted tiene un bucle como:

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

Usted es generalmente mejor encadenar ya que muchos de los pasos juntos como se puede hasta la cantidad que quepa en la memoria caché. En el momento en que desborda el caché, el rendimiento puede/disminuirá drásticamente.Si el código del paso 3 anterior era lo suficientemente grande que no caben en la memoria caché, tendría por lo general será mejor interrumpir el circuito en dos piezas como esto (si es posible):

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

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

Loop desenrollar es un tema bastante disputado. Por un lado, puede conducir a un código que es mucho más amigable con la CPU, reduciendo la sobrecarga de las instrucciones ejecutadas para el bucle en sí. Al mismo tiempo, puede (y generalmente lo hace) aumentar el tamaño del código, por lo que es relativamente poco amigable con el caché. Mi propia experiencia es que en los puntos de referencia sintéticos que tienden a hacer cantidades realmente pequeñas de procesamiento en cantidades de datos realmente grandes, se gana mucho con el despliegue de bucles. En un código más práctico en el que tiende a tener más procesamiento en una pieza individual de datos, gana mucho menos, y el desbordamiento de la memoria caché que conduce a una pérdida de rendimiento grave no es particularmente raro en absoluto.

La memoria caché de datos también tiene un tamaño limitado. Esto significa que generalmente desea que sus datos estén empaquetados de la manera más densa posible, de modo que la mayor cantidad posible de datos encajará en la caché. Solo por un ejemplo obvio, una estructura de datos que está vinculada junto con punteros necesita ganar bastante en términos de complejidad computacional para compensar la cantidad de espacio de caché de datos utilizado por esos punteros. Si va a utilizar una estructura de datos vinculada, generalmente quiere al menos asegurarse de que está vinculando datos relativamente grandes.

En muchos casos, sin embargo, he encontrado que originalmente trucos que aprendí de ajuste de datos en una minúscula cantidad de memoria en diminutos procesadores que han sido (en su mayoría) obsoleto desde hace décadas, funciona bastante bien en los procesadores modernos. La intención ahora es incluir más datos en la memoria caché en lugar de la memoria principal, pero el efecto es casi el mismo. En algunos casos, puede pensar que las instrucciones de la CPU son casi gratuitas, y la velocidad de ejecución general se rige por el ancho de banda de la memoria caché (o la memoria principal), por lo que el procesamiento extra para descomprimir datos de un formato denso se resuelve en su favor. Esto es particularmente cierto cuando se trata de datos suficientes que ya no encajarán en la memoria caché, por lo que la velocidad general se rige por el ancho de banda de la memoria principal. En este caso, puede ejecutar un lote de instrucciones para guardar algunas lecturas de memoria y seguir adelante.

El procesamiento en paralelo puede agravar ese problema. En muchos casos, la reescritura del código para permitir el procesamiento en paralelo puede llevar virtualmente a ninguna ganancia en el rendimiento, o incluso a una pérdida de rendimiento. Si la velocidad total se rige por el ancho de banda de la CPU a la memoria, es improbable que tener más núcleos compitiendo por ese ancho de banda sirva para nada (y puede causar un daño sustancial). En tal caso, el uso de múltiples núcleos para mejorar la velocidad a menudo se reduce a hacer aún más para empaquetar los datos con mayor certeza y aprovechar aún más la potencia de procesamiento para descomprimir los datos, por lo que la ganancia de velocidad real es reducir el ancho de banda consumido , y los núcleos extra solo evitan perder tiempo para desempacar los datos del formato más denso.

Otro problema basado en caché que puede surgir en la codificación paralela es compartir (y compartir falsamente) las variables. Si dos (o más) núcleos necesitan escribir en la misma ubicación en la memoria, la línea de caché que contiene esos datos puede terminar yendo y viniendo entre los núcleos para dar a cada núcleo acceso a los datos compartidos. El resultado a menudo es un código que corre más lento en paralelo que en serie (es decir, en un solo núcleo). Hay una variación de esto llamada "uso compartido falso", en la cual el código en los diferentes núcleos está escribiendo en datos separados, pero los datos para los diferentes núcleos terminan en la misma línea de caché. Dado que el caché controla los datos puramente en términos de líneas enteras de datos, los datos se mezclan entre los núcleos de todos modos, lo que lleva exactamente al mismo problema.

Answer 2

Si yo fuera tú, me aseguraría de que sé qué partes del código son puntos de acceso, que yo defino como

• un bucle estrecho que no contiene ninguna llamada de función, ya que si se llama a cualquier función, entonces el PC pasará la mayor parte de su tiempo en esa función,
• que da cuenta de una fracción significativa de tiempo de ejecución (como> = 10%), que se puede determinar a partir de un generador de perfiles. (Solo muestro la pila manualmente.)

Si tiene un punto de acceso así, debe caber en la memoria caché. No estoy seguro de cómo le dices que haga eso, pero sospecho que es automático.

Answer 3

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

Answer 4

compiladores más C/C++ prefieren para optimizar el tamaño más que por 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 5

un documento útil que le dirá más de lo que siempre quiso saber sobre cachés es What Every Programmer Should Know About Memory de Ulrich Drepper. Hennessey lo cubre muy bien. Christer y Mike Acton también han escrito un montón de cosas buenas sobre esto.

Creo que debería preocuparse más por la memoria caché de datos que la caché de instrucciones — en mi experiencia, las fallas de caché son más frecuentes, más dolorosas y más bien corregidas.

Answer 6

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 invertir 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 que espero que cambie En particular, me gustaría ver, para empezar, que el tipo bool se convierte en un tipo de datos real en C/C++, en lugar del byte ridículamente inútil que es actualmente.

ACTUALIZACIÓN: 12/29/2013

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

la cabeza, vectores de cola fueron uno al lado del otro en la memoria, excepto cuando primero la cabeza, y luego la cola envuelta y comenzó de nuevo al comienzo de la matriz. Sin embargo, el segmento de resumen (continuo) estaba en una matriz fija, asignada estáticamente, que no estaba particularmente cerca de ninguna de ellas, y ni siquiera se asignó desde el montón.

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

1. Las exigencias que venían en se añadieron a la cabeza y la rebanada Resumen al mismo tiempo, a la derecha junto a la otra en líneas adyacentes de código.

2. Cuando el tiempo se disparó, la cola se restó de la rebanada Resumen, y los resultados fueron dejados en el Resumen de los sectores, como era de esperar

3. La segunda función llamada cuando el temporizador disparado todas avanzada los indicadores que sirven el anillo. En particular .... El Jefe sobreescribí la cola, ocupando de esta manera la misma posición de memoria La nueva cola ocupada los próximos 512 posiciones de memoria, o envueltos

4. El usuario quería más flexibilidad en el número de demandas está gestionando, de 512 a 4098, o tal vez más. Sentí que la forma más robusta e irresistible de hacer esto era asignar tanto los 1000 segmentos de tiempo como el resumen como un bloque contiguo de memoria, de modo que IMPOSIBLE para el resumen fuera una longitud diferente. que las otras 1,000 rebanadas de tiempo.

5. Dado lo anterior, comencé a preguntarme si podría obtener más rendimiento si, en lugar de tener la sección Resumen permanezca en una ubicación, lo tenía "deambulando" entre la Cabeza y la Cola, por lo que siempre era correcto al lado del Jefe para agregar nuevas demandas, y justo al lado de la Cola cuando el temporizador se disparó y los valores de la Cola tuvieron que ser restados del Resumen.

Hice exactamente esto, pero luego encontré un par de optimizaciones adicionales en el proceso. Cambié el código que calculó el Resumen sucesivo para que dejara los resultados en la cola, en lugar del resumen. ¿Por qué? Debido a que la siguiente función estaba realizando un memcpy() para mover el segmento Resumen en la memoria que acaba de ocupar la cola. (extraño 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, la nueva Cabecera ocupó la antigua ubicación de la memoria del sector Resumen ahora obsoleto, así que de nuevo, acabo de asignar pSummary a pHead, y cero todos sus valores con un memset a cero.

Encabezando el camino hasta el final del anillo (realmente un tambor, 512 pistas de ancho) era la cola, pero solo tuve que comparar su puntero contra un puntero pEndOfRing constante para detectar esa condición. A todos los demás punteros se les podría asignar el valor de puntero del vector justo delante de él. IE: Solo necesitaba una prueba condicional para 1: 3 de los punteros para envolverlos correctamente.

El diseño inicial se había utilizado enteros byte para maximizar el uso de la caché, sin embargo, yo era capaz de relajar esta restricción - la satisfacción de los usuarios solicitan para manejar los recuentos más altos de recursos por usuario por milisegundo - uso de pantalones cortos sin signo y todavía doble de rendimiento , porque incluso con 3 vectores adyacentes de 512 pantalones cortos sin signo, caché de datos 32K de la memoria caché L1 fácilmente podrían mantener las requeridas 3.720 bytes, 2/3rds de los cuales fueron en lugares simplemente utilizados. Solo cuando Tail, Summary o Head envuelto fueron 1 de los 3 separados por cualquier "paso" significativo en el 8MB L3cache.

El espacio total de memoria de tiempo de ejecución para este código es inferior a 2 MB, por lo que se ejecuta completamente fuera de cachés en chip, e incluso en un chip i7 con 4 núcleos, 4 instancias de este proceso se pueden ejecutar sin degradación en cuanto a rendimiento, y el rendimiento total aumenta ligeramente con 5 procesos en ejecución. Es un Opus Magnum en el uso de la memoria caché.

Answer 7

ACTUALIZACIÓN: 13/01/2014 De acuerdo con este diseñador de chips de alto nivel, fallos de caché es ahora el factor de forma aplastante dominante en el rendimiento del código, así que estamos básicamente todo el camino de vuelta a mediados de los años 80 y rápida 286 chips en términos de los cuellos de botella de rendimiento relativo de carga, almacenamiento, aritmética de enteros y errores de caché.

A Crash Course In Modern Hardware by Cliff Click @ Azul . . . . .

--- ahora que vuelva a su programa regular ---

veces, un ejemplo es mejor que una descripción de cómo hacer algo. Con ese espíritu, este es un ejemplo particularmente exitoso de cómo cambié algunos códigos para usarlos mejor en cachés de chips. Esto se hizo hace un tiempo en una CPU 486 y luego migró a una CPU Pentium de 1ra generación. El efecto en el rendimiento fue similar.

Ejemplo: Subíndice Mapping

Aquí está un ejemplo de una técnica que utiliza para ajustar los datos en la memoria caché del chip que tiene utilidad de propósito general.

Tenía un doble vector flotante que tenía 1.250 elementos de longitud, que era una curva de epidemiología con colas muy largas. La parte "interesante" de la curva solo tenía unos 200 valores únicos, pero no quería una prueba if() de dos lados para hacer un lío de la tubería de la CPU (por lo tanto, las colas largas, que podrían usar como subíndices los más extremos valores que el código de Monte Carlo escupiría), 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 8 bits como subíndice en el vector doble, que acorté a 256 elementos. Todas las minúsculas tenían los mismos valores antes de 128 delante de cero y de 128 después de cero, por lo que a excepción de los valores medios de 256, todos señalaron el primer o el ú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 encogió 10,000 bytes hasta 3.298. Como el programa gastó el 90% o más de su tiempo en este bucle interno, los 2 vectores nunca se expulsaron de la memoria caché de datos de 8k. El programa duplicó inmediatamente su rendimiento. Este código recibió aproximadamente 100 mil millones de veces en el proceso de cálculo de un valor de la OEA para más de 1 millón de préstamos hipotecarios.

Dado que las colas de la curva fueron rara vez tocado, es muy posible que sólo el medio 200-300 elementos de la pequeña vector int eran en realidad mantienen en la memoria caché, junto con 160-240 medio de dobles que representa 1/8ths de porcentajes de interesar. 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, ya que también es mi experiencia, que inclinar el código hacia la memoria caché de instrucciones no es tan exitoso como optimizar la memoria caché 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 la CPU y la velocidad de la memoria, y a excepción de una aberración a finales de los 80, eso siempre ha sido cierto.

Otra técnica favorita que utilizo para favorecer la memoria caché de datos, y salvaje la caché de instrucciones, es mediante el uso de una gran cantidad de bits 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., se requiere que las máscaras de uso de CPU oculten los enteros del host que utilizan los bits, lo que reduce el tamaño datos, aumenta efectivamente los tamaños de caché y bus, pero requiere más instrucciones. Si bien esta técnica produce código que no funciona tan bien en los puntos de referencia sintéticos, en los sistemas ocupados donde los usuarios y los procesos compiten por los recursos, funciona maravillosamente.