C Программа для определения уровней и размера кеша

Ответ 1

Время, затрачиваемое на измерение вашего времени (то есть время просто вызова функции clock()), очень много (много многих...) раз больше времени, необходимого для выполнения arr[(i*16)&lengthMod]++, Это чрезвычайно низкое отношение сигнал/шум (среди других возможных ловушек) делает ваш план неработоспособным. Большая часть проблемы заключается в том, что вы пытаетесь измерить одну итерацию цикла; пример кода, который вы связываете, пытается измерить полный набор итераций (прочитайте часы перед запуском цикла, прочитайте его снова после выхода из цикла, не используйте printf() внутри цикла).

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

Что касается того, "какой элемент увеличивается"; arr - адрес буфера 1 МБ; arr[(i * 16) & lengthMod]++; заставляет (i * 16) * lengthMod генерировать смещение от этого адреса; это смещение - это адрес int, который увеличивается. Вы выполняете смену (i * 16 превратится в я < 4), логическое и дополнение, затем либо чтение/добавление/запись, либо однократное увеличение в зависимости от вашего процессора).

Изменить: Как описано, ваш код страдает от плохого отношения сигнал/шум (отношение сигнал/шум) из-за относительной скорости доступа к памяти (кэш или без кеша) и вызывающих функций только для измерения времени. Чтобы получить тайминги, которые вы сейчас получаете, я предполагаю, что вы изменили код, чтобы выглядеть примерно так:

int main() {
    int steps = 64 * 1024 * 1024;
    int arr[1024 * 1024];
    int lengthMod = (1024 * 1024) - 1;
    int i;
    double timeTaken;
    clock_t start;

    start = clock();
    for (i = 0; i < steps; i++) {
        arr[(i * 16) & lengthMod]++;
    }
    timeTaken = (double)(clock() - start)/CLOCKS_PER_SEC;
    printf("Time for %d: %.12f \n", i, timeTaken);
}

Это перемещает измерение вне цикла, поэтому вы не измеряете единый доступ (что было бы действительно невозможно), а вы измеряете доступ к steps.

Вы можете увеличить steps по мере необходимости, и это будет иметь прямое влияние на ваши тайминги. Поскольку время, которое вы получаете, слишком близко друг к другу, а в некоторых случаях даже инвертировано (ваше время колеблется между размерами, что мало вероятно из-за кеша), вы можете попробовать изменить значение steps на 256 * 1024 * 1024 или даже больше.

ПРИМЕЧАНИЕ. Вы можете сделать steps настолько большим, насколько вы можете поместиться в подписанный int (который должен быть достаточно большим), поскольку логический и гарантирует, что вы обертываете в своем буфере.

Ответ 2

После 10 минут поиска руководства по эксплуатации Intel и еще 10 минут кодирования я придумал это (для процессоров на базе Intel):

void i386_cpuid_caches () {
    int i;
    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;

        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"
        );
    }
}

Ссылка: http://download.intel.com/products/processor/manual/325462.pdf 3-166 Vol. 2A

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

Изменить: добавлен дескриптор типа кэша. Edit2: добавлен индикатор уровня кэша. Edit3: добавлена ​​дополнительная документация.

Ответ 3

Я знаю это! (На самом деле это очень сложно из-за предварительной выборки)

 for (times = 0; times < Max; time++) /* many times*/
     for (i=0; i < ArraySize; i = i + Stride)
           dummy = A[i]; /* touch an item in the array */

Изменение шага позволяет проверить свойства кешей. Посмотрев на график, вы получите ответы.

Посмотрите слайды 35-42 http://www.it.uu.se/edu/course/homepage/avdark/ht11/slides/11_Memory_and_optimization-1.pdf

Эрик Хейгерстен - действительно хороший учитель (а также действительно компетентный, был ведущим архитектором на солнце в какой-то момент), поэтому взгляните на остальные его слайды, чтобы получить более подробные объяснения!

Ответ 4

Чтобы ответить на ваш вопрос о странных цифрах выше 1 МБ, это довольно просто; политики кэширования, связанные с предсказанием ветвления, и тот факт, что кэш L3 используется совместно между ядрами.

Ядро i3 имеет очень интересную структуру кэша. На самом деле любой современный процессор. Вы должны прочитать о них по википедии; есть всевозможные способы решить "хорошо, мне, вероятно, это не понадобится...", тогда он может сказать: "Я поставлю его в кэш-память" или любое количество вещей. Тайм-ауты кэша L1-2-3 могут быть очень сложными на основе большого количества факторов и индивидуальных решений по дизайну.

Кроме того, все эти решения и многое другое (см. статьи в википедии по этому вопросу) должны быть синхронизированы между кэшами двух ядер. Методы синхронизации общего кэша L3 с отдельными кешами L1 и L2 могут быть уродливыми, они могут включать в себя отслеживание и повторное выполнение расчетов или другие методы. Очень маловероятно, что у вас когда-либо будет совершенно свободное второе ядро, и ничто не конкурирует за пространство кэша L3 и, таким образом, вызывает странность синхронизации.

В общем случае, если вы работаете над данными, скажем, со сверткой ядра, вы хотите убедиться, что он вписывается в кеш L1 и формирует ваш алгоритм вокруг этого. Кэш L3 на самом деле не предназначен для работы над набором данных так, как вы это делаете (хотя это лучше, чем основная память!)

Я клянусь, если бы мне был нужен алгоритм кэширования, я бы с ума сошел.

Ответ 5

Для бенчмаркинга с различными шагами вы можете попробовать lat_mem_rd из пакета lmbench, это open-source: http://www.bitmover.com/lmbench/lat_mem_rd.8.html

Я отправил свой порт для Windows в http://habrahabr.ru/post/111876/ - он довольно длинный, чтобы его копировать. Что два года назад я не тестировал его с использованием современных процессоров.

Ответ 6

Для окон вы можете использовать метод GetLogicalProcessorInformation.

Для linux вы можете использовать sysconf(). Вы можете найти допустимые аргументы для sysconf в /usr/include/unistd.h или /usr/include/bits/confname.h