open - Medición de latencias de caché

whatsapp cache link

Question

Así que estoy tratando de medir las latencias de la caché L1, L2, L3 usando C. Sé el tamaño de las mismas y creo que entiendo conceptualmente cómo hacerlo, pero estoy teniendo problemas con mi implementación. Me pregunto si algunas de las complejidades de hardware, como la precarga, están causando problemas.

#include <time.h>
#include <stdio.h>
#include <string.h>
int main(){
srand(time(NULL)); // Seed ONCE
const int L1_CACHE_SIZE = 32768/sizeof(int);
const int L2_CACHE_SIZE = 262144/sizeof(int);
const int L3_CACHE_SIZE = 6587392/sizeof(int);
const int NUM_ACCESSES = 1000000;
const int SECONDS_PER_NS = 1000000000;
int arrayAccess[L1_CACHE_SIZE];
int arrayInvalidateL1[L1_CACHE_SIZE];
int arrayInvalidateL2[L2_CACHE_SIZE];
int arrayInvalidateL3[L3_CACHE_SIZE];
int count=0;
int index=0;
int i=0;
struct timespec startAccess, endAccess;
double mainMemAccess, L1Access, L2Access, L3Access;
int readValue=0;
memset(arrayAccess, 0, L1_CACHE_SIZE*sizeof(int));
memset(arrayInvalidateL1, 0, L1_CACHE_SIZE*sizeof(int));
memset(arrayInvalidateL2, 0, L2_CACHE_SIZE*sizeof(int));
memset(arrayInvalidateL3, 0, L3_CACHE_SIZE*sizeof(int));
index = 0;
clock_gettime(CLOCK_REALTIME, &startAccess); //start clock
while (index < L1_CACHE_SIZE) {
int tmp = arrayAccess[index]; //Access Value from L2
index = (index + tmp + ((index & 4) ? 28 : 36)); // on average this should give 32 element skips, with changing strides
count++; //divide overall time by this
}
clock_gettime(CLOCK_REALTIME, &endAccess); //end clock
mainMemAccess = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
mainMemAccess /= count;
printf("Main Memory Access %lf/n", mainMemAccess);
index = 0;
count=0;
clock_gettime(CLOCK_REALTIME, &startAccess); //start clock
while (index < L1_CACHE_SIZE) {
int tmp = arrayAccess[index]; //Access Value from L2
index = (index + tmp + ((index & 4) ? 28 : 36)); // on average this should give 32 element skips, with changing strides
count++; //divide overall time by this
}
clock_gettime(CLOCK_REALTIME, &endAccess); //end clock
L1Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
L1Access /= count;
printf("L1 Cache Access %lf/n", L1Access);
//invalidate L1 by accessing all elements of array which is larger than cache
for(count=0; count < L1_CACHE_SIZE; count++){
int read = arrayInvalidateL1[count];
read++;
readValue+=read;
}
index = 0;
count = 0;
clock_gettime(CLOCK_REALTIME, &startAccess); //start clock
while (index < L1_CACHE_SIZE) {
int tmp = arrayAccess[index]; //Access Value from L2
index = (index + tmp + ((index & 4) ? 28 : 36)); // on average this should give 32 element skips, with changing strides
count++; //divide overall time by this
}
clock_gettime(CLOCK_REALTIME, &endAccess); //end clock
L2Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
L2Access /= count;
printf("L2 Cache Acces %lf/n", L2Access);
//invalidate L2 by accessing all elements of array which is larger than cache
for(count=0; count < L2_CACHE_SIZE; count++){
int read = arrayInvalidateL2[count];
read++;
readValue+=read;
}
index = 0;
count=0;
clock_gettime(CLOCK_REALTIME, &startAccess); //sreadValue+=read;tart clock
while (index < L1_CACHE_SIZE) {
int tmp = arrayAccess[index]; //Access Value from L2
index = (index + tmp + ((index & 4) ? 28 : 36)); // on average this should give 32 element skips, with changing strides
count++; //divide overall time by this
}
clock_gettime(CLOCK_REALTIME, &endAccess); //end clock
L3Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
L3Access /= count;
printf("L3 Cache Access %lf/n", L3Access);
printf("Read Value: %d", readValue);
}

Empiezo accediendo a un valor en la matriz de la que quiero datos. Obviamente, esto debería provenir de la memoria principal porque es el primer acceso. La matriz es pequeña (menos que el tamaño de página) por lo que debe copiarse en L1, L2, L3. Acceder al valor de la misma matriz que ahora debería ser L1. A continuación, accedo a todos los valores de una matriz del mismo tamaño que la caché L1 para invalidar los datos a los que quiero acceder (por lo que ahora debería estar solo en L2 / 3). Luego repito este proceso para L2 y L3. Sin embargo, los tiempos de acceso son evidentes, lo que significa que estoy haciendo algo mal ...

Creo que puede haber problemas con el tiempo que lleva el reloj (comenzar y detener va a tomar algo de tiempo en ns y cambiará cuando se guarden en caché / sin marcar)

¿Puede alguien darme algunos consejos sobre lo que podría estar haciendo mal?

ACTUALIZACIÓN1: Así que amorticé el costo del temporizador haciendo muchos accesos, arreglé el tamaño de mis cachés y también tomé el consejo de hacer un esquema de indexación más complejo para evitar pasos fijos. Desafortunadamente los tiempos todavía están apagados. Todos parecen venir por L1. Estoy pensando que el problema podría ser invalidar en lugar de acceder. ¿Un esquema aleatorio vs LRU afectaría la invalidación de los datos?

ACTUALIZACIÓN2: Se corrigió el memset (el memset agregado de L3 para invalidar los datos en L3 también así que el primer acceso comienza en la memoria principal) y el esquema de indexación, todavía no hay suerte.

ACTUALIZACIÓN3: No podría lograr que este método funcione, pero hubo algunas buenas respuestas sugeridas y publiqué un par de soluciones propias.

También ejecuté Cachegrind para ver acertar / fallar

 ==6710== I refs: 1,735,104
==6710== I1 misses: 1,092
==6710== LLi misses: 1,084
==6710== I1 miss rate: 0.06%
==6710== LLi miss rate: 0.06%
==6710==
==6710== D refs: 1,250,696 (721,162 rd + 529,534 wr)
==6710== D1 misses: 116,492 ( 7,627 rd + 108,865 wr)
==6710== LLd misses: 115,102 ( 6,414 rd + 108,688 wr)
==6710== D1 miss rate: 9.3% ( 1.0% + 20.5% )
==6710== LLd miss rate: 9.2% ( 0.8% + 20.5% )
==6710==
==6710== LL refs: 117,584 ( 8,719 rd + 108,865 wr)
==6710== LL misses: 116,186 ( 7,498 rd + 108,688 wr)
==6710== LL miss rate: 3.8% ( 0.3% + 20.5% )
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw
. . . . . . . . . #include <time.h>
. . . . . . . . . #include <stdio.h>
. . . . . . . . . #include <string.h>
. . . . . . . . .
6 0 0 0 0 0 2 0 0 int main(){
5 1 1 0 0 0 2 0 0 srand(time(NULL)); // Seed ONCE
1 0 0 0 0 0 1 0 0 const int L1_CACHE_SIZE = 32768/sizeof(int);
1 0 0 0 0 0 1 0 0 const int L2_CACHE_SIZE = 262144/sizeof(int);
1 0 0 0 0 0 1 0 0 const int L3_CACHE_SIZE = 6587392/sizeof(int);
1 0 0 0 0 0 1 0 0 const int NUM_ACCESSES = 1000000;
1 0 0 0 0 0 1 0 0 const int SECONDS_PER_NS = 1000000000;
21 2 2 3 0 0 3 0 0 int arrayAccess[L1_CACHE_SIZE];
21 1 1 3 0 0 3 0 0 int arrayInvalidateL1[L1_CACHE_SIZE];
21 2 2 3 0 0 3 0 0 int arrayInvalidateL2[L2_CACHE_SIZE];
21 1 1 3 0 0 3 0 0 int arrayInvalidateL3[L3_CACHE_SIZE];
1 0 0 0 0 0 1 0 0 int count=0;
1 1 1 0 0 0 1 0 0 int index=0;
1 0 0 0 0 0 1 0 0 int i=0;
. . . . . . . . . struct timespec startAccess, endAccess;
. . . . . . . . . double mainMemAccess, L1Access, L2Access, L3Access;
1 0 0 0 0 0 1 0 0 int readValue=0;
. . . . . . . . .
7 0 0 2 0 0 1 1 1 memset(arrayAccess, 0, L1_CACHE_SIZE*sizeof(int));
7 1 1 2 2 0 1 0 0 memset(arrayInvalidateL1, 0, L1_CACHE_SIZE*sizeof(int));
7 0 0 2 2 0 1 0 0 memset(arrayInvalidateL2, 0, L2_CACHE_SIZE*sizeof(int));
7 1 1 2 2 0 1 0 0 memset(arrayInvalidateL3, 0, L3_CACHE_SIZE*sizeof(int));
. . . . . . . . .
1 0 0 0 0 0 1 1 1 index = 0;
4 0 0 0 0 0 1 0 0 clock_gettime(CLOCK_REALTIME, &startAccess); //start clock
772 1 1 514 0 0 0 0 0 while (index < L1_CACHE_SIZE) {
1,280 1 1 768 257 257 256 0 0 int tmp = arrayAccess[index]; //Access Value from L2
2,688 0 0 768 0 0 256 0 0 index = (index + tmp + ((index & 4) ? 28 : 36)); // on average this should give 32 element skips, with changing strides
256 0 0 256 0 0 0 0 0 count++; //divide overall time by this
. . . . . . . . . }
4 0 0 0 0 0 1 0 0 clock_gettime(CLOCK_REALTIME, &endAccess); //end clock
14 1 1 5 1 1 1 1 1 mainMemAccess = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
6 0 0 2 0 0 1 0 0 mainMemAccess /= count;
. . . . . . . . .
6 1 1 2 0 0 2 0 0 printf("Main Memory Access %lf/n", mainMemAccess);
. . . . . . . . .
1 0 0 0 0 0 1 0 0 index = 0;
1 0 0 0 0 0 1 0 0 count=0;
4 1 1 0 0 0 1 0 0 clock_gettime(CLOCK_REALTIME, &startAccess); //start clock
772 1 1 514 0 0 0 0 0 while (index < L1_CACHE_SIZE) {
1,280 0 0 768 240 0 256 0 0 int tmp = arrayAccess[index]; //Access Value from L2
2,688 0 0 768 0 0 256 0 0 index = (index + tmp + ((index & 4) ? 28 : 36)); // on average this should give 32 element skips, with changing strides
256 0 0 256 0 0 0 0 0 count++; //divide overall time by this
. . . . . . . . . }
4 0 0 0 0 0 1 0 0 clock_gettime(CLOCK_REALTIME, &endAccess); //end clock
14 1 1 5 0 0 1 1 0 L1Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
6 1 1 2 0 0 1 0 0 L1Access /= count;
. . . . . . . . .
6 0 0 2 0 0 2 0 0 printf("L1 Cache Access %lf/n", L1Access);
. . . . . . . . .
. . . . . . . . . //invalidate L1 by accessing all elements of array which is larger than cache
32,773 1 1 24,578 0 0 1 0 0 for(count=0; count < L1_CACHE_SIZE; count++){
40,960 0 0 24,576 513 513 8,192 0 0 int read = arrayInvalidateL1[count];
8,192 0 0 8,192 0 0 0 0 0 read++;
16,384 0 0 16,384 0 0 0 0 0 readValue+=read;
. . . . . . . . . }
. . . . . . . . .
1 0 0 0 0 0 1 0 0 index = 0;
1 1 1 0 0 0 1 0 0 count = 0;
4 0 0 0 0 0 1 1 0 clock_gettime(CLOCK_REALTIME, &startAccess); //start clock
772 1 1 514 0 0 0 0 0 while (index < L1_CACHE_SIZE) {
1,280 0 0 768 256 0 256 0 0 int tmp = arrayAccess[index]; //Access Value from L2
2,688 0 0 768 0 0 256 0 0 index = (index + tmp + ((index & 4) ? 28 : 36)); // on average this should give 32 element skips, with changing strides
256 0 0 256 0 0 0 0 0 count++; //divide overall time by this
. . . . . . . . . }
4 1 1 0 0 0 1 0 0 clock_gettime(CLOCK_REALTIME, &endAccess); //end clock
14 0 0 5 1 0 1 1 0 L2Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
6 1 1 2 0 0 1 0 0 L2Access /= count;
. . . . . . . . .
6 0 0 2 0 0 2 0 0 printf("L2 Cache Acces %lf/n", L2Access);
. . . . . . . . .
. . . . . . . . . //invalidate L2 by accessing all elements of array which is larger than cache
262,149 2 2 196,610 0 0 1 0 0 for(count=0; count < L2_CACHE_SIZE; count++){
327,680 0 0 196,608 4,097 4,095 65,536 0 0 int read = arrayInvalidateL2[count];
65,536 0 0 65,536 0 0 0 0 0 read++;
131,072 0 0 131,072 0 0 0 0 0 readValue+=read;
. . . . . . . . . }
. . . . . . . . .
1 0 0 0 0 0 1 0 0 index = 0;
1 0 0 0 0 0 1 0 0 count=0;
4 0 0 0 0 0 1 1 0 clock_gettime(CLOCK_REALTIME, &startAccess); //sreadValue+=read;tart clock
772 1 1 514 0 0 0 0 0 while (index < L1_CACHE_SIZE) {
1,280 0 0 768 256 0 256 0 0 int tmp = arrayAccess[index]; //Access Value from L2
2,688 0 0 768 0 0 256 0 0 index = (index + tmp + ((index & 4) ? 28 : 36)); // on average this should give 32 element skips, with changing strides
256 0 0 256 0 0 0 0 0 count++; //divide overall time by this
. . . . . . . . . }
4 0 0 0 0 0 1 0 0 clock_gettime(CLOCK_REALTIME, &endAccess); //end clock
14 1 1 5 1 0 1 1 0 L3Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
6 0 0 2 0 0 1 0 0 L3Access /= count;
. . . . . . . . .
6 1 1 2 0 0 2 0 0 printf("L3 Cache Access %lf/n", L3Access);
. . . . . . . . .
6 0 0 1 0 0 1 0 0 printf("Read Value: %d", readValue);
. . . . . . . . .
3 0 0 3 0 0 0 0 0 }

Answer 1

Bueno para los interesados, no pude hacer funcionar mi primer código, así que probé un par de enfoques alternativos que produjeron resultados decentes.

La primera utilizaba listas vinculadas con nodos asignados zancada bytes aparte en un espacio de memoria contigua. La desreferenciación de los nodos mitiga la efectividad de la captura previa y, en el caso de que se tomen múltiples líneas de caché, hice los pasos más largos para evitar los golpes de caché. A medida que aumenta el tamaño de la lista asignada, salta al caché o estructura de memoria que lo mantendrá mostrando divisiones claras en la latencia.

#include <time.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
//MACROS
#define ONE iterate = (char**) *iterate;
#define FIVE ONE ONE ONE
#define TWOFIVE FIVE FIVE FIVE FIVE FIVE
#define HUNDO TWOFIVE TWOFIVE TWOFIVE TWOFIVE
//prototype
void allocateRandomArray(long double);
void accessArray(char *, long double, char**);
int main(){
//call the function for allocating arrays of increasing size in MB
allocateRandomArray(.00049);
allocateRandomArray(.00098);
allocateRandomArray(.00195);
allocateRandomArray(.00293);
allocateRandomArray(.00391);
allocateRandomArray(.00586);
allocateRandomArray(.00781);
allocateRandomArray(.01172);
allocateRandomArray(.01562);
allocateRandomArray(.02344);
allocateRandomArray(.03125);
allocateRandomArray(.04688);
allocateRandomArray(.0625);
allocateRandomArray(.09375);
allocateRandomArray(.125);
allocateRandomArray(.1875);
allocateRandomArray(.25);
allocateRandomArray(.375);
allocateRandomArray(.5);
allocateRandomArray(.75);
allocateRandomArray(1);
allocateRandomArray(1.5);
allocateRandomArray(2);
allocateRandomArray(3);
allocateRandomArray(4);
allocateRandomArray(6);
allocateRandomArray(8);
allocateRandomArray(12);
allocateRandomArray(16);
allocateRandomArray(24);
allocateRandomArray(32);
allocateRandomArray(48);
allocateRandomArray(64);
allocateRandomArray(96);
allocateRandomArray(128);
allocateRandomArray(192);
}
void allocateRandomArray(long double size){
int accessSize=(1024*1024*size); //array size in bytes
char * randomArray = malloc(accessSize*sizeof(char)); //allocate array of size allocate size
int counter;
int strideSize=4096; //step size
char ** head = (char **) randomArray; //start of linked list in contiguous memory
char ** iterate = head; //iterator for linked list
for(counter=0; counter < accessSize; counter+=strideSize){
(*iterate) = &randomArray[counter+strideSize]; //iterate through linked list, having each one point stride bytes forward
iterate+=(strideSize/sizeof(iterate)); //increment iterator stride bytes forward
}
*iterate = (char *) head; //set tailf to point to head
accessArray(randomArray, size, head);
free(randomArray);
}
void accessArray(char *cacheArray, long double size, char** head){
const long double NUM_ACCESSES = 1000000000/100; //number of accesses to linked list
const int SECONDS_PER_NS = 1000000000; //const for timer
FILE *fp = fopen("accessData.txt", "a"); //open file for writing data
int newIndex=0;
int counter=0;
int read=0;
struct timespec startAccess, endAccess; //struct for timer
long double accessTime = 0;
char ** iterate = head; //create iterator
clock_gettime(CLOCK_REALTIME, &startAccess); //start clock
for(counter=0; counter < NUM_ACCESSES; counter++){
HUNDO //macro subsitute 100 accesses to mitigate loop overhead
}
clock_gettime(CLOCK_REALTIME, &endAccess); //end clock
//calculate the time elapsed in ns per access
accessTime = (((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec)) / (100*NUM_ACCESSES);
fprintf(fp, "%Lf/t%Lf/n", accessTime, size); //print results to file
fclose(fp); //close file
}

Esto produjo los resultados más consistentes, y el uso de una variedad de tamaños de matriz y el trazado de las respectivas latencias dio una distinción muy clara de los diferentes tamaños de caché presentes.

El siguiente método como el anterior asignado matrices de tamaño creciente. Pero en lugar de utilizar una lista vinculada para el acceso a la memoria, llené cada índice con su número respectivo y aleatoriamente mezclé la matriz. Luego usé estos índices para saltar aleatoriamente dentro de la matriz de accesos, mitigando los efectos de la captura previa. Sin embargo, tuvo una fuerte desviación ocasional en el tiempo de acceso cuando se arrastran múltiples líneas de caché adyacentes y se llega a golpear.

#include <time.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
//prototype
void allocateRandomArray(long double);
void accessArray(int *, long int);
int main(){
srand(time(NULL)); // Seed random function
int i=0;
for(i=2; i < 32; i++){
allocateRandomArray(pow(2, i)); //call latency function on arrays of increasing size
}
}
void allocateRandomArray(long double size){
int accessSize = (size) / sizeof(int);
int * randomArray = malloc(accessSize*sizeof(int));
int counter;
for(counter=0; counter < accessSize; counter ++){
randomArray[counter] = counter;
}
for(counter=0; counter < accessSize; counter ++){
int i,j;
int swap;
i = rand() % accessSize;
j = rand() % accessSize;
swap = randomArray[i];
randomArray[i] = randomArray[j];
randomArray[j] = swap;
}
accessArray(randomArray, accessSize);
free(randomArray);
}
void accessArray(int *cacheArray, long int size){
const long double NUM_ACCESSES = 1000000000;
const int SECONDS_PER_NS = 1000000000;
int newIndex=0;
int counter=0;
int read=0;
struct timespec startAccess, endAccess;
long double accessTime = 0;
clock_gettime(CLOCK_REALTIME, &startAccess); //start clock
for(counter = 0; counter < NUM_ACCESSES; counter++){
newIndex=cacheArray[newIndex];
}
clock_gettime(CLOCK_REALTIME, &endAccess); //end clock
//calculate the time elapsed in ns per access
accessTime = (((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec)) / (NUM_ACCESSES);
printf("Access time: %Lf for size %ld/n", accessTime, size);
}

Promediado en muchos ensayos, este método también produjo resultados relativamente precisos. La primera opción es definitivamente la mejor de las dos, pero este es un enfoque alternativo que funciona bien también.

Answer 2

En realidad, no es una respuesta, pero de todos modos, algo ya se ha mencionado en otras respuestas y comentarios aquí.

Bueno, justo el otro día respondo esta pregunta:

• Estimación del tamaño de la caché en su sistema

se trata de la medición de las tasas de transferencia de L1/L2/.../L?/MEMORY , eche un vistazo para obtener un mejor punto de inicio de su problema

[Notas]

1. Recomiendo usar la instrucción RDTSC para medir el tiempo

   especialmente para L1 ya que cualquier otra cosa es demasiado lento. ¡No olvides establecer la afinidad del proceso en una sola CPU porque todos los núcleos tienen su propio contador y su conteo difiere mucho incluso en la misma entrada Clock !!!

   Ajuste el reloj de la CPU a Máximo para las computadoras con reloj variable y no olvide contabilizar el desbordamiento de RDTSC si usa solo una parte de 32 bits (contador de 32 bits de desbordamiento de la CPU moderna en un segundo). Para calcular el tiempo, use el reloj de la CPU (mida o use el valor de registro)

   t0 <- RDTSC
   Sleep(250);
   t1 <- RDTSC
   CPU f=(t1-t0)<<2 [Hz]

2. establecer la afinidad del proceso a una sola CPU

   todos los núcleos de la CPU generalmente tienen sus propios cachés L1, L2, por lo que en el sistema operativo multitarea puede medir cosas confusas si no lo hace

3. hacer salida gráfica (diagrama)

   entonces verás lo que realmente sucede en ese enlace de arriba. Publiqué algunas parcelas

4. use la mayor prioridad de proceso disponible por OS

Answer 3

La prueba clásica ampliamente utilizada para la latencia de caché se itera sobre la lista enlazada. Funciona en CPU superescalar / superpulsado moderno e incluso en núcleos fuera de servicio como ARM Cortex-A9 + e Intel Core 2 / ix. Este método es utilizado por lmbench de fuente abierta, en la prueba lat_mem_rd ( página man ) y en la herramienta de medición de latencia CPU-Z: http://cpuid.com/medias/files/softwares/misc/latency.zip (binario nativo de Windows )

Hay fuentes de la prueba lat_mem_rd de lmbench: https://github.com/foss-for-synopsys-dwc-arc-processors/lmbench/blob/master/src/lat_mem_rd.c

Y la prueba principal es

#define ONE p = (char **)*p;
#define FIVE ONE ONE ONE ONE ONE
#define TEN FIVE FIVE
#define FIFTY TEN TEN TEN TEN TEN
#define HUNDRED FIFTY FIFTY
void
benchmark_loads(iter_t iterations, void *cookie)
{
struct mem_state* state = (struct mem_state*)cookie;
register char **p = (char**)state->p[0];
register size_t i;
register size_t count = state->len / (state->line * 100) + 1;
while (iterations-- > 0) {
for (i = 0; i < count; ++i) {
HUNDRED;
}
}
use_pointer((void *)p);
state->p[0] = (char*)p;
}

Entonces, después de descifrar la macro, hacemos muchas operaciones lineales como:

 p = (char**) *p; // (in intel syntax) == mov eax, [eax]
p = (char**) *p;
p = (char**) *p;
.... // 100 times total
p = (char**) *p;

sobre la memoria, lleno de punteros, cada elemento de stride hacia adelante.

Como dice la página del manual http://www.bitmover.com/lmbench/lat_mem_rd.8.html

El punto de referencia se ejecuta como dos bucles anidados. El bucle externo es el tamaño de zancada. El bucle interno es el tamaño de la matriz. Para cada tamaño de matriz, la referencia crea un anillo de punteros que apuntan hacia adelante una zancada. Atravesar la matriz se hace por

 p = (char **)*p;

en un bucle for (el exceso de bucle for no es significativo; el bucle es un bucle desenrollado de 1000 cargas de largo). El ciclo se detiene después de hacer un millón de cargas. El tamaño de la matriz varía de 512 bytes a (típicamente) ocho megabytes. Para los tamaños pequeños, la memoria caché tendrá un efecto, y las cargas serán mucho más rápidas. Esto se vuelve mucho más aparente cuando se trazan los datos.

La descripción más detallada con ejemplos de PODER está disponible en el wiki de IBM: Untangling memory access measures - lat_mem_rd - por Jenifer Hopper 2013

La prueba lat_mem_rd ( http://www.bitmover.com/lmbench/lat_mem_rd.8.html ) toma dos argumentos, un tamaño de matriz en MB y un tamaño de zancada. El punto de referencia usa dos bucles para atravesar el conjunto, usando el paso como el incremento creando un anillo de punteros que apuntan hacia adelante un paso. La prueba mide la latencia de lectura de memoria en nanosegundos para el rango de tamaños de memoria. La salida consta de dos columnas: la primera es el tamaño de la matriz en MB (el valor de coma flotante) y la segunda es la latencia de carga sobre todos los puntos de la matriz. Cuando se grafican los resultados, puede ver claramente las latencias relativas de toda la jerarquía de la memoria, incluida la latencia más rápida de cada nivel de caché y la latencia de la memoria principal.

PD: Hay un documento de Intel (gracias a Eldar Abusalimov ) con ejemplos de ejecución lat_mem_rd: ftp://download.intel.com/design/intarch/PAPERS/321074.pdf - lo siento url derecha es http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-cache-latency-bandwidth-paper.pdf "Medición de caché y latencia de memoria y ancho de banda de CPU a memoria: para uso con arquitectura Intel" por Joshua Ruggiero desde diciembre de 2008:

Answer 4

Ok, varios problemas con tu código:

1. Como mencionaste, tu medida lleva mucho tiempo. De hecho, es muy probable que lleven más tiempo que el acceso único, por lo que no están midiendo nada útil. Para mitigar eso, acceda a múltiples elementos y amortícelos (divida el tiempo total entre la cantidad de accesos. Tenga en cuenta que para medir la latencia, desea que estos accesos se serialicen; de lo contrario, se pueden realizar en paralelo y solo se medirá el rendimiento de accesos no relacionados. Para lograr eso, solo podría agregar una dependencia falsa entre los accesos.

   Por ejemplo, inicializar la matriz a ceros, y hacer:

   clock_gettime(CLOCK_REALTIME, &startAccess); //start clock
   for (int i = 0; i < NUM_ACCESSES; ++i) {
   int tmp = arrayAccess[index]; //Access Value from Main Memory
   index = (index + i + tmp) & 1023;
   }
   clock_gettime(CLOCK_REALTIME, &endAccess); //end clock

   .. y, por supuesto, recuerda dividir el tiempo entre NUM_ACCESSES .
   Ahora, hice el índice intencionalmente complicado para evitar un paso fijo que podría desencadenar un captador previo (un poco exagerado, no es probable que note un impacto, pero por el bien de la demostración ...). Probablemente podría conformarse con un index += 32 simple index += 32 , que le daría pasos de 128k (dos líneas de caché), y evitaría el "beneficio" de la mayoría de los buscadores simples de línea adyacente / simple. También reemplacé el % 1000 con & 1023 ya que & es más rápido, pero debe ser potencia de 2 para que funcione de la misma manera, así que simplemente incremente ACCESS_SIZE a 1024 y debería funcionar.

2. Invalidar el L1 cargando algo diferente es bueno, pero los tamaños parecen divertidos. No especificó su sistema pero 256000 parece bastante grande para una L1. Un L2 suele ser 256k en muchas CPU modernas comunes x86 para, por ejemplo, también tenga en cuenta que 256k no es 256000 , sino más bien 256*1024=262144 . Lo mismo ocurre con el segundo tamaño: 1M no es 1024000 , es 1024*1024=1048576 . Suponiendo que es de hecho su tamaño L2 (más probable es que sea un L3, pero probablemente demasiado pequeño para eso).

3. Sus matrices invalidantes son de tipo int , por lo que cada elemento es más largo que un solo byte (lo más probable es 4 bytes, según el sistema). En realidad, está invalidando el valor de bytes de L1_CACHE_SIZE*sizeof(int) (y lo mismo ocurre con el ciclo de invalidación L2)

Actualizar:

1. memset recibe el tamaño en bytes, tus tamaños están divididos por sizeof(int)

2. Sus lecturas de invalidación nunca se utilizan y pueden optimizarse. Intente acumular las lecturas en algún valor e imprímalo al final, para evitar esta posibilidad.

3. El memset al principio también está accediendo a los datos, por lo que su primer bucle está accediendo a los datos de L3 (ya que los otros 2 conjuntos de archivos aún eran efectivos para expulsarlo de L1 + L2, aunque solo parcialmente debido al error de tamaño).

4. Los pasos pueden ser demasiado pequeños para que tenga acceso a la misma línea de caché (golpe L1). Asegúrate de que estén lo suficientemente extendidos al agregar 32 elementos (x4 bytes), eso es 2 cachelines, por lo que tampoco obtendrás ningún beneficio de captación previa de la línea de caché.

5. Como NUM_ACCESSES es más grande que ACCESS_SIZE, esencialmente estás repitiendo los mismos elementos y probablemente obtendrás L1 hits por ellos (por lo que el tiempo medio cambia a favor de la latencia de acceso L1). En su lugar, intente usar el tamaño L1 para acceder a todo el L1 (excepto los saltos) exactamente una vez. Por ejemplo, como este -

   index = 0;
   while (index < L1_CACHE_SIZE) {
   int tmp = arrayAccess[index]; //Access Value from L2
   index = (index + tmp + ((index & 4) ? 28 : 36)); // on average this should give 32 element skips, with changing strides
   count++; //divide overall time by this
   }

no se olvide de aumentar arrayAccess al tamaño L1.

Ahora, con los cambios anteriores (más o menos), obtengo algo como esto:

L1 Cache Access 7.812500
L2 Cache Acces 15.625000
L3 Cache Access 23.437500

Que todavía parece un poco largo, pero posiblemente porque incluye una dependencia adicional en las operaciones aritméticas

Answer 5

Prefiero tratar de usar el reloj de hardware como una medida. La instrucción rdtsc le dirá la cuenta actual del ciclo desde que la CPU se encendió. También es mejor usar asm para asegurarse de que siempre se usen las mismas instrucciones tanto en las carreras medidas como en las secas. Usando eso y algunas estadísticas inteligentes, hice esto hace mucho tiempo:

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
#include <sys/mman.h>
int i386_cpuid_caches (size_t * data_caches) {
int i;
int num_data_caches = 0;
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;
if (cache_type == 1 || cache_type == 3) {
data_caches[num_data_caches++] = cache_total_size;
}
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"
);
}
return num_data_caches;
}
int test_cache(size_t attempts, size_t lower_cache_size, int * latencies, size_t max_latency) {
int fd = open("/dev/urandom", O_RDONLY);
if (fd < 0) {
perror("open");
abort();
}
char * random_data = mmap(
NULL
, lower_cache_size
, PROT_READ | PROT_WRITE
, MAP_PRIVATE | MAP_ANON // | MAP_POPULATE
, -1
, 0
); // get some random data
if (random_data == MAP_FAILED) {
perror("mmap");
abort();
}
size_t i;
for (i = 0; i < lower_cache_size; i += sysconf(_SC_PAGESIZE)) {
random_data[i] = 1;
}
int64_t random_offset = 0;
while (attempts--) {
// use processor clock timer for exact measurement
random_offset += rand();
random_offset %= lower_cache_size;
int32_t cycles_used, edx, temp1, temp2;
asm (
"mfence/n/t" // memory fence
"rdtsc/n/t" // get cpu cycle count
"mov %%edx, %2/n/t"
"mov %%eax, %3/n/t"
"mfence/n/t" // memory fence
"mov %4, %%al/n/t" // load data
"mfence/n/t"
"rdtsc/n/t"
"sub %2, %%edx/n/t" // substract cycle count
"sbb %3, %%eax" // substract cycle count
: "=a" (cycles_used)
, "=d" (edx)
, "=r" (temp1)
, "=r" (temp2)
: "m" (random_data[random_offset])
);
// printf("%d/n", cycles_used);
if (cycles_used < max_latency)
latencies[cycles_used]++;
else
latencies[max_latency - 1]++;
}
munmap(random_data, lower_cache_size);
return 0;
}
int main() {
size_t cache_sizes[32];
int num_data_caches = i386_cpuid_caches(cache_sizes);
int latencies[0x400];
memset(latencies, 0, sizeof(latencies));
int empty_cycles = 0;
int i;
int attempts = 1000000;
for (i = 0; i < attempts; i++) { // measure how much overhead we have for counting cyscles
int32_t cycles_used, edx, temp1, temp2;
asm (
"mfence/n/t" // memory fence
"rdtsc/n/t" // get cpu cycle count
"mov %%edx, %2/n/t"
"mov %%eax, %3/n/t"
"mfence/n/t" // memory fence
"mfence/n/t"
"rdtsc/n/t"
"sub %2, %%edx/n/t" // substract cycle count
"sbb %3, %%eax" // substract cycle count
: "=a" (cycles_used)
, "=d" (edx)
, "=r" (temp1)
, "=r" (temp2)
:
);
if (cycles_used < sizeof(latencies) / sizeof(*latencies))
latencies[cycles_used]++;
else
latencies[sizeof(latencies) / sizeof(*latencies) - 1]++;
}
{
int j;
size_t sum = 0;
for (j = 0; j < sizeof(latencies) / sizeof(*latencies); j++) {
sum += latencies[j];
}
size_t sum2 = 0;
for (j = 0; j < sizeof(latencies) / sizeof(*latencies); j++) {
sum2 += latencies[j];
if (sum2 >= sum * .75) {
empty_cycles = j;
fprintf(stderr, "Empty counting takes %d cycles/n", empty_cycles);
break;
}
}
}
for (i = 0; i < num_data_caches; i++) {
test_cache(attempts, cache_sizes[i] * 4, latencies, sizeof(latencies) / sizeof(*latencies));
int j;
size_t sum = 0;
for (j = 0; j < sizeof(latencies) / sizeof(*latencies); j++) {
sum += latencies[j];
}
size_t sum2 = 0;
for (j = 0; j < sizeof(latencies) / sizeof(*latencies); j++) {
sum2 += latencies[j];
if (sum2 >= sum * .75) {
fprintf(stderr, "Cache ID %i has latency %d cycles/n", i, j - empty_cycles);
break;
}
}
}
return 0;
}

Salida en mi Core2Duo:

Cache ID 0:
- Level: 1
- Type: Data Cache
- Total Size: 32768 bytes (32 kb)
Cache ID 1:
- Level: 1
- Type: Instruction Cache
- Total Size: 32768 bytes (32 kb)
Cache ID 2:
- Level: 2
- Type: Unified Cache
- Total Size: 262144 bytes (256 kb)
Cache ID 3:
- Level: 3
- Type: Unified Cache
- Total Size: 3145728 bytes (3072 kb)
Empty counting takes 90 cycles
Cache ID 0 has latency 6 cycles
Cache ID 2 has latency 21 cycles
Cache ID 3 has latency 168 cycles