tipos sirve que para mis memoria informatica fotos definicion caracteristicas caché cache bueno borro borrar borran caching performance cpu-cache

caching - sirve - si borro la memoria cache se borran mis fotos



¿Cómo se escribe el código que mejor utiliza la memoria caché de la CPU para mejorar el rendimiento? (15)

Además de alinear su estructura y sus campos, si su estructura es asignada, puede usar asignadores que admitan asignaciones alineadas; como _aligned_malloc (sizeof (DATA), SYSTEM_CACHE_LINE_SIZE); de lo contrario, puede tener un intercambio aleatorio falso; recuerde que en Windows, el montón predeterminado tiene una alineación de 16 bytes.

Esto podría parecer una pregunta subjetiva, pero lo que estoy buscando son instancias específicas, que podría haber encontrado relacionadas con esto.

  1. ¿Cómo hacer que el código, la memoria caché sea eficaz / compatible con la caché (más éxitos de caché, el menor número de errores de caché posible)? Desde ambas perspectivas, la caché de datos y la memoria caché del programa (caché de instrucciones), es decir, qué cosas en el código, relacionadas con las estructuras de datos y las construcciones de código, deberíamos tener en cuenta para que la caché sea efectiva.

  2. ¿Hay alguna estructura de datos particular que uno debe usar / evitar, o hay una manera particular de acceder a los miembros de esa estructura, etc. ... para hacer efectiva la caché de códigos?

  3. ¿Hay alguna construcción de programa (if, for, switch, break, goto, ...), flujo de código (para dentro de if, if inside a for, etc ...) que uno debe seguir / evitar en este asunto?

Tengo muchas ganas de escuchar experiencias individuales relacionadas con la elaboración de un código de caché eficiente en general. Puede ser cualquier lenguaje de programación (C, C ++, Assembly, ...), cualquier destino de hardware (ARM, Intel, PowerPC, ...), cualquier sistema operativo (Windows, Linux, S ymbian, ...), etc. .

La variedad ayudará a comprender mejor profundamente.

Además de los patrones de acceso a los datos, un factor importante en el código de memoria caché es el tamaño de los datos. Menos datos significa que encaja más en la memoria caché.

Esto es principalmente un factor con estructuras de datos alineadas con la memoria. La sabiduría "convencional" dice que las estructuras de datos deben alinearse en los límites de las palabras porque la CPU solo puede acceder a palabras completas, y si una palabra contiene más de un valor, debe hacer un trabajo extra (leer-modificar-escribir en lugar de una escritura simple) . Pero los caches pueden invalidar por completo este argumento.

De manera similar, una matriz booleana de Java usa un byte completo para cada valor para permitir operar en valores individuales directamente. Puede reducir el tamaño de datos en un factor de 8 si usa bits reales, pero luego el acceso a valores individuales se vuelve mucho más complejo, requiriendo operaciones de cambio de bit y máscara (la clase BitSet hace por usted). Sin embargo, debido a los efectos de caché, esto puede ser considerablemente más rápido que usar un booleano [] cuando la matriz es grande. IIRC Una vez logré una aceleración por un factor de 2 o 3 de esta manera.

Escribe tu programa para tomar un tamaño mínimo. Es por eso que no siempre es una buena idea usar optimizaciones -O3 para GCC. Toma un tamaño más grande. A menudo, -Os es tan bueno como -O2. Sin embargo, todo depende del procesador utilizado. YMMV.

Trabaja con pequeños trozos de datos a la vez. Es por eso que los algoritmos de clasificación menos eficientes pueden ejecutarse más rápido que el quicksort si el conjunto de datos es grande. Encuentre maneras de dividir sus conjuntos de datos más grandes en conjuntos más pequeños. Otros han sugerido esto.

Para ayudarlo a aprovechar mejor la localidad temporal / espacial de la instrucción, le recomendamos que estudie cómo se convierte el código en ensamblado. Por ejemplo:

for(i = 0; i < MAX; ++i) for(i = MAX; i > 0; --i)

Los dos bucles producen códigos diferentes a pesar de que se limitan a analizar a través de una matriz. En cualquier caso, tu pregunta es muy específica de la arquitectura. Por lo tanto, su única forma de controlar estrictamente el uso de la memoria caché es comprender cómo funciona el hardware y optimizar su código para ello.

Ha habido muchas respuestas en consejos generales como selección de estructura de datos, patrón de acceso, etc. Aquí me gustaría agregar otro patrón de diseño de código llamado canalización de software que hace uso de la administración de memoria caché activa.

La idea se toma prestada de otras técnicas de canalización, por ejemplo, la canalización de instrucciones de CPU.

Este tipo de patrón se aplica mejor a procedimientos que

  1. podría desglosarse en subpasos múltiples razonables, S [1], S [2], S [3], ... cuyo tiempo de ejecución es más o menos comparable con el tiempo de acceso a la RAM (~ 60-70ns).
  2. toma un lote de entrada y realiza los pasos múltiples antes mencionados para obtener un resultado.

Tomemos un caso simple donde solo hay un sub-procedimiento. Normalmente, al código le gustaría:

def proc(input): return sub-step(input))

Para tener un mejor rendimiento, es posible que desee pasar múltiples entradas a la función en un lote para que amortice la sobrecarga de llamada de función y también aumente la localidad de caché de código.

def batch_proc(inputs): results = [] for i in inputs: // avoids code cache miss, but still suffer data(inputs) miss results.append(sub-step(i)) return res

Sin embargo, como se dijo anteriormente, si la ejecución del paso es más o menos la misma que la hora de acceso a la RAM, puede mejorar aún más el código a algo como esto:

def batch_pipelined_proc(inputs): for i in range(0, len(inputs)-1): prefetch(inputs[i+1]) # work on current item while [i+1] is flying back from RAM results.append(sub-step(inputs[i-1])) results.append(sub-step(inputs[-1]))

El flujo de ejecución se vería así:

  1. captación previa (1) solicite a la CPU que capte previamente la entrada [1] en la memoria caché, donde la instrucción de captación previa toma el valor de P para ciclar y regresar, y en el fondo la entrada [1] llegaría a la caché después de R ciclos.
  2. works_on (0) cold miss en 0 y funciona en él, que toma M
  3. captación previa (2) emitir otra captura
  4. works_on (1) si P + R <= M, entonces las entradas [1] deberían estar en la memoria caché ya antes de este paso, así evitará que se pierda un caché de datos
  5. works_on (2) ...

Podría haber más pasos involucrados, entonces usted puede diseñar un pipeline de etapas múltiples, siempre que el tiempo de los pasos y la latencia de acceso a la memoria coincidan, usted sufriría un pequeño error en la caché de código / datos. Sin embargo, este proceso debe ajustarse con muchos experimentos para encontrar la agrupación correcta de pasos y el tiempo de captación previa. Debido a su esfuerzo requerido, ve una mayor adopción en el procesamiento de flujo de datos / paquetes de alto rendimiento. Se puede encontrar un buen ejemplo de código de producción en DPDK QoS Enqueue pipeline design: http://dpdk.org/doc/guides/prog_guide/qos_framework.html Capítulo 21.2.4.3. Enqueue Pipeline.

Se puede encontrar más información:

https://software.intel.com/en-us/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and

http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf

La caché está ahí para reducir el número de veces que la CPU se pararía esperando que se cumpliera una solicitud de memoria (evitando la latencia de memoria) y como un segundo efecto, posiblemente para reducir la cantidad total de datos que se debe transferir (preservando ancho de banda de memoria).

Las técnicas para evitar el sufrimiento de la latencia de recuperación de la memoria suelen ser lo primero que se debe tener en cuenta y, a veces, ayudan mucho. El ancho de banda de memoria limitado también es un factor limitante, particularmente para aplicaciones multinúcleo y multiproceso donde muchos hilos desean usar el bus de memoria. Un conjunto diferente de técnicas ayuda a abordar el último problema.

La mejora de la localidad espacial significa que se asegura de que cada línea de caché se utilice por completo una vez que se haya asignado a un caché. Cuando hemos analizado varios puntos de referencia estándar, hemos visto que una gran fracción sorprendente de ellos no puede usar el 100% de las líneas de caché obtenidas antes de que se desalojen las líneas de caché.

Mejorar la utilización de la línea de caché ayuda en tres aspectos:

  • Tiende a encajar datos más útiles en la memoria caché, lo que aumenta esencialmente el tamaño efectivo de la memoria caché.
  • Tiende a incluir datos más útiles en la misma línea de caché, lo que aumenta la probabilidad de que los datos solicitados se encuentren en la caché.
  • Reduce los requisitos de ancho de banda de memoria, ya que habrá menos recuperaciones.

Las técnicas comunes son:

  • Usa tipos de datos más pequeños
  • Organice sus datos para evitar agujeros de alineación (clasificar los miembros de su estructura disminuyendo el tamaño de una forma)
  • Tenga cuidado con el asignador de memoria dinámica estándar, que puede introducir agujeros y difundir sus datos en la memoria a medida que se calienta.
  • Asegúrese de que todos los datos adyacentes se utilicen realmente en los bucles calientes. De lo contrario, considere dividir las estructuras de datos en componentes calientes y fríos, de modo que los bucles calientes usen datos calientes.
  • evite algoritmos y estructuras de datos que muestren patrones de acceso irregulares y favorezca las estructuras de datos lineales.

También debemos tener en cuenta que hay otras maneras de ocultar la latencia de la memoria que el uso de cachés.

CPU moderna: a menudo tiene uno o más precapitores de hardware . Se entrenan en las fallas de un caché y tratan de detectar las regularidades. Por ejemplo, después de algunas fallas en las líneas de caché subsiguientes, el prefetcher hw comenzará a buscar líneas de caché en el caché, anticipando las necesidades de la aplicación. Si tiene un patrón de acceso regular, el prefetcher de hardware generalmente está haciendo un muy buen trabajo. Y si su programa no muestra patrones de acceso regulares, puede mejorar las cosas al agregar instrucciones de captación previa .

Al reagrupar las instrucciones de tal manera que aquellas que siempre fallan en el caché se producen cerca una de la otra, la CPU a veces puede superponer estas recuperaciones para que la aplicación solo soporte un golpe de latencia ( paralelismo del nivel de memoria ).

Para reducir la presión general del bus de memoria, debe comenzar a dirigirse a lo que se denomina localidad temporal . Esto significa que debe reutilizar los datos mientras aún no se ha desalojado del caché.

Fusionar bucles que tocan los mismos datos ( fusión de bucle ) y emplear técnicas de reescritura conocidas como embaldosado o bloqueo, todos se esfuerzan por evitar esas recuperaciones de memoria adicionales.

Si bien hay algunas reglas generales para este ejercicio de reescritura, normalmente debe considerar cuidadosamente las dependencias de datos transportados por bucle, para asegurarse de no afectar la semántica del programa.

Estas cosas son lo que realmente vale la pena en el mundo multinúcleo, donde normalmente no verá gran parte de las mejoras de rendimiento después de agregar el segundo hilo.

La estructura de datos más efectiva para un caché es una matriz. Las cachés funcionan mejor si su estructura de datos se distribuye de forma secuencial, ya que las CPU leen líneas enteras de caché (generalmente 32 bytes o más) a la vez desde la memoria principal.

Cualquier algoritmo que acceda a la memoria en orden aleatorio arruina las cachés porque siempre necesita nuevas líneas de caché para acomodar la memoria a la que se accede de forma aleatoria. Por otro lado, un algoritmo que se ejecuta secuencialmente a través de una matriz es mejor porque:

  1. Le da a la CPU la posibilidad de leer por adelantado, por ejemplo, poner especulativamente más memoria en la caché, a la que se accederá más adelante. Esta lectura anticipada brinda un gran impulso al rendimiento.

  2. Ejecutar un ciclo cerrado en una matriz grande también permite que la CPU guarde en caché el código que se ejecuta en el ciclo y en la mayoría de los casos le permite ejecutar un algoritmo completamente desde la memoria caché sin tener que bloquear el acceso a la memoria externa.

La memoria caché se organiza en "líneas de caché" y la memoria (real) se lee y se escribe en fragmentos de este tamaño.

Las estructuras de datos que están contenidas dentro de una única línea de caché son, por lo tanto, más eficientes.

Del mismo modo, los algoritmos que acceden a bloques de memoria contiguos serán más eficientes que los algoritmos que saltan a través de la memoria en un orden aleatorio.

Lamentablemente, el tamaño de la línea de caché varía drásticamente entre los procesadores, por lo que no hay forma de garantizar que una estructura de datos que sea óptima en un procesador sea eficiente en cualquier otro.

Las reglas básicas son realmente bastante simples. Donde se pone complicado es en cómo se aplican a su código.

El caché funciona en dos principios: localidad temporal y localidad espacial. La primera es la idea de que si recientemente usó una cierta cantidad de datos, probablemente la necesitará nuevamente pronto. Esto último significa que si usó recientemente los datos en la dirección X, es probable que pronto necesite la dirección X + 1.

El caché intenta acomodar esto al recordar los fragmentos de datos utilizados más recientemente. Funciona con líneas de caché, generalmente de 128 bytes, por lo que incluso si solo necesita un solo byte, toda la línea de caché que lo contiene se ingresa en el caché. Entonces, si necesita el siguiente byte después, ya estará en la memoria caché.

Y esto significa que siempre querrá su propio código para explotar estas dos formas de localidad tanto como sea posible. No salte toda la memoria. Haz todo el trabajo que puedas en un área pequeña y luego pasa al siguiente y haz todo el trabajo que puedas.

Un ejemplo simple es el recorrido de la matriz 2D que mostró la respuesta de 1800. Si lo recorre una fila a la vez, está leyendo la memoria secuencialmente. Si lo hace en columnas, leerá una entrada, luego saltará a una ubicación completamente diferente (el comienzo de la siguiente fila), leerá una entrada y saltará de nuevo. Y cuando finalmente regrese a la primera fila, ya no estará en la memoria caché.

Lo mismo aplica al código. Saltos o ramas significa un uso de memoria caché menos eficiente (porque no estás leyendo las instrucciones secuencialmente, sino saltando a una dirección diferente). Por supuesto, los pequeños enunciados if probablemente no cambien nada (solo se salta unos pocos bytes, por lo que aún terminarás dentro de la región en caché), pero las llamadas a funciones típicamente implican que estás saltando a un nivel completamente diferente. dirección que puede no estar en la memoria caché. A menos que se haya llamado recientemente.

El uso de la memoria caché de instrucciones suele ser un problema menor. Lo que generalmente necesita preocuparse es el caché de datos.

En una estructura o clase, todos los miembros se disponen contiguamente, lo cual es bueno. En una matriz, todas las entradas se disponen contiguamente también. En las listas enlazadas, cada nodo se asigna a una ubicación completamente diferente, lo que es malo. Los punteros, en general, tienden a apuntar a direcciones no relacionadas, lo que probablemente dará como resultado una falta de caché si la desreferencia.

Y si desea explotar múltiples núcleos, puede ser realmente interesante, ya que normalmente, solo una CPU puede tener una dirección dada en su caché L1 a la vez. Por lo tanto, si ambos núcleos acceden constantemente a la misma dirección, se producirán constantes errores de caché, ya que están peleándose por la dirección.

No puedo creer que no haya más respuestas a esto. De todos modos, un ejemplo clásico es iterar una matriz multidimensional "de adentro hacia afuera":

pseudocode for (i = 0 to size) for (j = 0 to size) do something with ary[j][i]

La razón por la que esto es ineficiente es porque las CPU modernas cargarán la línea de caché con direcciones de memoria "cercanas" desde la memoria principal cuando acceda a una sola dirección de memoria. Estamos iterando a través de las filas "j" (externas) en la matriz en el ciclo interno, por lo que para cada viaje a través del ciclo interno, la línea de caché hará que se vacíe y cargue con una línea de direcciones que están cerca de [ j] [i] entrada. Si esto se cambia a su equivalente:

for (i = 0 to size) for (j = 0 to size) do something with ary[i][j]

Funcionará mucho más rápido.

Preguntar cómo hacer un código, almacenar en caché eficazmente el caché y la mayoría de las demás preguntas, generalmente es preguntar cómo optimizar un programa, eso es porque el caché tiene un impacto tan grande en las actuaciones que cualquier programa optimizado es uno que sea caché. efectivo-caché amigable.

Sugiero leer sobre Optimización, hay algunas buenas respuestas en este sitio. En términos de libros, recomiendo en los sistemas informáticos: la perspectiva de un programador que contiene algunos textos sobre el uso correcto de la memoria caché.

(Por cierto, tan malo como un error de caché puede ser, hay peor) si un programa está paging desde el disco duro ...)

Puedo responder (2) diciendo que en el mundo de C ++, las listas vinculadas pueden matar fácilmente la memoria caché de la CPU. Las matrices son una mejor solución cuando es posible. No hay experiencia sobre si esto se aplica a otros idiomas, pero es fácil imaginar que surjan los mismos problemas.

Solo una publicación lo tocó, pero surge un gran problema cuando se comparten datos entre procesos. Desea evitar que varios procesos intenten modificar la misma línea de caché simultáneamente. Algo a tener en cuenta aquí es compartir "falso", donde dos estructuras de datos adyacentes comparten una línea de caché y las modificaciones a una invalidan la línea de caché para la otra. Esto puede hacer que las líneas de caché se muevan innecesariamente hacia adelante y hacia atrás entre las cachés de procesador que comparten los datos en un sistema multiprocesador. Una forma de evitarlo es alinear y rellenar las estructuras de datos para ponerlas en diferentes líneas.

Un ejemplo que vi utilizado en un motor de juego era mover datos de objetos a sus propias matrices. Un objeto del juego que estaba sujeto a la física también podría tener muchos otros datos adjuntos. Pero durante el ciclo de actualización de la física, todo lo que le importaba al motor eran datos sobre posición, velocidad, masa, cuadro delimitador, etc. Así que todo eso se colocó en sus propias matrices y se optimizó lo más posible para SSE.

Por lo tanto, durante el ciclo de física, los datos de física se procesaron en orden de matriz utilizando vectores matemáticos. Los objetos del juego usaron su ID de objeto como el índice en las diversas matrices. No era un puntero porque los punteros podían invalidarse si las matrices debían ser reubicadas.

En muchos sentidos, esto violó los patrones de diseño orientados a objetos, pero hizo que el código fuera mucho más rápido al colocar datos muy juntos que necesitaban operar en los mismos bucles.

Este ejemplo probablemente esté desactualizado porque espero que la mayoría de los juegos modernos usen un motor de física precompilado como Havok.

Una observación del "ejemplo clásico" del usuario 1800 INFORMATION (demasiado tiempo para un comentario)

Quería verificar las diferencias de tiempo para dos órdenes de iteración ("outter" e "inner"), así que hice un experimento simple con una gran matriz 2D:

measure::start(); for ( int y = 0; y < N; ++y ) for ( int x = 0; x < N; ++x ) sum += A[ x + y*N ]; measure::stop();

y el segundo caso con los bucles for intercambiados.

La versión más lenta ("x primero") era de 0.88 segundos y la más rápida, de 0.06 segundos. Ese es el poder del almacenamiento en caché :)

gcc -O2 y aún así los bucles no fueron optimizados. El comentario de Ricardo de que "la mayoría de los compiladores modernos pueden resolver esto por sí mismos" no es válido