c++ - ¿Qué es un código "amigable al caché"?

performance caching

Question

¿Cuál es la diferencia entre el " código hostil de la caché " y el código " amigable de la caché "?

¿Cómo puedo asegurarme de que escribo código eficiente en caché?

Answer 1

Preliminares

En las computadoras modernas, solo las estructuras de memoria de nivel más bajo (los registros ) pueden mover datos en ciclos de un solo reloj. Sin embargo, los registros son muy caros y la mayoría de los núcleos informáticos tienen menos de unas pocas docenas de registros (desde unos pocos cientos hasta un total de mil bytes ). En el otro extremo del espectro de memoria ( DRAM ), la memoria es muy barata (es decir, literalmente, millones de veces más barata ), pero requiere cientos de ciclos después de una solicitud para recibir los datos. Para salvar esta brecha entre lo súper rápido y lo costoso y lo súper lento y lo barato son las memorias caché , llamadas L1, L2, L3 en velocidad y costo decrecientes. La idea es que la mayoría del código de ejecución afectará a un pequeño conjunto de variables a menudo, y el resto (un conjunto mucho más grande de variables) con poca frecuencia. Si el procesador no puede encontrar los datos en la memoria caché L1, busca en la memoria caché L2. Si no está allí, entonces caché L3, y si no está allí, memoria principal. Cada uno de estos "fallos" es caro en el tiempo.

(La analogía es que la memoria caché es la memoria del sistema, ya que la memoria del sistema es para el almacenamiento en el disco duro. El almacenamiento en el disco duro es muy barato, pero muy lento).

El almacenamiento en caché es uno de los principales métodos para reducir el impacto de la latencia . Parafraseando a Herb Sutter (cfr. Enlaces a continuación): aumentar el ancho de banda es fácil, pero no podemos salir de la latencia .

Los datos siempre se recuperan a través de la jerarquía de memoria (menor == más rápido a más lento). Un hit / miss de caché por lo general se refiere a un hit / miss en el nivel más alto de caché en la CPU. Por nivel más alto, me refiero al mayor == más lento. La tasa de aciertos de la memoria caché es crucial para el rendimiento, ya que cada falta de memoria caché da como resultado la obtención de datos desde la RAM (o peor aún), lo que lleva mucho tiempo (cientos de ciclos para RAM, decenas de millones de ciclos para HDD). En comparación, la lectura de datos de la memoria caché (nivel más alto) generalmente toma solo unos pocos ciclos.

En las arquitecturas de computadoras modernas, el cuello de botella del rendimiento está dejando el dado de la CPU (por ejemplo, accediendo a la memoria RAM o superior). Esto solo empeorará con el tiempo. El aumento de la frecuencia del procesador ya no es relevante para aumentar el rendimiento. El problema es el acceso a la memoria. Los esfuerzos de diseño de hardware en las CPU, por lo tanto, se centran actualmente en la optimización de cachés, captación previa, canalizaciones y concurrencia. Por ejemplo, las CPU modernas gastan alrededor del 85% de las memorias caché y hasta el 99% para almacenar / mover datos.

Hay mucho que decir sobre el tema. Aquí hay algunas grandes referencias sobre cachés, jerarquías de memoria y programación adecuada:

• La página de Agner Fog . En sus excelentes documentos, puede encontrar ejemplos detallados que cubren idiomas que van desde ensamblaje hasta C ++.
• Si le gustan los videos, le recomiendo que eche un vistazo a la charla de Herb Sutter sobre la arquitectura de la máquina (youtube) (¡compruebe específicamente las 12:00 y las siguientes!)
• Diapositivas sobre la optimización de la memoria por Christer Ericson (director de tecnología @ Sony)
• Artículo de LWN.net " Lo que todo programador debe saber sobre la memoria "

Principales conceptos para el código de caché

Un aspecto muy importante del código compatible con el caché tiene que ver con el principio de localidad , cuyo objetivo es colocar los datos relacionados en la memoria para permitir un almacenamiento en caché eficiente. En términos de la memoria caché de la CPU, es importante conocer las líneas de la memoria caché para comprender cómo funciona esto: ¿Cómo funcionan las líneas de la memoria caché?

Los siguientes aspectos particulares son de gran importancia para optimizar el almacenamiento en caché:

1. Localidad temporal : cuando se accede a una ubicación de memoria determinada, es probable que se vuelva a acceder a la misma ubicación en un futuro próximo. Idealmente, esta información aún se almacenará en caché en ese punto.
2. Localidad espacial : se refiere a la colocación de datos relacionados entre sí. El almacenamiento en caché ocurre en muchos niveles, no solo en la CPU. Por ejemplo, cuando se lee de la memoria RAM, normalmente se obtiene una porción de memoria más grande de lo que se solicitó específicamente porque muy a menudo el programa requerirá esa información pronto. Los cachés HDD siguen la misma línea de pensamiento. Específicamente para cachés de CPU, la noción de líneas de caché es importante.

Use contenedores c ++ apropiados

Un ejemplo simple de amigable al caché versus hostil no amigable es el std::vector versus std::list c ++ . Los elementos de un std::vector se almacenan en una memoria contigua, y como tal, acceder a ellos es mucho más fácil de almacenar en caché que acceder a los elementos de una std::list , que almacena su contenido en todo el lugar. Esto se debe a la localidad espacial.

Bjarne Stroustrup da una muy buena ilustración de esto en este clip de youtube (¡gracias a @Mohammad Ali Baydoun por el enlace!).

No descuide el caché en la estructura de datos y el diseño de algoritmos

Siempre que sea posible, intente adaptar sus estructuras de datos y el orden de los cálculos de manera que permita el máximo uso de la memoria caché. Una técnica común en este sentido es el bloqueo de caché (versión Archive.org) , que es de suma importancia en la computación de alto rendimiento (cfr. Por ejemplo, ATLAS ).

Conocer y explotar la estructura implícita de los datos.

Otro ejemplo simple, que muchas personas en el campo a veces olvidan, es la columna principal (por ejemplo, fortran , matlab ) frente a la ordenación por filas principales (por ejemplo, c , c ++ ) para almacenar matrices bidimensionales. Por ejemplo, considere la siguiente matriz:

1 2
3 4

En la ordenación de filas principales, esto se almacena en la memoria como 1 2 3 4 ; en la orden de columna principal, esto se almacenaría como 1 3 2 4 . Es fácil ver que las implementaciones que no explotan este orden se encontrarán rápidamente en problemas de caché (¡fácilmente evitables!). Desafortunadamente, veo cosas como esta muy a menudo en mi dominio (aprendizaje automático). @MatteoItalia mostró este ejemplo con más detalle en su respuesta.

Al recuperar un determinado elemento de una matriz de la memoria, los elementos cercanos también se buscarán y se almacenarán en una línea de caché. Si se explota el ordenamiento, esto dará como resultado menos accesos a la memoria (porque los siguientes valores que se necesitan para los cálculos posteriores ya están en una línea de caché).

Para simplificar, supongamos que el caché comprende una sola línea de caché que puede contener 2 elementos de matriz y que cuando un elemento dado se recupera de la memoria, el siguiente también lo es. Digamos que queremos tomar la suma de todos los elementos en el ejemplo de matriz 2x2 anterior (llamémoslo M ):

Aprovechar el ordenamiento (por ejemplo, cambiar el índice de la columna primero en c ++ ):

M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses

No explotar el ordenamiento (por ejemplo, cambiar el índice de fila primero en c ++ ):

M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses

En este ejemplo simple, explotar el orden duplica aproximadamente la velocidad de ejecución (ya que el acceso a la memoria requiere muchos más ciclos que calcular las sumas). En la práctica, la diferencia de rendimiento puede ser mucho mayor.

Evita las ramas impredecibles.

Las tuberías y compiladores de características de arquitecturas modernas se están volviendo muy buenos para reordenar el código para minimizar los retrasos debidos al acceso a la memoria. Cuando su código crítico contiene ramas (impredecibles), es difícil o imposible obtener datos previamente. Esto conducirá indirectamente a más fallos de caché.

Esto se explica muy bien aquí (gracias a @ 0x90 por el enlace): ¿Por qué es más rápido procesar una matriz ordenada que una matriz sin clasificar?

Evitar funciones virtuales.

En el contexto de c ++ , virtual métodos virtual representan un tema controvertido con respecto a las fallas de caché (existe un consenso general de que deben evitarse cuando sea posible en términos de rendimiento). Las funciones virtuales pueden provocar fallas en la memoria caché durante la búsqueda, pero esto solo sucede si la función específica no se llama a menudo (de lo contrario, es probable que se almacene en caché), por lo que algunos consideran que no hay problema. Para obtener referencia sobre este problema, consulte: ¿Cuál es el costo de rendimiento de tener un método virtual en una clase de C ++?

Problemas comunes

Un problema común en las arquitecturas modernas con cachés multiprocesador se llama compartir falso . Esto ocurre cuando cada procesador individual está intentando usar datos en otra región de memoria e intenta almacenarlos en la misma línea de caché . Esto hace que la línea de caché, que contiene datos que otro procesador puede usar, se sobrescriba una y otra vez. Efectivamente, diferentes hilos se hacen esperar unos a otros al inducir errores de caché en esta situación. Vea también (gracias a @Matt por el enlace): ¿Cómo y cuándo alinearse con el tamaño de la línea de caché?

Un síntoma extremo de almacenamiento en caché deficiente en la memoria RAM (que probablemente no es lo que quiere decir en este contexto) es lo que se denomina thrashing . Esto ocurre cuando el proceso genera continuamente fallas en la página (por ejemplo, acceso a la memoria que no se encuentra en la página actual) que requieren acceso al disco.

Answer 2

Además de la respuesta de @Marc Claesen, creo que un ejemplo instructivo clásico de código antipático es el código que escanea una matriz bidimensional C (por ejemplo, una imagen de mapa de bits) en forma de columna en lugar de fila.

Los elementos adyacentes en una fila también están adyacentes en la memoria, por lo que acceder a ellos en secuencia significa acceder a ellos en orden ascendente de memoria; esto es compatible con la memoria caché, ya que la memoria caché tiende a captar previamente bloques de memoria contiguos.

En cambio, acceder a dichos elementos en forma de columna es hostil para la memoria caché, ya que los elementos en la misma columna están separados entre sí en la memoria (en particular, su distancia es igual al tamaño de la fila), por lo que cuando usa este patrón de acceso, están saltando en la memoria, potencialmente desperdiciando el esfuerzo del caché de recuperar los elementos cercanos en la memoria.

Y todo lo que se necesita para arruinar la actuación es ir desde

// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

a

// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

Este efecto puede ser bastante dramático (varios orden de magnitudes en velocidad) en sistemas con cachés pequeños y / o trabajar con matrices grandes (por ejemplo, más de 10 megapíxeles de imágenes de 24 bpp en las máquinas actuales); por esta razón, si tiene que hacer muchos escaneos verticales, a menudo es mejor rotar la imagen de 90 grados primero y luego realizar los diversos análisis, limitando el código hostil al caché solo a la rotación.

Answer 3

Bienvenido al mundo del diseño orientado a datos. El mantra básico es ordenar, eliminar sucursales, agrupar, eliminar llamadas virtual : todos los pasos hacia una mejor localidad.

Ya que marcó la pregunta con C ++, aquí está la típica mierda de C ++ obligatoria. Los errores de la programación orientada a objetos de Tony Albrecht también es una excelente introducción al tema.

Answer 4

Como @Marc Claesen mencionó que una de las formas de escribir código compatible con caché es explotar la estructura en la que se almacenan nuestros datos. Además de eso, otra forma de escribir código compatible con caché es: cambiar la forma en que se almacenan nuestros datos; luego escriba un nuevo código para acceder a los datos almacenados en esta nueva estructura.

Esto tiene sentido en el caso de cómo los sistemas de bases de datos linealizan las tuplas de una tabla y las almacenan. Hay dos formas básicas de almacenar las tuplas de una tabla, es decir, el almacén de filas y el almacén de columnas. En el almacén de filas, como su nombre indica, las tuplas se almacenan por filas. Supongamos que una tabla llamada Product se almacena tiene 3 atributos, es decir int32_t key, char name[56] y el int32_t price , por lo que el tamaño total de una tupla es de 64 bytes.

Podemos simular una ejecución de consulta de tienda de fila muy básica en la memoria principal mediante la creación de una matriz de Estructuras de Product con tamaño N, donde N es el número de filas en la tabla. Tal diseño de memoria también se llama matriz de estructuras. Así que la estructura para el producto puede ser como:

struct Product
{
   int32_t key;
   char name[56];
   int32_t price''
}

/* create an array of structs */
Product* table = new Product[N];
/* now load this array of structs, from a file etc. */

De manera similar, podemos simular una ejecución de consulta de almacén de columna muy básica en la memoria principal mediante la creación de 3 arreglos de tamaño N, un arreglo para cada atributo de la tabla Product . Tal diseño de memoria también se llama estructura de matrices. Así que las 3 matrices para cada atributo de Producto pueden ser como:

/* create separate arrays for each attribute */
int32_t* key = new int32_t[N];
char* name = new char[56*N];
int32_t* price = new int32_t[N];
/* now load these arrays, from a file etc. */

Ahora, después de cargar tanto la matriz de estructuras (Diseño de fila) como las 3 matrices separadas (Diseño de columna), tenemos el almacén de fila y el almacén de columna en nuestra tabla Product presente en nuestra memoria.

Ahora pasamos a la parte de código amigable de caché. Supongamos que la carga de trabajo en nuestra tabla es tal que tenemos una consulta de agregación en el atributo de precio. Como

SELECT SUM(price)
FROM PRODUCT

Para el almacén de filas podemos convertir la consulta SQL anterior en

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + table[i].price;

Para el almacén de columnas podemos convertir la consulta SQL anterior en

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + price[i];

El código para el almacén de columnas sería más rápido que el código para el diseño de la fila en esta consulta, ya que solo requiere un subconjunto de atributos y en el diseño de la columna lo estamos haciendo, es decir, solo accediendo a la columna de precios.

Supongamos que el tamaño de la línea de caché es de 64 bytes.

En el caso del diseño de filas cuando se lee una línea de caché, se lee el valor del precio de solo 1 ( cacheline_size/product_struct_size = 64/64 = 1 ), porque nuestra estructura tiene un tamaño de 64 bytes y llena toda nuestra línea de caché, por lo que para cada tupla se produce una falla de caché en el caso de un diseño de fila.

En el caso del diseño de columna cuando se lee una línea de caché, se lee el valor del precio de 16 ( cacheline_size/price_int_size = 64/4 = 16 ) tuplas, porque 16 valores de precios contiguos almacenados en la memoria se incorporan al caché, por lo que décimo sexto tupla un caché se pierda durante el diseño de la columna.

Por lo tanto, el diseño de la columna será más rápido en el caso de una consulta dada, y será más rápido en dichas consultas de agregación en un subconjunto de columnas de la tabla. Puede probar este experimento con los datos del TPC-H pruebas TPC-H y comparar los tiempos de ejecución de ambos diseños. El artículo de wikipedia sobre sistemas de bases de datos orientados a columnas también es bueno.

Por lo tanto, en los sistemas de bases de datos, si la carga de trabajo de consulta se conoce de antemano, podemos almacenar nuestros datos en diseños que se adapten a las consultas de carga de trabajo y acceder a los datos de estos diseños. En el caso del ejemplo anterior, creamos un diseño de columna y cambiamos nuestro código para calcular la suma, de modo que se convirtiera en compatible con la memoria caché.

Answer 5

Debe aclararse que no solo los datos deben ser compatibles con la memoria caché, sino que también son importantes para el código. Esto es además de la predicción de rama, la reordenación de instrucciones, evitando divisiones reales y otras técnicas.

Normalmente, cuanto más denso sea el código, menos líneas de caché se requerirán para almacenarlo. Esto hace que haya más líneas de caché disponibles para los datos.

El código no debe llamar a funciones en todo el lugar, ya que normalmente requieren una o más líneas de caché propias, lo que da como resultado menos líneas de caché para los datos.

Una función debe comenzar en una dirección fácil de alineación de línea de caché. Aunque existen (gcc) compiladores para esto, tenga en cuenta que si las funciones son muy cortas, podría ser inútil para cada uno ocupar una línea de caché completa. Por ejemplo, si tres de las funciones que se usan con más frecuencia se ajustan dentro de una línea de caché de 64 bytes, esto es menos desperdicio que si cada una tuviera su propia línea y resultara en dos líneas de caché menos disponibles para otros usos. Un valor de alineación típico podría ser 32 o 16.

Así que pasa un tiempo extra para hacer el código denso. Pruebe diferentes construcciones, compile y revise el tamaño del código generado y el perfil.

Answer 6

La optimización del uso del caché se reduce en gran medida a dos factores.

Localidad de Referencia

El primer factor (al que otros ya han aludido) es la localidad de referencia. Sin embargo, la localidad de referencia tiene dos dimensiones: espacio y tiempo.

• Espacial

La dimensión espacial también se reduce a dos cosas: primero, queremos empaquetar nuestra información densamente, por lo que más información cabrá en esa memoria limitada. Esto significa (por ejemplo) que necesita una mejora importante en la complejidad computacional para justificar estructuras de datos basadas en pequeños nodos unidos por punteros.

En segundo lugar, queremos que la información que se procesará en conjunto también se ubique en conjunto. Un caché típico funciona en "líneas", lo que significa que cuando accede a cierta información, otra información de direcciones cercanas se cargará en el caché con la parte que tocamos. Por ejemplo, cuando toco un byte, la memoria caché puede cargar 128 o 256 bytes cerca de ese. Para aprovechar eso, generalmente desea que los datos estén organizados para maximizar la probabilidad de que también utilice esos otros datos que se cargaron al mismo tiempo.

Por solo un ejemplo realmente trivial, esto puede significar que una búsqueda lineal puede ser mucho más competitiva con una búsqueda binaria de lo que cabría esperar. Una vez que haya cargado un elemento desde una línea de caché, usar el resto de los datos en esa línea de caché es casi gratis. Una búsqueda binaria se vuelve notablemente más rápida solo cuando los datos son lo suficientemente grandes como para que la búsqueda binaria reduzca el número de líneas de caché a las que accede.

• Hora

La dimensión de tiempo significa que cuando realiza algunas operaciones en algunos datos, desea (tanto como sea posible) realizar todas las operaciones en esos datos a la vez.

Ya que lo ha etiquetado como C ++, señalaré un ejemplo clásico de un diseño relativamente poco amigable para el caché: std::valarray . valarray sobrecarga la mayoría de los operadores aritméticos, por lo que puedo (por ejemplo) decir a = b + c + d; (donde a , b , d son todos conjuntos de valores) para hacer una adición de elementos de esos arreglos.

El problema con esto es que recorre un par de entradas, coloca los resultados en forma temporal, recorre otro par de entradas, etc. Con una gran cantidad de datos, el resultado de un cálculo puede desaparecer de la memoria caché antes de que se use en el siguiente cálculo, por lo que terminamos leyendo (y escribiendo) los datos varias veces antes de obtener nuestro resultado final. Si cada elemento del resultado final será algo como (a[n] + b[n]) * (c[n] + d[n]); En general, preferimos leer cada a[n] , b[n] , c[n] d[n] una vez, hacer el cálculo, escribir el resultado, incrementar n y repetir hasta que hayamos terminado. ²

Línea compartida

El segundo factor importante es evitar compartir la línea. Para entender esto, es probable que tengamos que hacer una copia de seguridad y observar un poco cómo se organizan los cachés. La forma más simple de caché es mapeado directo. Esto significa que una dirección en la memoria principal solo se puede almacenar en un punto específico en el caché. Si estamos usando dos elementos de datos que se asignan al mismo lugar en el caché, funciona mal: cada vez que usamos un elemento de datos, el otro debe ser borrado del caché para dejar espacio para el otro. El resto del caché puede estar vacío, pero esos elementos no usarán otras partes del caché.

Para evitar esto, la mayoría de las cachés son lo que se llama "conjunto asociativo". Por ejemplo, en un caché asociativo de conjuntos de 4 vías, cualquier elemento de la memoria principal se puede almacenar en cualquiera de los 4 lugares diferentes del caché. Entonces, cuando la memoria caché va a cargar un elemento, busca el elemento ³ menos usado recientemente entre esos cuatro, lo descarga a la memoria principal y carga el nuevo elemento en su lugar.

El problema es probablemente bastante obvio: para una memoria caché asignada directamente, dos operandos que se asignan a la misma ubicación de la memoria caché pueden provocar un mal comportamiento. Un caché asociativo de conjuntos en N aumenta el número de 2 a N + 1. Organizar una memoria caché en más "formas" requiere circuitos adicionales y generalmente se ejecuta más lentamente, por lo que (por ejemplo) una memoria caché asociativa con un conjunto de 8192 vías tampoco es una buena solución.

En última instancia, este factor es más difícil de controlar en el código portátil, sin embargo. Su control sobre dónde se colocan sus datos suele ser bastante limitado. Peor aún, la asignación exacta de la dirección al caché varía entre procesadores similares. Sin embargo, en algunos casos puede valer la pena hacer cosas como asignar un búfer grande y luego usar solo partes de lo que asignó para asegurarse de que no se compartan los datos en las mismas líneas de caché (aunque probablemente necesite detectar el procesador exacto y actuar en consecuencia para hacer esto).

• Compartir falso

Hay otro elemento relacionado llamado "compartir falso". Esto surge en un sistema multiprocesador o multinúcleo, donde dos (o más) procesadores / núcleos tienen datos que están separados, pero que caen en la misma línea de caché. Esto obliga a los dos procesadores / núcleos a coordinar su acceso a los datos, aunque cada uno tenga su propio elemento de datos independiente. Especialmente si los dos modifican los datos de forma alterna, esto puede llevar a una desaceleración masiva ya que los datos deben ser constantemente transportados entre los procesadores. Esto no se puede curar fácilmente organizando el caché en más "formas" o algo así tampoco. La principal forma de evitarlo es garantizar que dos subprocesos modifiquen raramente (preferiblemente nunca) los datos que podrían estar en la misma línea de caché (con las mismas advertencias sobre la dificultad de controlar las direcciones a las que se asignan los datos).

1. Aquellos que conocen bien C ++ podrían preguntarse si esto está abierto a la optimización a través de algo así como plantillas de expresión. Estoy bastante seguro de que la respuesta es que sí, podría hacerse y si lo fuera, probablemente sería una victoria bastante importante. Sin embargo, no estoy al tanto de que alguien lo haya hecho y, dado lo poco que se va a usar el valarray , me sorprendería al menos que alguien lo haga.

2. En el caso de que alguien se valarray cómo podría ser tan malo un valarray (diseñado específicamente para el rendimiento), se trata de una cosa: realmente fue diseñado para máquinas como la Crays más antigua, que usaba memoria principal rápida y no caché. Para ellos, este era realmente un diseño casi ideal.

3. Sí, estoy simplificando: la mayoría de las cachés no miden precisamente el elemento menos recientemente utilizado con precisión, pero utilizan cierta heurística que pretende estar cerca de eso sin tener que mantener una marca de tiempo completa para cada acceso.

Answer 7

Los procesadores de hoy trabajan con muchos niveles de áreas de memoria en cascada. Así que la CPU tendrá un montón de memoria que está en el chip de la CPU en sí. Tiene un acceso muy rápido a esta memoria. Hay diferentes niveles de caché cada uno de acceso más lento (y más grande) que el siguiente, hasta que llega a la memoria del sistema que no está en la CPU y el acceso es relativamente más lento.

Lógicamente, para el conjunto de instrucciones de la CPU, usted simplemente se refiere a las direcciones de memoria en un espacio de direcciones virtuales gigantes. Cuando acceda a una única dirección de memoria, la CPU irá a buscarla. en los viejos tiempos solo obtendría esa única dirección. Pero hoy, la CPU recuperará un montón de memoria alrededor del bit que solicitó y la copiará en el caché. Se asume que si usted solicitó una dirección particular, es muy probable que vaya a solicitar una dirección cercana muy pronto. Por ejemplo, si estuviera copiando un búfer, leería y escribiría de direcciones consecutivas, una justo después de la otra.

Así que hoy, cuando recupera una dirección, comprueba el primer nivel de caché para ver si ya ha leído esa dirección en el caché, si no la encuentra, entonces se trata de una falta de caché y tiene que pasar al siguiente nivel de caché para encontrarlo, hasta que finalmente tenga que salir a la memoria principal.

El código compatible con la memoria caché trata de mantener los accesos juntos en la memoria para minimizar los errores de la memoria caché.

Entonces, un ejemplo sería imaginar que desea copiar una tabla gigante de 2 dimensiones. Está organizado con una fila de alcance consecutiva en la memoria, y una fila sigue a la siguiente a la derecha.

Si copia los elementos una fila a la vez de izquierda a derecha, sería fácil de almacenar en caché. Si decidiera copiar la tabla una columna a la vez, copiaría exactamente la misma cantidad de memoria, pero sería un caché hostil.

Answer 8

Simplemente acumulándose: el ejemplo clásico de código antipático frente a amigable con el caché es el "bloqueo de caché" de la matriz multiplicada.

Matriz ingenua multiplica se parece a

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k==;k<N;i++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

Si N es grande, por ejemplo, si N * sizeof(elemType) es mayor que el tamaño del caché, entonces cada acceso único a src2[k][j] será un error de caché.

Hay muchas formas diferentes de optimizar esto para un caché. Este es un ejemplo muy simple: en lugar de leer un elemento por línea de caché en el bucle interno, use todos los elementos:

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k==;k<N;i++) {
         for(jj=0;jj<itemsPerCacheLine; jj+) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}

Si el tamaño de la línea de caché es de 64 bytes, y estamos operando en flotantes de 32 bits (4 bytes), entonces hay 16 elementos por línea de caché. Y el número de fallas de caché a través de esta simple transformación se reduce aproximadamente 16 veces.

Las transformaciones más avanzadas operan en mosaicos 2D, se optimizan para múltiples cachés (L1, L2, TLB), etc.

Algunos resultados de googlear "bloqueo de caché":

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

Una buena animación de vídeo de un algoritmo de bloqueo de caché optimizado.

http://www.youtube.com/watch?v=IFWgwGMMrh0

La colocación de bucles está muy relacionada:

http://en.wikipedia.org/wiki/Loop_tiling

Answer 9

Tenga en cuenta que las memorias caché no solo almacenan en caché la memoria continua. Tienen varias líneas (al menos 4), por lo que la memoria discontinua y superpuesta a menudo se puede almacenar con la misma eficiencia.

Lo que falta en todos los ejemplos anteriores son los puntos de referencia medidos. Hay muchos mitos sobre el rendimiento. A menos que lo midas no lo sabes. No complique su código a menos que tenga una mejora medida .