que - ¿Cuánto cuesta una caché L1?

que es cache en informatica

Question

Editar : para fines de referencia (si alguien tropieza con esta pregunta), Igor Ostrovsky escribió una gran publicación sobre errores de caché. Discute varios problemas diferentes y muestra números de ejemplo. Fin Editar

Hice algunas pruebas <long story goes here> y me pregunto si la diferencia de rendimiento se debe a fallas en la memoria caché. El siguiente código demuestra el problema y lo reduce a la porción crítica de tiempo. El siguiente código tiene un par de bucles que visitan la memoria en orden aleatorio y luego en orden de dirección ascendente.

Lo ejecuté en una máquina XP (compilada con VS2005: cl / O2) y en una caja Linux (gcc -Os). Ambos produjeron tiempos similares. Estos tiempos son en milisegundos. Creo que todos los loops se están ejecutando y no están optimizados (de lo contrario, se ejecutarían "instantáneamente").

*** Testing 20000 nodes Total Ordered Time: 888.822899 Total Random Time: 2155.846268

¿Estos números tienen sentido? ¿La diferencia se debe principalmente a errores de caché L1 o también está sucediendo algo más? Hay 20,000 ^ 2 accesos de memoria y si todos fallaron en la caché, eso es alrededor de 3.2 nanosegundos por error. La máquina XP (P4) que probé es de 3,2 GHz y sospecho (pero no lo sé) que tiene una memoria caché de 32 KB L1 y 512 KB de L2. Con 20,000 entradas (80KB), asumo que no hay un número significativo de fallas L2. Entonces esto sería (3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss . Eso parece alto para mí. Tal vez no lo sea, o tal vez mi matemática es mala. Intenté medir errores de caché con VTune, pero obtuve un BSOD. Y ahora no puedo hacer que se conecte al servidor de licencias (grrrr).

typedef struct stItem
{
   long     lData;
   //char     acPad[20];
} LIST_NODE;



#if defined( WIN32 )
void StartTimer( LONGLONG *pt1 )
{
   QueryPerformanceCounter( (LARGE_INTEGER*)pt1 );
}

void StopTimer( LONGLONG t1, double *pdMS )
{
   LONGLONG t2, llFreq;

   QueryPerformanceCounter( (LARGE_INTEGER*)&t2 );
   QueryPerformanceFrequency( (LARGE_INTEGER*)&llFreq );
   *pdMS = ((double)( t2 - t1 ) / (double)llFreq) * 1000.0;
}
#else
// doesn''t need 64-bit integer in this case
void StartTimer( LONGLONG *pt1 )
{
   // Just use clock(), this test doesn''t need higher resolution
   *pt1 = clock();
}

void StopTimer( LONGLONG t1, double *pdMS )
{
   LONGLONG t2 = clock();
   *pdMS = (double)( t2 - t1 ) / ( CLOCKS_PER_SEC / 1000 );
}
#endif



long longrand()
{
   #if defined( WIN32 )
   // Stupid cheesy way to make sure it is not just a 16-bit rand value
   return ( rand() << 16 ) | rand();
   #else
   return rand();
   #endif
}

// get random value in the given range
int randint( int m, int n )
{
   int ret = longrand() % ( n - m + 1 );
   return ret + m;
}

// I think I got this out of Programming Pearls (Bentley).
void ShuffleArray
(
   long *plShuffle,  // (O) return array of "randomly" ordered integers
   long lNumItems    // (I) length of array
)
{
   long i;
   long j;
   long t;

   for ( i = 0; i < lNumItems; i++ )
      plShuffle[i] = i;

   for ( i = 0; i < lNumItems; i++ )
      {
      j = randint( i, lNumItems - 1 );

      t = plShuffle[i];
      plShuffle[i] = plShuffle[j];
      plShuffle[j] = t;
      }
}



int main( int argc, char* argv[] )
{
   long          *plDataValues;
   LIST_NODE     *pstNodes;
   long          lNumItems = 20000;
   long          i, j;
   LONGLONG      t1;  // for timing
   double dms;

   if ( argc > 1 && atoi(argv[1]) > 0 )
      lNumItems = atoi( argv[1] );

   printf( "/n/n*** Testing %u nodes/n", lNumItems );

   srand( (unsigned int)time( 0 ));

   // allocate the nodes as one single chunk of memory
   pstNodes = (LIST_NODE*)malloc( lNumItems * sizeof( LIST_NODE ));
   assert( pstNodes != NULL );

   // Create an array that gives the access order for the nodes
   plDataValues = (long*)malloc( lNumItems * sizeof( long ));
   assert( plDataValues != NULL );

   // Access the data in order
   for ( i = 0; i < lNumItems; i++ )
      plDataValues[i] = i;

   StartTimer( &t1 );

   // Loop through and access the memory a bunch of times
   for ( j = 0; j < lNumItems; j++ )
      {
      for ( i = 0; i < lNumItems; i++ )
         {
         pstNodes[plDataValues[i]].lData = i * j;
         }
      }

   StopTimer( t1, &dms );
   printf( "Total Ordered Time: %f/n", dms );

   // now access the array positions in a "random" order
   ShuffleArray( plDataValues, lNumItems );

   StartTimer( &t1 );

   for ( j = 0; j < lNumItems; j++ )
      {
      for ( i = 0; i < lNumItems; i++ )
         {
         pstNodes[plDataValues[i]].lData = i * j;
         }
      }

   StopTimer( t1, &dms );
   printf( "Total Random Time: %f/n", dms );

}

Answer 1

3.2ns para una falta de caché L1 es completamente plausible. A modo de comparación, en una CPU PowerPC multinúcleo moderna particular, una falla L1 es de aproximadamente 40 ciclos, un poco más larga para algunos núcleos que otros, dependiendo de qué tan lejos estén de la memoria caché L2 (sí, realmente). Una falla L2 es al menos 600 ciclos.

La memoria caché es todo en rendimiento; Las CPU son mucho más rápidas que la memoria ahora que realmente está optimizando para el bus de memoria en lugar del núcleo.

Answer 2

Algunos números para un 3.4GHz P4 de un Lavalys Everest ejecutan:

• el dcache L1 es 8K (caché 64 bytes)
• L2 es 512K
• La latencia de búsqueda L1 es de 2 ciclos
• La latencia de búsqueda L2 es aproximadamente el doble de lo que está viendo: 20 ciclos

Más aquí: http://www.freeweb.hu/instlatx64/GenuineIntel0000F25_P4_Gallatin_MemLatX86.txt

(para las latencias, mira en la parte inferior de la página)

Answer 3

Aquí hay un intento de proporcionar información sobre el costo relativo de las fallas de la memoria caché por analogía con las galletas con chispas de chocolate para hornear ...

Tus manos son tus registros. Le toma 1 segundo para colocar las chispas de chocolate en la masa.

El mostrador de la cocina es tu caché L1, doce veces más lento que los registros. Se necesitan 12 x 1 = 12 segundos para pasar al mostrador, recoger la bolsa de nueces y vaciarla en la mano.

El refrigerador es tu caché L2, cuatro veces más lento que L1. Se necesitan 4 x 12 = 48 segundos para caminar hasta el refrigerador, abrirlo, quitar los restos de la comida de la noche anterior, sacar un cartón de huevos, abrir el cartón, poner 3 huevos en el mostrador y volver a colocar el cartón la nevera.

El armario es tu caché L3, tres veces más lento que L2. Se necesitan 3 x 48 = 2 minutos y 24 segundos para dar tres pasos hacia el armario, inclinarse, abrir la puerta, enraizar para encontrar el recipiente para hornear, extraerlo del armario, abrirlo, excavar para encontrar el polvo de hornear , póngalo en el mostrador y barrer el desastre que derramó en el piso.

Y la memoria principal? Esa es la tienda de la esquina, 5 veces más lenta que L3. Se necesitan 5 x 2:24 = 12 minutos para encontrar tu billetera, ponerte los zapatos y la chaqueta, correr por la calle, tomar un litro de leche, correr a casa, quitarte los zapatos y la chaqueta, y regresar a la cocina.

Tenga en cuenta que todos estos accesos son de complejidad constante, O (1), pero las diferencias entre ellos pueden tener un gran impacto en el rendimiento. La optimización puramente para la complejidad de la gran O es como decidir agregar chips de chocolate a la mezcla 1 a la vez o 10 a la vez, pero olvidando ponerlos en su lista de compras.

Moraleja de la historia: organice sus accesos de memoria para que la CPU tenga que ir de compras lo menos posible.

Los números se tomaron de la publicación de blog CPU Cache Flushing Fallacy , que indica que para un procesador Intel de la era de 2012 en particular, se cumple lo siguiente:

• registro de acceso = 4 instrucciones por ciclo
• Latencia L1 = 3 ciclos (12 x registro)
• Latencia L2 = 12 ciclos (4 x L1, 48 x registro)
• Latencia L3 = 38 ciclos (3 x L2, 12 x L1, registro de 144 x)
• Latencia de DRAM = 65 ns = 195 ciclos en una CPU de 3 GHz (5 x L3, 15 x L2, 60 x L1, registro de 720 x)

La Galería de efectos de caché de procesador también hace una buena lectura sobre este tema.

Answer 4

Bueno, sí, parece que será principalmente errores de caché L1.

10 ciclos para una caché L1 suena razonable, probablemente un poco en el lado bajo.

Una lectura de RAM va a tomar del orden de los 100 o incluso puede ser de 1000 (estoy demasiado cansado para intentar hacer las matemáticas en este momento;)) de ciclos, por lo que todavía es una gran victoria sobre eso.

Answer 5

Es difícil decir algo con seguridad sin muchas más pruebas, pero en mi experiencia esa escala de diferencia definitivamente se puede atribuir a la CPU L1 y / o a la caché L2, especialmente en un escenario con acceso aleatorio. Probablemente podrías empeorar aún más asegurándote de que cada acceso esté al menos a una distancia mínima del último.

Answer 6

Lo más fácil es tomar una fotografía a escala de la CPU objetivo y medir físicamente la distancia entre el núcleo y la caché de nivel 1. Multiplique esa distancia por la distancia que los electrones pueden viajar por segundo en cobre. Luego, calcula cuántos ciclos de reloj puedes tener en ese mismo momento. Esa es la cantidad mínima de ciclos de CPU que desperdiciará en un error de caché L1.

También puede calcular el costo mínimo de obtención de datos de la RAM en términos de la cantidad de ciclos de CPU desperdiciados de la misma manera. Puede que te sorprenda.

Tenga en cuenta que lo que está viendo aquí definitivamente tiene algo que ver con fallas de caché (ya sea L1 o L1 y L2) porque normalmente la caché extraerá los datos en la misma línea de caché una vez que acceda a cualquier cosa en esa línea de caché que requiera menos viajes a la RAM.

Sin embargo, lo que probablemente también esté viendo es el hecho de que la memoria RAM (aunque es llamada memoria de acceso aleatorio) aún prefiere el acceso a la memoria lineal.

Answer 7

Si bien no puedo ofrecer una respuesta a si los números tienen sentido (no estoy muy versado en las latencias de caché, pero para el registro ~ 10 ciclo de caché L1 no se oye bien), puedo ofrecer Cachegrind como un herramienta para ayudarlo a ver las diferencias en el rendimiento de la memoria caché entre sus 2 pruebas.

Cachegrind es una herramienta de Valgrind (el marco de trabajo que alimenta el siempre valioso memcheck) que registra el caché y los accesos directos / errores de las ramificaciones. Le dará una idea de cuántos aciertos / errores de caché está obteniendo realmente en su programa.

Answer 8

Si planea usar cachegrind, tenga en cuenta que solo es un simulador de golpe / error de caché. No siempre será exacto. Por ejemplo: si accede a alguna ubicación de memoria, digamos 0x1234 en un bucle 1000 veces, cachegrind siempre le mostrará que solo hubo una falta de caché (el primer acceso) incluso si tiene algo como:

clflush 0x1234 en tu loop.

En x86, esto causará todas las 1000 fallas de caché.