PUERTA | PUERTA-CS-2006 | Pregunta 80

Una CPU tiene una caché de asignación directa de 32 KB con un tamaño de bloque de 128 bytes. Suponga que A es una array bidimensional de tamaño 512 × 512 con elementos que ocupan 8 bytes cada uno. Considere los siguientes dos segmentos de código C, P1 y P2.
P1:

   
for (i=0; i<512; i++) {
   for (j=0; j<512; j++) {
      x += A[i][j];
   }
}

P2:

   
for (i=0; i<512; i++) {
   for (j=0; j<512; j++) {
      x += A[j][i];
   }
}

P1 y P2 se ejecutan de forma independiente con el mismo estado inicial, es decir, el arreglo A no está en caché y i, j, x están en registros. Deje que el número de errores de caché experimentados por P1 sea M1 y que para P2 sea M2.

El valor de M1 es:
(A) 0
(B) 2048
(C) 16384
(D) 262144

Respuesta: (C)
Explicación: [P1] ejecuta los bucles de manera que accede a los elementos de A en orden principal de fila y [P2 ] accede a los elementos en el orden principal de las columnas.
Número de bloques de caché = CacheSize/BlockSize = 32KB / 128 Byte = 256
Número de elementos de array en cada bloque = BlockSize/ElementSize = 128 Byte / 8 Byte = 16

Errores totales para [P1] = ArraySize * (N.º de elementos de array en cada bloque) / (N.º de bloques de caché) = 512 * 512 * 16/256 = 16384

Cuestionario de esta pregunta