tipos resueltos rendimiento que memoria informatica factores elementos ejercicios diseño directa determinan definicion correspondencia caracteristicas caché cache c caching

resueltos - que es cache en informatica



C Programa para determinar los niveles y el tamaño de la memoria caché (6)

¡Yo se esto! (En realidad es muy complicado debido a la precarga)

for (times = 0; times < Max; time++) /* many times*/ for (i=0; i < ArraySize; i = i + Stride) dummy = A[i]; /* touch an item in the array */

Cambiar zancada le permite probar las propiedades de las cachés. Al mirar un gráfico, obtendrá sus respuestas.

Mire las diapositivas 35-42 http://www.it.uu.se/edu/course/homepage/avdark/ht11/slides/11_Memory_and_optimization-1.pdf

Erik Hagersten es un profesor realmente bueno (y también muy competente, fue el arquitecto principal al sol en un punto), así que eche un vistazo al resto de sus diapositivas para obtener más explicaciones.

Re-escritura completa / Actualización para mayor claridad (y su cordura, es demasiado larga) ... ( Publicación anterior )

Para una tarea, necesito encontrar los niveles (L1, L2, ...) y el tamaño de cada caché. Sugerencias dadas y lo que encontré hasta ahora: creo que la idea es crear matrices de diferentes tamaños y leerlas. Sincronizando estas operaciones:

sizes = [1k, 4k, 256K, ...] foreach size in sizes create array of `size` start timer for i = 0 to n // just keep accessing array arr[(i * 16) % arr.length]++ // i * 16 supposed to modify every cache line ... see link record/print time

ACTUALIZADO (28 de septiembre a las 6:57 p.m. UTC + 8)

Ver también fuente completa

Ok, siguiendo los consejos de @mah, podría haber arreglado el problema de la relación SNR ... y también encontré un método para sincronizar mi código ( wall_clock_time desde un código de ejemplo de laboratorio)

Sin embargo, parece que estoy obteniendo resultados incorrectos: estoy en un Intel Core i3 2100: [ SPECS ]

  • L1: 2 x 32 K
  • L2: 2 x 256 K
  • L3: 3MB

Los resultados que obtuve, en un gráfico:

longitudMod: 1KB a 512K

La base del primer pico es 32K ... razonable ... el segundo es 384K ... ¿por qué? Estoy esperando 256?

longitudMod: 512k a 4MB

Entonces, ¿por qué este rango puede ser un desastre?

También leí acerca de la captación previa o la interferencia de otras aplicaciones, así que cerré tantas cosas como fuera posible mientras se ejecuta el script; parece que (a través de varias ejecuciones) los datos de 1MB o más siempre son tan desordenados.

Después de 10 minutos de búsqueda en el manual de instrucciones de Intel y otros 10 minutos de codificación, se me ocurrió esto (para los procesadores basados ​​en Intel):

void i386_cpuid_caches () { int i; for (i = 0; i < 32; i++) { // Variables to hold the contents of the 4 i386 legacy registers uint32_t eax, ebx, ecx, edx; eax = 4; // get cache info ecx = i; // cache id __asm__ ( "cpuid" // call i386 cpuid instruction : "+a" (eax) // contains the cpuid command code, 4 for cache query , "=b" (ebx) , "+c" (ecx) // contains the cache id , "=d" (edx) ); // generates output in 4 registers eax, ebx, ecx and edx // taken from http://download.intel.com/products/processor/manual/325462.pdf Vol. 2A 3-149 int cache_type = eax & 0x1F; if (cache_type == 0) // end of valid cache identifiers break; char * cache_type_string; switch (cache_type) { case 1: cache_type_string = "Data Cache"; break; case 2: cache_type_string = "Instruction Cache"; break; case 3: cache_type_string = "Unified Cache"; break; default: cache_type_string = "Unknown Type Cache"; break; } int cache_level = (eax >>= 5) & 0x7; int cache_is_self_initializing = (eax >>= 3) & 0x1; // does not need SW initialization int cache_is_fully_associative = (eax >>= 1) & 0x1; // taken from http://download.intel.com/products/processor/manual/325462.pdf 3-166 Vol. 2A // ebx contains 3 integers of 10, 10 and 12 bits respectively unsigned int cache_sets = ecx + 1; unsigned int cache_coherency_line_size = (ebx & 0xFFF) + 1; unsigned int cache_physical_line_partitions = ((ebx >>= 12) & 0x3FF) + 1; unsigned int cache_ways_of_associativity = ((ebx >>= 10) & 0x3FF) + 1; // Total cache size is the product size_t cache_total_size = cache_ways_of_associativity * cache_physical_line_partitions * cache_coherency_line_size * cache_sets; printf( "Cache ID %d:/n" "- Level: %d/n" "- Type: %s/n" "- Sets: %d/n" "- System Coherency Line Size: %d bytes/n" "- Physical Line partitions: %d/n" "- Ways of associativity: %d/n" "- Total Size: %zu bytes (%zu kb)/n" "- Is fully associative: %s/n" "- Is Self Initializing: %s/n" "/n" , i , cache_level , cache_type_string , cache_sets , cache_coherency_line_size , cache_physical_line_partitions , cache_ways_of_associativity , cache_total_size, cache_total_size >> 10 , cache_is_fully_associative ? "true" : "false" , cache_is_self_initializing ? "true" : "false" ); } }

Referencia: http://download.intel.com/products/processor/manual/325462.pdf 3-166 Vol. 2A

Esto es mucho más confiable que la medición de latencias de caché, ya que es prácticamente imposible desactivar la captación previa de caché en un procesador moderno. Si necesita información similar para una arquitectura de procesador diferente, deberá consultar el manual correspondiente.

Editar: descriptor de tipo de caché agregado. Edit2: indicador de nivel de caché agregado. Edit3: se agregó más documentación.

El tiempo que toma medir su tiempo (es decir, el tiempo justo para llamar a la función de reloj ()) es muchos muchos (muchos, muchos, ...) veces mayor que el tiempo que lleva realizar arr[(i*16)&lengthMod]++ . Esta relación extremadamente baja de señal a ruido (entre otras posibles dificultades) hace que su plan sea inviable. Una gran parte del problema es que estás tratando de medir una sola iteración del ciclo; el código de muestra que ha vinculado está intentando medir un conjunto completo de iteraciones (lea el reloj antes de comenzar el ciclo, léalo de nuevo después de salir del ciclo, no use printf () dentro del ciclo).

Si su bucle es lo suficientemente grande, es posible que pueda superar el problema de la relación señal-ruido.

En cuanto a "qué elemento se está incrementando"; arr es una dirección de un buffer de 1MB; arr[(i * 16) & lengthMod]++; causes (i * 16) * lengthMod para generar un desplazamiento desde esa dirección; ese desplazamiento es la dirección del int que se incrementa. Está realizando un cambio (i * 16 se convertirá en i << 4), un incremento lógico y, además, un incremento de lectura / adición / escritura o un incremento individual, dependiendo de su CPU).

Editar: Como se describió, su código sufre de una SNR deficiente (relación señal / ruido) debido a las velocidades relativas de acceso a la memoria (caché o sin caché) y funciones de llamada solo para medir el tiempo. Para obtener los tiempos que está recibiendo actualmente, supongo que modificó el código para que se parezca a algo así como:

int main() { int steps = 64 * 1024 * 1024; int arr[1024 * 1024]; int lengthMod = (1024 * 1024) - 1; int i; double timeTaken; clock_t start; start = clock(); for (i = 0; i < steps; i++) { arr[(i * 16) & lengthMod]++; } timeTaken = (double)(clock() - start)/CLOCKS_PER_SEC; printf("Time for %d: %.12f /n", i, timeTaken); }

Esto mueve la medición fuera del ciclo, por lo que no está midiendo un solo acceso (lo cual sería realmente imposible), sino que está midiendo los steps accede.

Puede aumentar los steps según sea necesario y esto tendrá un impacto directo en sus tiempos. Dado que los tiempos que está recibiendo están muy juntos, y en algunos casos incluso invertidos (su tiempo oscila entre tamaños, lo que probablemente no sea causado por la caché), puede intentar cambiar el valor de los steps a 256 * 1024 * 1024 o incluso más grande.

NOTA: Puede realizar steps tan grandes como pueda encajar en un int firmado (que debería ser lo suficientemente grande), ya que el lógico y se asegura de que se ajuste en su búfer.

Para Windows, puede usar el método GetLogicalProcessorInformation .

Para Linux, puede usar sysconf() . Puede encontrar argumentos válidos para sysconf en /usr/include/unistd.h o /usr/include/bits/confname.h

Para responder a su pregunta de números extraños por encima de 1MB, es bastante simple; las políticas de desalojo de caché que tienen que ver con la predicción de bifurcación y el hecho de que la memoria caché L3 se comparte entre los núcleos.

Un núcleo i3 tiene una estructura de caché muy interesante. En realidad, cualquier procesador moderno lo hace. Deberías leer sobre ellos en wikipedia; hay todo tipo de formas para que decida "bueno, probablemente no necesite esto ..." y luego puede decir "Lo pondré en el caché de la víctima" o cualquier cantidad de cosas. Los tiempos de caché L1-2-3 pueden ser muy complejos en función de una gran cantidad de factores y de las decisiones de diseño individuales.

Además de eso, todas estas decisiones y más (ver artículos de wikipedia sobre el tema) deben sincronizarse entre los cachés de los dos núcleos. Los métodos para sincronizar el caché L3 compartido con cachés L1 y L2 separados pueden ser desagradables, pueden incluir cálculos de retroceso y reaprendizaje u otros métodos. Es muy poco probable que alguna vez tengas un segundo núcleo completamente libre y nada que compita con el espacio de caché L3 y, por lo tanto, causando rareza de sincronización.

En general, si está trabajando en datos, por ejemplo, en la conversión de núcleos, quiere asegurarse de que encaja dentro de la memoria caché L1 y darle forma a su algoritmo. La memoria caché L3 no está pensada para trabajar en un conjunto de datos de la forma en que lo hace (¡aunque es mejor que la memoria principal!)

Juro que si tuviera que implementar algoritmos de caché me volvería loco.