PUERTA | PUERTA-CS-2006 | Pregunta 81

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 la relación M1/M2 es:
(A) 0
(B) 1/16
(C) 1/8
(D) 16

Respuesta: (B)
Explicación: [P2] ejecuta los bucles de manera que accede a elementos de A en orden principal de fila y [P2] accede a elementos en orden principal de columna.
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

Errores totales para [P2] = Número total de elementos en la array (para cada elemento, habría un error) = 512 * 512 = 262144.

Ratio m1/m2 = 16384 / 262144 = 1/16.

Cuestionario de esta pregunta