Измерение задержек кэша
Поэтому я пытаюсь измерить задержки кэша 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, и это изменится, когда они будут кэшированы / не кэшированы)
Может кто-нибудь подсказать мне, что я могу делать неправильно?
ОБНОВЛЕНИЕ 1: Таким образом, я амортизировал стоимость таймера, делая много обращений, я фиксировал размер своих кешей и также принимал совет, чтобы сделать более сложную схему индексации, чтобы избежать фиксированных шагов. К сожалению, времена еще не прошли. Кажется, все они идут на L1. Я думаю, что проблема может быть в том, чтобы сделать недействительным вместо доступа. Повлияет ли схема случайного выбора на LRU на данные, признанные недействительными?
ОБНОВЛЕНИЕ 2: Исправлен набор настроек mem (добавлен набор настроек L3, чтобы также сделать недействительными данные в L3, так что первый доступ начинается в основной памяти) и схему индексации, все еще не повезло.
ОБНОВЛЕНИЕ 3: я никогда не мог заставить этот метод работать, но были некоторые хорошие предложенные ответы, и я отправил несколько собственных решений.
Я также запустил Cachegrind для просмотра попаданий
==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 }
5 ответов
Я бы предпочел использовать аппаратные часы в качестве меры. 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
Широко используемый классический тест на задержку кеширования перебирает связанный список. Он работает на современном суперскалярном / суперпайплированном процессоре и даже на ядрах с неупорядоченным порядком, таких как ARM Cortex-A9+ и Intel Core 2/ix. Этот метод используется lmbench с открытым исходным кодом - в тесте lat_mem_rd ( man-страница) и в средстве измерения задержки 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 элементы вперед.
Как говорит справочная страница http://www.bitmover.com/lmbench/lat_mem_rd.8.html
Тест выполняется в виде двух вложенных циклов. Внешняя петля - размер шага. Внутренний цикл - это размер массива. Для каждого размера массива эталонный тест создает кольцо указателей, которые указывают на один шаг вперед. Обход массива выполняется
p = (char **)*p;
в цикле for (верхний цикл цикла for не имеет значения; цикл представляет собой развернутый цикл длиной 1000 загрузок). Цикл останавливается после выполнения миллиона загрузок. Размер массива варьируется от 512 байт до (обычно) восьми мегабайт. При небольших размерах кэш будет иметь эффект, и загрузка будет намного быстрее. Это становится намного более очевидным, когда данные наносятся на график.
Более подробное описание с примерами POWER доступно на вики-сайте IBM: Распутывание измерений доступа к памяти - 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 года:
Хорошо, несколько проблем с вашим кодом:
Как вы упомянули, ваши измерения занимают много времени. На самом деле, они, скорее всего, займут намного больше времени, чем сам единый доступ, поэтому они не измеряют ничего полезного. Чтобы уменьшить это, получите доступ к нескольким элементам и амортизируйте (разделите общее время на количество обращений. Обратите внимание, что для измерения задержки вы хотите, чтобы эти доступы были сериализованы, в противном случае они могут выполняться параллельно, и вы будете измерять только пропускную способность. несвязанных доступов. Чтобы достичь этого, вы можете просто добавить ложную зависимость между доступами.
Например, инициализируйте массив нулями и выполните:
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, что даст вам шаг в 128 Кб (две строки кэша) и позволит избежать "преимущества" большинства простых приставок для соседних строк / простых потоков. Я также заменил% 1000с& 1023поскольку&быстрее, но он должен быть степени 2, чтобы работать так же, так что просто увеличитьACCESS_SIZEдо 1024 и должно работать.Инвалидировать L1, загружая что-то еще, хорошо, но размеры выглядят забавно. Вы не указали свою систему, но
256000кажется довольно большим для L1. L2 обычно составляет 256 КБ на многих распространенных современных процессорах x86, например. Также обратите внимание, что 256 КБ не256000, скорее256*1024=262144, То же самое касается второго размера: 1M не1024000, его1024*1024=1048576, Предполагая, что это действительно ваш размер L2 (скорее всего, L3, но, вероятно, слишком мал для этого).Ваши недействительные массивы имеют тип
intпоэтому каждый элемент длиннее одного байта (скорее всего 4 байта, в зависимости от системы). Вы фактически лишаете законной силыL1_CACHE_SIZE*sizeof(int)стоимость байтов (то же самое касается цикла аннулирования L2)
Обновить:
memsetполучает размер в байтах, ваши размеры делятся наsizeof(int)Ваши чтения недействительности никогда не используются, и могут быть оптимизированы. Старайтесь накапливать чтения в некотором значении и печатать его в конце, чтобы избежать этой возможности.
Memset в начале также получает доступ к данным, поэтому ваш первый цикл обращается к данным из L3 (так как другие 2 memset по-прежнему были эффективны при удалении их из L1+L2, хотя только частично из-за ошибки размера.
Шаг может быть слишком маленьким, поэтому вы получаете два доступа к одной и той же кэш-линии (попадание L1). Убедитесь, что они достаточно распределены, добавив 32 элемента (x4 байта) - это 2 строки кэша, так что вы также не получите никаких преимуществ при предварительном извлечении смежных строк.
Поскольку NUM_ACCESSES больше, чем ACCESS_SIZE, вы, по сути, повторяете одни и те же элементы и, вероятно, получите для них попадания L1 (поэтому среднее время смещается в пользу задержки доступа 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
Который все еще кажется немного длинным, но, возможно, потому что он включает в себя дополнительную зависимость от арифметических операций
Не совсем ответ, но все равно прочитайте, кое-что уже упоминалось в других ответах и комментариях здесь
ну как раз на днях я отвечаю на этот вопрос:
речь идет об измерении L1/L2/.../L?/MEMORY скорость передачи взглянуть на это для лучшего начала вашей проблемы
[Заметки]
Я настоятельно рекомендую использовать инструкцию RDTSC для измерения времени
особенно для L1, поскольку все остальное слишком медленно. Не забудьте установить привязку процесса к одному процессору, потому что все ядра имеют свой счетчик, и их количество сильно отличается даже на одном входе Clock!!!
Настройте тактовую частоту процессора на максимум для компьютеров с переменной тактовой частотой и не забудьте учесть
RDTSCпереполнение, если вы используете только 32-битную часть (современный 32-битный счетчик переполнения процессора в секунду). Для расчета времени используйте часы процессора (измерьте его или используйте значение реестра)t0 <- RDTSC Sleep(250); t1 <- RDTSC CPU f=(t1-t0)<<2 [Hz]установить привязку процесса к одному процессору
все ядра ЦП обычно имеют свои собственные кэши L1,L2, поэтому в многозадачных ОС вы можете измерить запутанные вещи, если вы этого не сделаете
сделать графический вывод (диаграмма)
тогда вы увидите, что на самом деле происходит в этой ссылке выше, я разместил довольно много сюжетов
использовать самый высокий приоритет процесса, доступный ОС
Для тех, кто заинтересован, я не смог заставить работать свой первый код, поэтому я попробовал пару альтернативных подходов, которые дали приличные результаты.
В первом использовались связанные списки с узлами, расположенными в непрерывном пространстве памяти. Разыменование узлов снижает эффективность средства предварительной выборки, и в случае, когда несколько строк кэша извлекаются, я делаю шаги значительно большими, чтобы избежать попаданий в кэш. При увеличении размера выделенного списка он переходит к структуре кеша или памяти, в которой он хранится, показывая явное деление задержки.
#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);
}
Усредненный по многим испытаниям, этот метод также дал относительно точные результаты. Первый вариант, безусловно, лучший из двух, но это альтернативный подход, который также хорошо работает.