Измерение латентности кэша
Итак, я пытаюсь измерить задержки кеша L1, L2, L3, используя C. Я знаю их размер, и я чувствую, что понимаю концептуально, как это сделать, но у меня возникают проблемы с моей реализацией. Мне интересно, возникают ли некоторые из других аппаратных сложностей, таких как предварительная выборка.
#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);
}
Я начинаю с обращения к значению в массиве, из которого я хочу получить данные. Очевидно, это должно происходить из основной памяти, потому что это первый доступ. Массив небольшой (меньше размера страницы), поэтому его нужно скопировать в L1, L2, L3. Я получаю доступ к значению из того же массива, который теперь должен быть L1. Затем я получаю доступ ко всем значениям из массива того же размера, что и кэш L1, чтобы аннулировать данные, к которым я хочу получить доступ (так что теперь он должен быть только в L2/3). Затем я повторяю этот процесс для L2 и L3. Время доступа явно отключено, что означает, что я делаю что-то неправильно...
Я думаю, что могут возникнуть проблемы с временем, затрачиваемым на часы (запуск и остановка займет некоторое время в ns, и это изменится, когда они будут сохранены в кэше /unchached )
Может ли кто-нибудь дать мне несколько указаний на то, что я могу сделать неправильно?
UPDATE1: Таким образом, я амортизировал стоимость таймера, сделав много доступа, я установил размер своих кешей, и я также принял решение сделать более сложную схему индексирования, чтобы избежать фиксированных шагов. К сожалению, время все еще выключено. Кажется, все они подходят к L1. Я думаю, что проблема может заключаться в недействительности, а не в доступе. Может ли случайная схема LRU повлиять на данные, которые недействительны?
UPDATE2: Исправлено memset (добавлено memset L3 для недействительности данных в L3, так что первый доступ начинается в основной памяти) и схема индексирования, все еще не удача.
UPDATE3: я не мог заставить этот метод работать, но были некоторые полезные ответы, и я опубликовал пару своих решений.
Я также запускал Cachegrind для просмотра hit/miss
==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 }
Ответы
Ответ 1
Я бы скорее попытался использовать аппаратные часы в качестве меры. Команда rdtsc
сообщит вам текущий счет цикла с момента включения процессора. Также лучше использовать asm
, чтобы всегда использовать одни и те же инструкции как в измеренных, так и в сухих пробегах. Используя эту и некоторые умные статистические данные, я сделал это давным-давно:
#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;
}
Вывод на моем 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
Ответ 2
Хорошо, несколько проблем с кодом:
-
Как вы упомянули, ваши измерения занимают много времени. Фактически, они, скорее всего, уйдут дольше, чем единственный доступ, поэтому они не измеряют ничего полезного. Чтобы уменьшить это, выполните доступ к нескольким элементам и амортизируйте (разделите общее время на количество обращений. Обратите внимание, что для измерения задержки вы хотите, чтобы эти обращения были сериализованы, в противном случае они могут выполняться параллельно, и вы будете только измерять пропускную способность от несвязанных доступов. Для этого вы можете просто добавить ложную зависимость между обращениями.
Например, инициализируйте массив нулями и выполните:
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
.. и, конечно, не забудьте разделить время на NUM_ACCESSES
.
Теперь я сделал индекс намеренно сложным, так что вы избегаете фиксированного шага, который может вызвать предборщик (немного перебор, вы вряд ли заметите удар, но ради демонстрации...). Вероятно, вы можете согласиться на простой index += 32
, который даст вам шаги 128k (две строки кэша) и избежит "преимущества" большинства простых смежных линейных/простых потоковых префетов. Я также заменил % 1000
на & 1023
, так как &
работает быстрее, но для того, чтобы он работал так же, он должен быть равен 2, поэтому просто увеличьте ACCESS_SIZE
до 1024 и он должен работать.
-
Недействительность L1 при загрузке чего-то еще хороша, но размеры выглядят забавно. Вы не указали свою систему, но 256000
кажется довольно большим для L1. L2 обычно составляет 256 тыс. На многих современных современных процессорах x86, например. Также обратите внимание, что 256k не 256000
, а скорее 256*1024=262144
. То же самое касается второго размера: 1M не 1024000
, it 1024*1024=1048576
. Предположим, что действительно ваш размер L2 (скорее, L3, но, вероятно, слишком мал для этого).
-
Ваши недействительные массивы имеют тип int
, поэтому каждый элемент длиннее одного байта (скорее всего, 4 байта, в зависимости от системы). Вы фактически недействительны L1_CACHE_SIZE*sizeof(int)
значение байтов (и то же самое относится к циклу аннулирования L2)
Обновление:
-
memset
получает размер в байтах, ваши размеры делятся на sizeof(int)
-
Ваши объявления о недействительности никогда не используются и могут быть оптимизированы. Попытайтесь аккумулировать чтение в некотором значении и напечатать его в конце, чтобы избежать этой возможности.
-
Вначале memset также получает доступ к данным, поэтому ваш первый цикл обращается к данным из L3 (поскольку остальные 2 memsets все еще эффективны для выселения из L1 + L2, хотя частично из-за ошибка размера.
-
Шаги могут быть слишком маленькими, поэтому вы получаете два доступа к одной и той же линии (L1 hit). Убедитесь, что они достаточно распространены, добавив 32 элемента (x4 байта) - 2 кэш-линии, поэтому вы также не получите каких-либо смежных преимуществ предварительной выборки кешлайн.
-
Поскольку NUM_ACCESSES больше ACCESS_SIZE, вы, по существу, повторяете одни и те же элементы и, вероятно, получите для них L1-хиты (поэтому время avg сдвигается в пользу задержки доступа L1). Вместо этого попробуйте использовать размер L1, чтобы получить доступ ко всему L1 (за исключением пропусков) ровно один раз. Напр. как это -
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
}
не забудьте увеличить размер arrayAccess
до L1.
Теперь, с изменениями выше (более или менее), я получаю что-то вроде этого:
L1 Cache Access 7.812500
L2 Cache Acces 15.625000
L3 Cache Access 23.437500
Это все еще кажется немного длинным, но возможно потому, что оно включает дополнительную зависимость от арифметических операций
Ответ 3
Широко используемый классический тест для латентности кэша выполняет итерацию по связанному списку. Он работает на современных суперскалярных/суперпипелированных процессорах и даже на ядрах вне порядка, таких как ARM Cortex-A9 + и Intel Core 2/ix. Этот метод используется open-source lmbench - в тесте lat_mem_rd
(справочная страница) и в инструменте измерения задержки CPU-Z: http://cpuid.com/medias/files/softwares/misc/latency.zip (собственный двоичный файл Windows)
Есть источники теста lat_mem_rd из lmbench: https://github.com/foss-for-synopsys-dwc-arc-processors/lmbench/blob/master/src/lat_mem_rd.c
И главное испытание
#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;
}
Итак, после расшифровки макроса мы выполняем много линейных операций, таких как:
p = (char**) *p; // (in intel syntax) == mov eax, [eax]
p = (char**) *p;
p = (char**) *p;
.... // 100 times total
p = (char**) *p;
над памятью, заполненной указателями, каждый из которых указывает на элементы stride
вперед.
Как говорится в man-странице http://www.bitmover.com/lmbench/lat_mem_rd.8.html
Тест работает как два вложенных цикла. Внешний цикл - это размер шага. Внутренний цикл - это размер массива. Для каждого размера массива эталонный показатель создает кольцо указателей, указывающих вперед один шаг. Перемещение массива выполняется с помощью
p = (char **)*p;
в цикле for (надголовок цикла for не имеет значения, цикл - развернутый цикл 1000 загрузок). Цикл прекращается после выполнения миллиона загрузок. Размер массива варьируется от 512 байт до (обычно) восьми мегабайт. Для небольших размеров кеш будет иметь эффект, а нагрузки будут намного быстрее. Это становится намного более очевидным, когда данные отображаются.
Более подробное описание с примерами на POWER можно найти в IBM wiki: Недопустимые измерения доступа к памяти - lat_mem_rd - Jenifer Hopper 2013
Тест lat_mem_rd (http://www.bitmover.com/lmbench/lat_mem_rd.8.html) принимает два аргумента: размер массива в МБ и размер шага. В тесте используется два цикла для прохождения через массив, используя шаг в качестве приращения, создавая кольцо указателей, указывающих вперед на один шаг. Тест измеряет задержку считывания памяти в наносекундах для диапазона размеров памяти. Вывод состоит из двух столбцов: первый - размер массива в МБ (значение с плавающей запятой), а второй - латентность загрузки по всем точкам массива. Когда результаты отображаются, вы можете четко видеть относительные задержки всей иерархии памяти, включая более высокую задержку каждого уровня кеша и задержку основной памяти.
PS: Есть бумага от Intel (благодаря Эльдар Абуласимов) с примерами запуска lat_mem_rd: ftp://download.intel.com/design/intarch/PAPERS/321074.pdf - извините правильный url http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-cache-latency-bandwidth-paper.pdf
"Измерение кэша и задержки памяти и пропускной способности ЦП для пропускной способности памяти - для использования с архитектурой Intel" Джошуа Руджиеро с декабря 2008 года:
Ответ 4
На самом деле не ответ, но прочитанный, в любом случае, некоторые вещи уже упоминались в других ответах и комментариях здесь.
ну как раз на днях я отвечаю на этот вопрос:
речь идет о измерении скоростей передачи L1/L2/.../L?/MEMORY
, чтобы лучше понять начальную точку вашей проблемы.
[Примечание]
-
Я настоятельно рекомендую использовать инструкцию RDTSC для измерения времени
особенно для L1, поскольку что-то еще слишком медленно. Не забудьте установить близость процесса к одиночному CPU, потому что у всех ядер есть свой счетчик, и их количество сильно отличается даже от того же самого входа Clock!!!
Настройте часы CPU на Максимальные для компьютеров с переменной частотой и не забывайте учитывать переполнение RDTSC
, если вы используете только 32-разрядную часть (современный 32-разрядный счетчик переполнения процессора в секунду). Для вычисления времени используйте часы процессора (измерьте его или используйте значение реестра)
t0 <- RDTSC
Sleep(250);
t1 <- RDTSC
CPU f=(t1-t0)<<2 [Hz]
-
установить близость процесса к одиночному процессору
все ядра CPU обычно имеют свои собственные L1, L2 кеши, поэтому в многозадачной ОС вы можете измерить запутывающие вещи, если не сделайте это
-
сделать графический вывод (диаграмма)
то вы увидите, что на самом деле происходит в этой ссылке выше. Я разместил довольно много графиков
-
использовать наивысший приоритет процесса, доступный ОС
Ответ 5
Хорошо для тех, кого это интересует, я не мог заставить свой первый набор кодов работать, поэтому я попробовал пару альтернативных подходов, которые дали достойные результаты.
Первыми используемыми связанными списками с узлами, выделенными шагами stride в отдельном пространстве памяти. Разделение узлов снижает эффективность предварительного ввода, а в случае, когда несколько строк кэша вытягиваются, я сделал шаги значительно большими, чтобы избежать попадания кеша. По мере увеличения размера выделенного списка он переходит к структуре кэша или памяти, которая будет удерживать его, показывая четкие деления в латентности.
#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
}
Это обеспечило самые последовательные результаты, и использование различных размеров массивов и построение соответствующих задержек дали очень четкое различие в различных размерах кеша.
Следующий метод, подобный предыдущим выделенным массивам увеличения размера. Но вместо того, чтобы использовать связанный список для доступа к памяти, я заполняю каждый индекс своим соответствующим номером и случайным образом перетасовывал массив. Затем я использовал эти индексы для случайного перемешивания в массиве для доступа, смягчая эффекты предварительного захвата. Тем не менее, он имел случайное сильное отклонение в времени доступа, когда несколько соседних строк кэша были втянуты и попали в него.
#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);
}
Усредненный во многих испытаниях, этот метод также дал относительно точные результаты. Первый выбор, безусловно, лучший из двух, но это альтернативный подход, который отлично работает.