Определить ассоциативность кэша процессора

Question

Я пытаюсь определить ассоциативность моего процессора.У меня Intel Core i5-2500:

Данные L1: 32 КБ, 8-полосный ассоциативный набор

L1 Инструкция: 32 КБ, 8-канальный ассоциативный набор

L2:256 Кб, ассоциативный набор с 8 путями

L3: 6 МБ, ассоциативный набор с 12 путями, общий для всех ядер

Я измеряю среднее время доступа к элементу массива в тактах процессора,Массив разбит на фрагменты.

В цикле я увеличиваю количество фрагментов.Расстояние между двумя соседними фрагментами равно размеру кэша L3.Я получаю доступ к первым элементам всех фрагментов, затем ко вторым элементам и так далее.Каждый элемент содержит индекс следующего элемента.Последний элемент содержит индекс первого.

Это выглядит так: введите здесь описание изображения

Когда количество фрагментов будет больше, чем ассоциативность кэша,среднее время доступа должно увеличиться.

Я получил следующие результаты: введите описание изображения здесь

Первый переход соответствует ассоциативности TLB, второй соответствует ассоциативности L1и кэш-память L2, но я не понимаю, почему после превышения ассоциативности кэш-памяти L3 время не увеличивается.

Я также пробовал разные размеры и смещения

Я что-то не так делаю?Или у меня есть ошибки в коде?

Не могли бы вы объяснить это мне.Вот код:

#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE 6291456  //6 Mb
#define OFFSET 6291456
#define ROUNDS 200
#define MIN_FRAGMENTS_COUNT 1
#define MAX_FRAGMENTS_COUNT 32

void FreeArray(int* array, int size) {
  assert(size > 0 && "Size must be gerater than zero\n");

  if (NULL == array) {
    return;
  }

  for (int i = 0; i < size; ++i) {
    array[i] = 0;
  }
  free(array);
}

int* CreateArray(int size) {
  assert(size > 0 && "Size must be greater than zero\n");

  return calloc(size, sizeof(int));
}

unsigned long long int GetTicksCount(void) {
  unsigned int high = 0;
  unsigned int low = 0;

  __asm__ __volatile__("rdtsc" : "=a"(low), "=d"(high));
  return (((unsigned long long int)high) << 32 | (unsigned long long int)low);
}

void SetIndexes(int* array, int fragment_size, int offset,
                int fragments_count) {
  assert(NULL != array && "Pointer to array must not be NULL\n");
  assert(fragment_size > 0 && "Fragmnet size must be greater than zero\n");
  assert(offset > 0 && "Offset must be greater than zero\n");
  assert(fragments_count > 0 && "Fragments count must be greater than zero\n");
  assert(fragment_size <= offset &&
         "Fragment size must not be greater than offset\n");

  int last_fragment = fragments_count - 1;
  int last_element = fragment_size - 1;

  for (int i = 0; i < last_element; ++i) {
    for (int j = 0; j < last_fragment; ++j) {
      array[j * offset + i] = (j + 1) * offset + i;  //Go in the same element of next fragment
    }
    array[last_fragment * offset + i] = i + 1;  // Go in the next element from last fragment
  }
  array[last_fragment * offset + last_element] = 0; // Go in first element from last element
}

unsigned long long int CalcAccessTime(int* array, int size) {
  assert(NULL != array && "Pointer to array must not be NULL\n");
  assert(size > 0 && "Size must be greater than zero\n");          

  unsigned long long int start = 0;
  unsigned long long int end = 0;
  unsigned long long int min_time = ULLONG_MAX;
  int index = 0;  

  for (int i = 0; i < ROUNDS; ++i) {
    start = GetTicksCount();
    for (int j = 0; j < size; ++j) {
      index = array[index];
    }
    end = GetTicksCount();

    unsigned long long int cur_time = (end - start) / size;

    if (cur_time < min_time) {
      min_time = cur_time;
    }
  }
  return min_time;
}

int main(int argc, char** argv) {
  int integers_count = SIZE / sizeof(int);
  int offset_int = OFFSET / sizeof(int);

  for (int i = MIN_FRAGMENTS_COUNT; i <= MAX_FRAGMENTS_COUNT; ++i) {
    int size = i * offset_int;
    int* array = CreateArray(size);

    if (NULL == array) {
      return -1;
    }

    SetIndexes(array, integers_count / i, offset_int, i);

    printf("Fragments: %d\n", i);
    printf("Time: %llu\n", CalcAccessTime(array, integers_count));

    FreeArray(array, size);
  }
  return 0;
}

Answer 1

В отличие от основных кэшей, LLC имеет дополнительный уровень отображения наборов.

Обычно вы не хотите, чтобы целые области памяти отображались в смежные наборы в одном и том же слайсе LLC, потому что тогда ядро, которое находится далеко от этого слайса, будет иметь ужасное время доступа.Вместо этого для общего случая вы хотите, чтобы ваши данные были распределены как можно более равномерно.Чтобы достичь этого, они добавили хеш-функцию как часть отображения, которое определило срез.

Исключением являются случаи использования, когда вы хотите, чтобы то, что называется «кластеризация под NUMA» или «ядро-кластеризация» - вВ этих случаях вы можете переопределить это распределение с помощью явной конфигурации.

Хеширование должно работать и на старших битах, чтобы лучше распределять области памяти, поэтому пропуск по размеру LLC не будет работать.Вы по-прежнему приземляетесь на один и тот же набор в нескольких срезах, что означает, что вы эффективно получаете ассоциативность, умноженную на количество срезов.Однако, в зависимости от выравнивания структуры, вы не обязательно получите оптимальное распределение, поэтому вы можете начать видеть скачки перед этим уровнем ассоциативности.

Вот статья с некоторыми подробностями о хешировании срезов: https://arxiv.org/pdf/1508.03767.pdf