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

uint32_t* data = ...;
// Последовательный порядок.
data[0] + data[1] + data[2] + ...
// Случайный порядок.
data[67] + data[69420] + data[42] + ...
// Самый медленный порядок.
data[A] + data[B] + data[C] + ...

Спойлер: можно сделать процесс на >30% медленнее, чем при паттерне случайного доступа.

Основные условия:

• Учитывается только время, затраченное на выполнение функции accumulator. Продолжительность создания позиций в расчёт не берётся.

• Сама функция accumulator имеет фиксированный вид; массив data заполняется случайным образом, и менять можно только содержимое positions:

constexpr int ELEMENT_COUNT = (1 << 16) * (PAGE_SIZE / sizeof(uint32_t));  // 2^26
/* data содержит целые числа, которые нужно просуммировать.
 * positions отражает паттерн доступа, который используется для сложения чисел.
 * Ожидается переполнение, но нас же не интересует реальная сумма?
 */
uint32_t accumulator(uint32_t const* data, uint32_t const* positions) {
    uint32_t total = 0;
    for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) {
        uint32_t pos = positions[i];
        total += data[pos];
    }
    return total;
}

• Длительность выполнения accumulator измеряется в тиках TSC с помощью инструкции rdtsc.

Дополнительные условия:

• Используется 2²⁶ целых числа: всего 65 536 страниц, каждая из которых содержит по 1024 чисел. Эти значения я выбрал только для того, чтобы не затягивать выполнение на моей машине.

• Большие страницы отключены.

• Все измерения производятся на моей системе:

Весь код лежит здесь. Запускайте его командой g++ -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out. Не поленитесь открыть slowest.cc и выполнить код у себя.

Наша цель — найти такую перестановку positions, при которой выполнение займёт максимум времени. Начнём с самого простого паттерна доступа:

void linear(uint32_t const* data, uint32_t* positions) {
    for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) {
        positions[i] = i;
    }
}

Это самый быстрый вариант — на выполнение ушло 133М (132 752 394) тиков. Результат ожидаемый, так как процессоры хорошо оптимизированы под последовательный доступ.

Но индексы доступа можно и рандомизировать.

void fisher_yates_shuffle(uint32_t const* data, uint32_t* positions) {
    linear(data, positions);
    uint32_t remaining = ELEMENT_COUNT;
    for (uint32_t i = 0; i < ELEMENT_COUNT; ++i) {
        uint32_t random = rand() % remaining;
        uint32_t tmp = positions[i];
        positions[i] = positions[i + random];
        positions[i + random] = tmp;
        --remaining;
    }
}

Теперь процессор не может предсказать, к каким данным будет следующее обращение. В итоге на всё про всё ушло 1,57B (1 572 108 618) тиков, то есть в 10 с лишним раз медленнее, чем при линейном доступе. А можно ещё медленнее? Конечно! Далее мы построим самую сложную перестановку, начав с самого простого способа ухудшения.

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

void separated_by_a_cacheline(uint32_t const* data, uint32_t* positions) {
    constexpr int element_count_per_cacheline =
        CACHELINE_SIZE / sizeof(uint32_t);
    constexpr int cacheline_count = ELEMENT_COUNT / element_count_per_cacheline;
    static_assert(ELEMENT_COUNT % element_count_per_cacheline == 0);
    int current = 0;
    for (int element_index = 0; element_index < element_count_per_cacheline;
         ++element_index) {
        for (int cacheline_index = 0; cacheline_index < cacheline_count;
             ++cacheline_index) {
            positions[current] =
                cacheline_index * element_count_per_cacheline + element_index;
            ++current;
        }
    }
}

Это ужасный паттерн доступа, поскольку здесь при каждом обращении используется лишь одно 4-байтовое число из 64-байтовой строки кэша. К моменту возвращения к той же самой строке полезные данные, которые можно было бы использовать повторно, уже окажутся из неё вытеснены. Естественно, это ведёт к огромной просадке быстродействия: 719М (718 804 156) тиков, то есть уже в 4 раза медленнее линейного случая.

Тем не менее при доступе к элементам, находящимся в разных строках кэша, блок аппаратной предвыборки всё равно может распознавать простой потоковый паттерн в data и начинать запрашивать будущие строки кэша до фактического запроса на их загрузку. Но при этом многие блоки предвыборки на платформах Intel не выходят за рамки 4-килобайтной страницы. Я предполагаю, что при переходе через границу страницы необходимо переводить виртуальный адрес в физический, а смежные виртуальные страницы не обязательно будут отображаться в смежные физические. Поэтому выполнение упреждающей предвыборки между страницами грозит ошибками, и из практических соображений не используется.

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

void separated_by_a_page(uint32_t const* data, uint32_t* positions) {
    constexpr int element_count_per_page = PAGE_SIZE / sizeof(uint32_t);
    constexpr int page_count = ELEMENT_COUNT / element_count_per_page;
    static_assert(ELEMENT_COUNT % element_count_per_page == 0);
    int current = 0;
    for (int element_index = 0; element_index < element_count_per_page;
         ++element_index) {
        for (int page_index = 0; page_index < page_count; ++page_index) {
            positions[current] =
                page_index * element_count_per_page + element_index;
            ++current;
        }
    }
}

Как итог — значительное замедление до 1,41B (1 411 153 154) тиков. В этом случае мы обхитрили аппаратный блок предвыборки, но здесь присутствует и ещё один эффект. В большинстве домашних ПК кэш имеет наборно-ассоциативную структуру. Это означает, что конкретная строка может быть помещена только в строго определённый набор (set), который содержит несколько каналов (ways).

В моей машине объём кэша L1d составляет 48 КБ на ядро: по 12 каналов в каждом из 64 наборов. Так как наборов всего 64, данные по адресу А и данные по адресу А + 4096 байт (64 набора 64 байта строки кэша) отображаются в тот же набор L1d и должны соперничать за один из 12 доступных каналов. А поскольку мы шагаем от страницы к странице (4096 байт), каждый внутренний цикл постоянно попадает в один и тот же набор вместо того, чтобы распределяться по всем 64. И это важно, так как в этом наборе есть всего 12 каналов. Как только за него начинают конкурировать более 12 активных строк, процессору приходится раз за разом их вытеснять и повторно загружать, что ведёт к промахам из-за конфликтов. Технически размер кэша равен 48 КБ, но для этого паттерна доступа его полезная часть составляет всего 768 Б (12 каналов 64 Б).

А теперь немного абстрагируемся и рассмотрим этот паттерн более обобщённо:

page 0, cacheline 0, elem 0
page 1, cacheline 0, elem 0
page 2, cacheline 0, elem 0
…
page 65534, cacheline 0, elem 0
page 65535, cacheline 0, elem 0
page 0, cacheline 0, elem 1
page 1, cacheline 0, elem 1
page 2, cacheline 0, elem 1
...

После обращения к 65 536 строкам кэша происходит возврат к исходной строке. В таком случае говорят, что расстояние между повторными использованиями строки кэша (cache line reuse distance) равно 65 536 — то есть после 65 536 обращений мы снова возвращаемся к той же строке, с которой эти обращения начали. И этот алгоритм тоже можно ухудшить, если при переходе к каждой новой странице перестать обращаться к той же строке:

void separated_by_a_page_and_cacheline(uint32_t const* data,
                                       uint32_t* positions) {
    constexpr int elements_per_cacheline = CACHELINE_SIZE / sizeof(uint32_t);
    constexpr int elements_per_page = PAGE_SIZE / sizeof(uint32_t);
    constexpr int cacheline_per_page = PAGE_SIZE / CACHELINE_SIZE;
    constexpr int page_count = ELEMENT_COUNT / elements_per_page;

    static_assert(ELEMENT_COUNT % elements_per_page == 0);

    int current = 0;
    for (int element_index_in_cacheline = 0;
         element_index_in_cacheline < elements_per_cacheline;
         ++element_index_in_cacheline) {
        for (int cacheline_index_in_page = 0;
             cacheline_index_in_page < cacheline_per_page;
             ++cacheline_index_in_page) {
            for (int page_index = 0; page_index < page_count; ++page_index) {
                positions[current++] =
                    page_index * elements_per_page +
                    cacheline_index_in_page * elements_per_cacheline +
                    element_index_in_cacheline;
            }
        }
    }
}

Теперь расстояние между повторными использованиями кэша увеличилось до 4B (65 536 страниц * 4096 (размер страницы) / 64 (размер строки кэша)), и паттерн доступа выглядит так:

page 0, cacheline 0, elem 0
page 1, cacheline 0, elem 0
page 2, cacheline 0, elem 0
…
page 65534, cacheline 0, elem 0
page 65535, cacheline 0, elem 0
page 0, cacheline 1, elem 0
page 1, cacheline 1, elem 0
page 2, cacheline 1, elem 0
...

Однако при выполнении операции с переходом по страницам и строкам кэша мы укладываемся в те же 1,41B (1 408 519 172) тиков, что весьма странно, так как ожидалось ухудшение.

Теперь расстояние между повторными использованиями строки кэша выросло до 4М (PAGE_COUNT PAGE_SIZE / CACHELINE_SIZE). Но при этом мы используем только ядро 3, и по строке L2 L#3 (2560KB) + L1d L#3 (48KB) + … видно, что это ядро имеет 2,5 МБ кэша L2 и 48 КБ кэша L1. Перебрав 65 536 страниц, мы обратились к 4 МБ данных. Это больше, чем ёмкость L1/L2 отдельного ядра, а значит, следующая нужная нам строка вряд ли по-прежнему будет находиться в этом кэше. Она может всё ещё присутствовать в L3, но L3 работает медленнее и подчиняется своей логике ассоциирования и вытеснения. В нашем случае рассчитывать на попадание в собственный кэш следует, только если расстояние между повторными использованиями строки будет меньше ~40 тысяч ((2560+48)*1024/64).

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

template <int page_stride>
void separated_by_stride_pages_and_cacheline(uint32_t const* data,
                                             uint32_t* positions) {
    constexpr int elements_per_cacheline = CACHELINE_SIZE / sizeof(uint32_t);
    constexpr int elements_per_page = PAGE_SIZE / sizeof(uint32_t);
    constexpr int cacheline_per_page = PAGE_SIZE / CACHELINE_SIZE;
    constexpr int page_count = ELEMENT_COUNT / elements_per_page;

    static_assert(ELEMENT_COUNT % elements_per_page == 0);
    static_assert(page_stride > 0);

    int current = 0;
    for (int element_index_in_cacheline = 0;
         element_index_in_cacheline < elements_per_cacheline;
         ++element_index_in_cacheline) {
        for (int cacheline_index_in_page = 0;
             cacheline_index_in_page < cacheline_per_page;
             ++cacheline_index_in_page) {
            for (int page_start = 0;
                 page_start < page_stride && page_start < page_count;
                 ++page_start) {
                for (int page_index = page_start; page_index < page_count;
                     page_index += page_stride) {
                    positions[current++] =
                        page_index * elements_per_page +
                        cacheline_index_in_page * elements_per_cacheline +
                        element_index_in_cacheline;
                }
            }
        }
    }
}

Обновлённый паттерн:

page 0, cacheline 0, elem 0
page N, cacheline 0, elem 0
page 2N, cacheline 0, elem 0
…
page 0, cacheline 1, elem 0
page N, cacheline 1, elem 0
page 2N, cacheline 1, elem 0
…
page 1, cacheline 0, elem 0
page N + 1, cacheline 0, elem 0
page 2N + 1, cacheline 0, elem 0
…

Вдобавок к фактическим шагам на N страниц мы также построим график, отражающий количество затрачиваемых на каждый шаг тиков:

При таком паттерне наихудший результат наблюдается при шаге через 8 страниц — даже хуже, чем при случайном доступе. Если выполнить операцию отдельно при -DSTRIDE=8, общее число тиков составит 2,06B (2 058 425 640). В графе наблюдается и много других интересных эффектов, связанных с памятью, но сегодня мы на них отвлекаться не будем. Одной из причин такого всплеска задержки является трансляция адресов, поскольку при этом шаге нужные записи таблиц страниц перестают попадать в одну строку кэша.

При обращении к данным по некоторому адресу фактически происходит обращение к их виртуальному адресу. За трансляцию этого виртуального адреса в физический отвечает модуль управления памятью (MMU). Эта концепция относится к базовой программе по устройству операционных систем, так что подробно разбирать мы её не станем. Нас интересует именно конкретная структура данных, используемая MMU и называемая запись таблицы страниц (Page Table Entry, PTE). В ней хранится физический номер фрейма страницы, соответствующий виртуальной странице, а также флаги и прочие метаданные. Размер записи PTE составляет 8 байт, а значит, в строку кэша вмещается 8 таких записей.

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

Но это ещё не всё. Мы уже забили кэш, уничтожили блок предвыборки, лишили процессор возможности переиспользовать одну и ту же строку кэша и довели MMU до предела, заставив его при каждом обращении выполнять обход таблиц. Последней же нашей хитростью станет саботаж контроллера DRAM.

Типичная оперативная память организована по каналам, рангам, микросхемам, банкам, строкам и столбцам. В качестве наглядного примера рассмотрим схему модуля DIMM ниже. Каждый модуль такой памяти может включать один или более рангов, которые, в свою очередь, содержат по несколько микросхем.

Показанный на фото модуль DIMM включает два ранга — каждый по восемь 8-разрядных микросхем DRAM. Когда контроллер памяти обращается к рангу, все эти чипы работают параллельно, и каждый из них отвечает за свои 8 бит на общей 64-битной шине данных. Таким образом, 64-битное слово распределяется по всем этим чипам, а не хранится в каком-то одном.

Но в целях этого эксперимента нас интересуют только банки. Каждая микросхема содержит по несколько банков памяти, которые, в свою очередь, содержат по множеству строк, представляющих собой последовательные биты данных. При доступе к данным по конкретному адресу в DRAM контроллер памяти «активирует» нужную строку и копирует её в буфер. Затем уже из этого буфера он извлекает те самые 8 бит данных из интересующего нас столбца.

Прежде чем банк сможет обратиться к данным из другой строки, он должен закрыть текущую строку с помощью операции предзаряда, после чего уже открыть новую. В результате такого постоянного переключения между строками внутри одного банка в строковом буфере возникают конфликты, замедляющие реагирование контроллера памяти на запросы данных. И напротив, если нас интересует именно та строка, которая сейчас открыта в банке, происходит попадание в буфер. Как мы уже знаем, в ранге присутствует несколько банков, поэтому строки из разных банков могут открываться одновременно, а нам это не нужно. На YouTube-канале Branch Education есть прекрасное видео об устройстве DRAM. Ниже я привёл схематичное сопоставление задержки при попадании в буфер и при промахе.

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

И реализуем мы это так: будем транслировать номер виртуальной страницы в номер физической (physical frame number, PFN) при помощи таблицы страниц с сохранением смещения страницы для формирования физического адреса. После этого декодируем полученный адрес в соответствии со схемой адресации DRAM для определения канала, ранга, группы банков, конкретного банка, строки и столбца. Чтобы создать самый медленный паттерн доступа, мы будем постоянно обращаться к разным строкам одного и того же банка. Это сведёт на нет локальность строкового буфера и возможность параллельного обращения к разным банкам, заставив контроллер выполнять операцию предзаряда и открывать новую строку практически при каждом запросе.

Тем не менее механизм отображения физических адресов в каналы, ранги, банки и строки в документации не описывается и зависит от платформы. На него влияет модель процессора, тип памяти, настройки BIOS/прошивки, конфигурация каналов и рангов, а также хэширование адресов. И хотя можно было бы использовать инструменты вроде DRAMA или Sudoku, мне не удалось завести их на своей машине, так что придётся обойтись приблизительной оценкой. Вооружившись работой по DRAMA и выполнив серию локальных экспериментов, я остановился на следующих настройках:

constexpr uint32_t DRAM_BANK_GROUP_COUNT = 4;
constexpr uint32_t DRAM_BANK_COUNT_PER_GROUP = 4;
constexpr uint32_t DRAM_ROW_SHIFT = 18;  // Подобрано экспериментально в диапазоне от 15 до 19.
DramLocation physical_address_to_dram_location(uint64_t physical_address,
                                               uint32_t page_index) {
    auto get_bit = [&](uint32_t index) {
        return (physical_address >> index) & 1;
    };

    uint64_t bg0 = get_bit(7) ^ get_bit(14);
    uint64_t bg1 = get_bit(15) ^ get_bit(19);
    uint64_t bg = bg1 * 2 + bg0;
    uint64_t ba0 = get_bit(17) ^ get_bit(21);
    uint64_t ba1 = get_bit(18) ^ get_bit(22);
    uint64_t ba = ba1 * 2 + ba0;

    return {
        .bank_index = bg * DRAM_BANK_COUNT_PER_GROUP + ba,
        .rank = 0,     // Используется ранг 0.
        .channel = 0,  // Используется один канал.
        .row_index = physical_address >> DRAM_ROW_SHIFT,
        .page_index = page_index,
    };
}

После всех этих манипуляций мы видим, что число тиков слегка возросло до 2,08B (2 082 308 014). Помимо неправильного использования хэша группы банков и хэша самих банков, а также приблизительной оценки сдвига строк, мы ещё и шагаем по памяти через 8 страниц. Это значит, что данные между последовательными обращениями оказываются разнесены на 32 КБ и никак не попадают в одну и ту же строку DRAM. Однако и этот паттерн доступа не вызывает достаточно конфликтов. Единственным, что ещё можно предпринять, является одновременное обращение только к одному банку. Вот только ввиду характерной для Intel схемы хэширования групп банков обращение всё равно происходит к нескольким сразу, так что полноценно воспользоваться этой уловкой не получится. Но мне понравилась сама идея изменения паттерна доступа к памяти, поэтому я решил её здесь оставить.

После одновременного выполнения всех тестов вывод получился таким:

~/Developer/rough/slowest main* ⇡
❯ g++ -DSTRIDE=8 -std=c++2a -O3 slowest.cc && taskset -c 3 sudo ./a.out
linear:                                                132752394
fisher_yates_shuffle:                                 1572108618
separated_by_a_cacheline:                              718804156
separated_by_a_page:                                  1411153154
separated_by_a_page_and_cacheline:                    1408519172
stride=8 separated_by_stride_pages_and_cacheline:     2058425640
separated_by_stride_bank_conflicts_and_cacheline:     2082308014

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

Напоследок:

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

• Если тематика статьи оказалась для вас интересной, рекомендую ознакомиться с тематическими задачками на платформе highload.fun. Собственно, именно она и подтолкнула меня к написанию поста.

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

  

• Уверен, некоторые умельцы смогут найти и ещё более медленный паттерн. У кого получится — делитесь в комментариях!