Влияние размера кэша на код

Question

Я хочу изучить влияние размера кеша на код. Для программ, работающих на больших массивах, может произойти значительное ускорение, если массив вписывается в кеш.

Как я могу уверить это?

Я попытался запустить эту гр программу:

#define L1_CACHE_SIZE  32  // Kbytes 8192 integers 
#define L2_CACHE_SIZE  256  // Kbytes 65536 integers 
#define L3_CACHE_SIZE  4096 // Kbytes 

#define ARRAYSIZE 32000 
#define ITERATIONS 250 

int arr[ARRAYSIZE]; 

/*************** TIME MEASSUREMENTS ***************/ 

double microsecs() { 
    struct timeval t; 
    if (gettimeofday(&t, NULL) < 0) 
    return 0.0; 
    return (t.tv_usec + t.tv_sec * 1000000.0);  
} 

void init_array() { 
    int i; 
    for (i = 0; i < ARRAYSIZE; i++) { 
     arr[i] = (rand() % 100); 
    } 
} 

int operation() { 
    int i, j; 
    int sum = 0; 
    for (j = 0; j < ITERATIONS; j++) { 
     for (i = 0; i < ARRAYSIZE; i++) { 
      sum =+ arr[i]; 
     } 
    } 

    return sum; 
} 

void main() { 

    init_array(); 

    double t1 = microsecs(); 
    int result = operation(); 
    double t2 = microsecs(); 

    double t = t2 - t1; 

    printf("CPU time %f milliseconds\n", t/1000); 
    printf("Result: %d\n", result);  
} 

принимая значения ARRAYSIZE и итерации (хранение продукта, и, следовательно, количество инструкций, постоянное), чтобы проверить, если запустить программу быстрее, если массив вписывается в кеш, но я всегда получаю одинаковое время процессора.

Может ли кто-нибудь сказать, что я делаю неправильно?

Answer 1

В коде есть опечатка. = + вместо + =.

Answer 2

Массив arr связан с разделом BSS [неинициализированный]. Значение по умолчанию для переменных в этом разделе равно нулю. Все страницы в этом разделе первоначально отображаются R/O на одномzero page. Это linux/Unix, но, вероятно, относится к большинству современных ОС.

Таким образом, независимо от размера массива вы получаете только одну страницу, которая будет кэшироваться, поэтому вы получаете те же результаты ,

Перед выполнением тестов вам нужно сломать «нулевое отображение страниц», написав что-то всем arr. То есть сначала сделайте что-то вроде memset. Это заставит ОС создать линейное сопоставление страниц для arr с использованием механизма COW (copy-on-write).

Answer 3

Что вы действительно хотите сделать, так это построить «гору памяти». Гора памяти помогает визуализировать, как доступ к памяти влияет на производительность программы. В частности, он измеряет пропускную способность чтения и пространственную локальность и временную локальность. Хорошая пространственная локальность означает, что последовательные обращения к памяти находятся рядом друг с другом, а хорошая временная локальность означает, что определенное место памяти доступно несколько раз за короткое время. Вот a link, который кратко упоминает производительность кеша и горы памяти. 3-е издание учебника, упомянутое в этой ссылке, является очень хорошей ссылкой, особенно в главе 6, для изучения производительности памяти и кеша. (На самом деле, я в настоящее время использую этот раздел в качестве ссылки, как я отвечу на этот вопрос.)

другого link показывает тестовую функцию, что вы могли бы использовать для измерения производительности кэша, который я скопированная здесь:

void test(int elems, int stride) 
{ 
    int i, result = 0; 
    volatile int sink; 
    for (i = 0; i < elems; i+=stride) 
     result += data[i]; 
    sink = result; 
} 

Stride - это временная локальность - насколько далеко друг от друга доступ к памяти. Идея состоит в том, что эта функция будет оценивать количество циклов, которые потребовались для запуска. Чтобы получить пропускную способность, вы хотите взять (размер/шаг)/(циклы/МГц), где размер - это размер массива в байтах, циклы - результат этой функции, а МГц - это тактовая частота вашего процессора , Вы хотите вызвать это один раз, прежде чем выполнять какие-либо измерения, чтобы «разогреть» ваш кеш. Затем запустите цикл и выполните измерения.

Я нашел GitHub repository, который вы могли бы использовать для создания 3D-памяти на своей машине. Я рекомендую вам попробовать его на нескольких машинах с разными процессорами и сравнить различия.