Cache-Latenzen messen

Question

Ich versuche also, die Latenzzeiten von L1-, L2- und L3-Caches mithilfe von C zu messen. Ich kenne die Größe der Caches und fühle, dass ich begrifflich verstehe, wie man das macht, aber ich habe Probleme mit meiner Implementierung. Ich frage mich, ob einige der anderen Hardware-Komplikationen wie das Prefetching Probleme verursachen.

#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
", 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
", 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
", 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
", L3Access); printf("Read Value: %d", readValue); }

Ich beginne damit, auf einen Wert in dem Array zuzugreifen, von dem ich Daten erhalten möchte. Dies sollte natürlich aus dem Hauptspeicher kommen, da es den ersten Zugriff gibt. Das Array ist klein (weniger als die Seitengröße) und sollte daher in L1, L2, L3 kopiert werden. Ich greife aus demselben Array auf den Wert zu, der jetzt L1 sein sollte. Ich greife dann auf alle Werte von einem Array mit der gleichen Größe wie L1-Cache zu, um die Daten zu annullieren, auf die ich zugreifen möchte (also jetzt nur in L2/3). Dann wiederhole ich diesen Vorgang für L2 und L3. Die Zugriffszeiten sind jedoch eindeutig aus, was bedeutet, dass ich etwas falsch mache ...

Ich denke, dass es Probleme mit der Zeit gibt, die es dauert, bis die Uhr läuft (Start und Stop werden einige Zeit in ns dauern und werden sich ändern, wenn sie zwischengespeichert/nicht im Cache gespeichert werden).

Kann mir jemand Hinweise geben, was ich falsch mache?

UPDATE1: Also habe ich die Kosten für den Timer amortisiert, indem ich viele Zugriffe vorgenommen habe, ich habe die Größe meiner Caches festgelegt und bin auch dem Rat gefolgt, ein komplexeres Indexierungsschema zu erstellen, um feste Schritte zu vermeiden. Leider sind die Zeiten immer noch abgelaufen. Sie scheinen alle für L1 zu kommen. Ich denke, das Problem könnte darin liegen, ungültig zu machen, anstatt darauf zuzugreifen. Würde ein zufälliges vs. LRU-Schema die ungültig gemachten Daten beeinflussen?

UPDATE2: Das Memset wurde korrigiert (L3-Memset wurde hinzugefügt, um Daten auch in L3 zu annullieren, sodass der erste Zugriff im Hauptspeicher beginnt) und das Indexierungsschema, immer noch kein Glück.

UPDATE3: Ich konnte diese Methode nie zum Laufen bringen, aber es gab einige gute Lösungsvorschläge und ich habe ein paar eigene Lösungen veröffentlicht.

Ich habe auch Cachegrind laufen lassen, um Treffer/Fehler anzuzeigen

 ==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
", 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
", 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
", 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
", L3Access); . . . . . . . . . 6 0 0 1 0 0 1 0 0 printf("Read Value: %d", readValue); . . . . . . . . . 3 0 0 3 0 0 0 0 0 }

Sergey L. · Accepted Answer

Ich würde eher versuchen, die Hardware-Uhr als Maßzahl zu verwenden. Die Anweisung rdtsc informiert Sie über den aktuellen Zykluswert seit dem Einschalten der CPU. Es ist auch besser, asm zu verwenden, um sicherzustellen, dass in gemessenen und trockenen Läufen immer die gleichen Anweisungen verwendet werden. Mit diesen und einigen cleveren Statistiken habe ich das vor langer Zeit gemacht:

#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:
" "- Level: %d
" "- Type: %s
" "- Sets: %d
" "- System Coherency Line Size: %d bytes
" "- Physical Line partitions: %d
" "- Ways of associativity: %d
" "- Total Size: %zu bytes (%zu kb)
" "- Is fully associative: %s
" "- Is Self Initializing: %s
" "
" , 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
	" // memory fence "rdtsc
	" // get cpu cycle count "mov %%edx, %2
	" "mov %%eax, %3
	" "mfence
	" // memory fence "mov %4, %%al
	" // load data "mfence
	" "rdtsc
	" "sub %2, %%edx
	" // 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
", 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
	" // memory fence "rdtsc
	" // get cpu cycle count "mov %%edx, %2
	" "mov %%eax, %3
	" "mfence
	" // memory fence "mfence
	" "rdtsc
	" "sub %2, %%edx
	" // 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
", 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
", i, j - empty_cycles); break; } } } return 0; }

Ausgabe auf meinem 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

Leeor · Answer

Ok, mehrere Probleme mit Ihrem Code:

Wie Sie erwähnt haben, dauert Ihre Messung sehr lange. Tatsächlich dauern sie sehr viel länger als der Einzelzugriff selbst, sodass sie nichts Nützliches messen. Um dies zu mildern, greifen Sie auf mehrere Elemente zu und amortisieren Sie sich (dividieren Sie die Gesamtzeit durch die Anzahl der Zugriffe. Beachten Sie, dass Sie zur Messung der Latenz diese Zugriffe serialisieren möchten, andernfalls können sie parallel ausgeführt werden, und Sie messen nur den Durchsatz Um dies zu erreichen, können Sie einfach eine falsche Abhängigkeit zwischen den Zugriffen hinzufügen.

Initialisieren Sie beispielsweise das Array mit Nullen, und führen Sie Folgendes aus:
```
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 
```
.. und natürlich vergessen Sie nicht, die Zeit durch NUM_ACCESSES zu teilen.
Nun, ich habe den Index absichtlich kompliziert gemacht, so dass Sie einen festen Schritt vermeiden, der einen Prefetcher auslösen könnte (ein bisschen Overkill, Sie werden wahrscheinlich keinen Aufprall bemerken, sondern der Demonstration wegen) ...). Sie könnten sich wahrscheinlich mit einem einfachen index += 32 zufrieden geben, der Ihnen 128k (zwei Cache-Zeilen) ermöglicht und den "Vorteil" der meisten einfachen angrenzenden Zeilen/einfachen Stream-Prefetchers vermeidet. Ich habe auch % 1000 durch & 1023 ersetzt, da & schneller ist, aber es muss eine Potenz von 2 sein, um auf dieselbe Weise zu arbeiten - erhöhen Sie einfach ACCESS_SIZE auf 1024 und es sollte funktionieren.
Es ist gut, die L1 durch Laden etwas anderes zu stornieren, aber die Größen sehen komisch aus. Sie haben Ihr System nicht angegeben, aber 256000 scheint für eine L1 ziemlich groß zu sein. Ein L2 ist normalerweise 256k auf vielen gängigen modernen x86-CPUs für z. Beachten Sie auch, dass 256k nicht 256000 ist, sondern 256*1024=262144. Gleiches gilt für die zweite Größe: 1M ist nicht 1024000, sondern 1024*1024=1048576. Angenommen, das ist tatsächlich Ihre L2-Größe (wahrscheinlicher eine L3, aber dafür wahrscheinlich zu klein).
Ihre ungültigen Arrays sind vom Typ int, daher ist jedes Element länger als ein einzelnes Byte (höchstwahrscheinlich 4 Byte, je nach System). Sie machen tatsächlich den Wert von L1_CACHE_SIZE*sizeof(int) für Bytes ungültig (und dasselbe gilt für die L2-Invalidierungsschleife).

Aktualisieren:

memset erhält die Größe in Bytes, Ihre Größen werden durch sizeof(int) geteilt.
Ihre Invalidierungslesevorgänge werden nie verwendet und können optimiert werden. Versuchen Sie, die Lesevorgänge in einem Wert zu sammeln und am Ende zu drucken, um diese Möglichkeit zu vermeiden.
Das Memset am Anfang greift auch auf die Daten zu, daher greift Ihre erste Schleife auf Daten vom L3 zu (da die anderen 2 Memsets noch wirksam waren, um sie von L1 + L2 zu entfernen, obwohl dies nur teilweise auf den Größenfehler zurückzuführen ist).
Die Schritte sind möglicherweise zu klein, sodass Sie zwei Zugriff auf dieselbe Cache-Linie erhalten (L1-Treffer). Vergewissern Sie sich, dass sie ausreichend verteilt sind, indem Sie 32 Elemente (x4 Bytes) hinzufügen. Dies sind zwei Cache-Linien, sodass Sie auch keine Vorzüge des benachbarten Cache-Vorablesezugriffs erhalten.
Da NUM_ACCESSES größer als ACCESS_SIZE ist, wiederholen Sie im Wesentlichen die gleichen Elemente und würden wahrscheinlich L1-Treffer für sie erhalten (daher verschiebt sich die durchschnittliche Zeit zugunsten der L1-Zugriffslatenz). Verwenden Sie stattdessen die L1-Größe, damit Sie genau einmal auf die gesamte L1 (mit Ausnahme der Übersprungen) zugreifen. Für z. so was -
```
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 } 
```

vergessen Sie nicht, arrayAccess auf L1 zu vergrößern.

Nun, mit den oben genannten Änderungen (mehr oder weniger), bekomme ich so etwas:

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

Was immer noch etwas lang erscheint, aber möglicherweise, weil es eine zusätzliche Abhängigkeit von Rechenoperationen enthält

osgx · Answer

Der häufig verwendete klassische Test für die Cache-Latenzzeit durchläuft die verknüpfte Liste. Es funktioniert auf modernen Superscalar/Superpipeline-CPUs und sogar auf Out-of-Order-Cores wie ARM Cortex-A9 + und Intel Core 2/ix. Diese Methode wird von Open-Source-lmbench verwendet - im Test lat_mem_rd ( man page ) und im Tool zur Messung der CPU-Z-Latenzzeit: http://cpuid.com/medias/files/softwares/misc/latency .Zip (native Windows-Binärdatei)

Es gibt Quellen für den lat_mem_rd-Test von lmbench: https://github.com/foss-for-synopsys-dwc-arc-processors/lmbench/blob/master/src/lat_mem_rd.c

Und der Haupttest ist

#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; }

Nachdem wir das Makro entschlüsselt haben, führen wir viele lineare Operationen durch, wie:

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

über dem Speicher, gefüllt mit Zeigern, werden alle stride-Elemente nach vorne gerichtet.

Wie sagt die Manpage http://www.bitmover.com/lmbench/lat_mem_rd.8.html

Der Benchmark läuft als zwei verschachtelte Schleifen. Die äußere Schleife ist die Schrittgröße. Die innere Schleife ist die Arraygröße. Für jede Arraygröße erstellt der Benchmark einen Zeigerring, der einen Schritt nach vorne zeigt. Das Durchfahren des Arrays erfolgt durch

 p = (char **)*p;

in einer for-Schleife (der Overhead der for-Schleife ist nicht signifikant; die Schleife ist eine abgewickelte Schleife, die 1000 lange lädt). Die Schleife stoppt nach einer Million Ladevorgänge. Die Größe des Arrays variiert zwischen 512 Byte und (normalerweise) acht Megabyte. Bei kleinen Größen wirkt sich der Cache-Speicher aus und das Laden wird wesentlich schneller. Dies wird deutlich deutlicher, wenn die Daten aufgezeichnet werden.

Eine ausführlichere Beschreibung mit Beispielen zu POWERs finden Sie im IBM-Wiki: Deaktivieren der Speicherzugriffsmessungen - lat_mem_rd - von Jenifer Hopper 2013

Der lat_mem_rd-Test ( http://www.bitmover.com/lmbench/lat_mem_rd.8.html ) benötigt zwei Argumente, eine Array-Größe in MB und eine Schrittweite. Der Benchmark verwendet zwei Schleifen, um das Array zu durchlaufen, wobei der Schritt als Inkrement verwendet wird, indem ein Zeigerring erstellt wird, der einen Schritt nach vorne zeigt. Der Test misst die Speicherleselatenz in Nanosekunden für den Bereich der Speichergrößen. Die Ausgabe besteht aus zwei Spalten: Die erste ist die Array-Größe in MB (der Gleitkommawert) und die zweite ist die Ladelatenz für alle Punkte des Arrays. Wenn die Ergebnisse grafisch dargestellt werden, können Sie die relativen Latenzzeiten der gesamten Speicherhierarchie einschließlich der schnelleren Latenzzeit für jede Cache-Ebene und der Hauptspeicherlatenz deutlich erkennen.

PS: Es gibt Papier von Intel (Dank an Eldar Abusalimov ) mit Beispielen für das Ausführen von lat_mem_rd: ftp://download.intel.com/design/intarch/PAPERS/321074.pdf - sorry, rechte URL ist http://www.intel.com/content/dam/www/public/us/de/documents/white-papers/ia-cache-latency-bandwidth-paper.pdf " Messen der Cache- und Speicherlatenz und der CPU-zu-Speicher-Bandbreite - Zur Verwendung mit Intel-Architektur "von Joshua Ruggiero aus Dezember 2008:

Spektre · Answer

Nicht wirklich eine Antwort, aber trotzdem gelesen, wurde in anderen Antworten und Kommentaren hier bereits etwas erwähnt

nun, gerade neulich beantworte ich diese Frage:

Cache-Größenschätzung auf Ihrem System?

es geht um die Messung von L1/L2/.../L?/MEMORY Übertragungsraten. Betrachten Sie es für einen besseren Startpunkt Ihres Problems

[Notizen]

Ich empfehle dringend die Verwendung des RDTSC-Befehls zur Zeitmessung

besonders für L1 da alles andere zu langsam ist. Vergessen Sie nicht, die Prozessaffinität auf singleCPUzu setzen, da alle Kerne einen eigenen Zähler haben und ihre Zählung selbst bei gleichem Eingangstakt sehr unterschiedlich ist !!!

Stellen Sie dieCPUclock für Computer mit variabler Uhr auf Maximum ein, und vergessen Sie nicht, den Überlauf RDTSC zu berücksichtigen, wenn Sie nur einen 32-Bit-Teil verwenden (moderner CPU-Überlauf-32-Bit-Zähler in einer Sekunde). Für die Zeitberechnung verwenden Sie die CPU-Uhr (messen oder verwenden Sie den Registrierungswert).
```
t0 <- RDTSC Sleep(250); t1 <- RDTSC CPU f=(t1-t0)<<2 [Hz] 
```
Prozessaffinität auf einzelne CPU setzen

alleCPU-Kerne haben normalerweise ihre eigenen L1, L2 caches. Bei Multi-TaskOSkönnen Sie verwirrende Dinge messen, wenn Sie dies nicht tun
Grafische Ausgabe machen (Diagramm)

dann werden Sie sehen, was in diesem Link tatsächlich passiert. Ich habe einige Plots gepostet
höchste Prozesspriorität des Betriebssystems verwenden

PandaRaid · Answer

Nun, für Interessierte konnte ich meinen ersten Code nicht zum Laufen bringen, also probierte ich ein paar alternative Ansätze aus, die zu anständigen Ergebnissen führten.

Die ersten verwendeten verknüpften Listen mit Knoten, die in einem zusammenhängenden Speicherbereich nebeneinander nebeneinander liegen. Durch die Dereferenzierung der Knoten wird die Effektivität des Vorabrufs verringert. Wenn mehrere Cache-Zeilen eingezogen werden, habe ich die Schritte beträchtlich groß gemacht, um Cache-Treffer zu vermeiden. Wenn die Größe der zugewiesenen Liste zunimmt, springt sie zu der Cache- oder Speicherstruktur, in der die Latenz deutlich angezeigt wird.

#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	%Lf
", accessTime, size); //print results to file fclose(fp); //close file }

Dies führte zu den konsistentesten Ergebnissen, und die Verwendung verschiedener Array-Größen und das Aufzeichnen der jeweiligen Latenzen ergab eine klare Unterscheidung der verschiedenen vorhandenen Cache-Größen.

Die nächste Methode wie die zuvor zugewiesenen Arrays mit zunehmender Größe. Anstatt eine verknüpfte Liste für den Speicherzugriff zu verwenden, fülle ich jeden Index mit der entsprechenden Nummer und mischte das Array zufällig. Diese Indexe habe ich dann verwendet, um innerhalb des Arrays für Zugriffe zufällig herumzuspringen und die Auswirkungen des Vorabrufs zu mildern. Es gab jedoch gelegentlich starke Abweichungen in der Zugriffszeit, wenn mehrere benachbarte Cache-Zeilen eingezogen wurden und zufällig getroffen wurden.

#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
", accessTime, size); }

Über viele Studien hinweg gemittelt, lieferte diese Methode auch relativ genaue Ergebnisse. Die erste Wahl ist definitiv die bessere der beiden, aber dies ist ein alternativer Ansatz, der auch gut funktioniert.