Мне было поручено создать определенное количество промахов кэширования данных и пропусков кэша команд. Я смог обработать часть кэша данных без проблем.
Итак, я остался с созданием промахов кэша команд. Я не знаю, что их вызывает. Может ли кто-нибудь предложить метод их генерации?
Я использую GCC в Linux.
Как объяснили люди, миссия кэша команд концептуально совпадает с пропуском кэша данных - инструкции не находятся в кеше. Это связано с тем, что счетчик процессорных процессоров (ПК) переместился в место, которое не было загружено в кеш, или было вымыто из-за того, что кеш был заполнен, и эта строка кэша была выбрана для выселения (как правило, в последнее время используется).
Намного сложнее создать достаточно кода вручную, чтобы заставить пропустить команду, чем заставить пропустить кеш данных.
Один способ получить много кода, для небольших усилий - написать программу, которая генерирует исходный код.
Например, напишите программу для создания функции с огромным оператором switch (в C) [Warning, untested]:
printf("void bigswitch(int n) {\n switch (n) {");
for (int i=1; i<100000; ++i) {
printf(" case %d: n += %d;\n", n, n+i/2);
}
printf(" }\n return n;}\n");
Затем вы можете вызывать это из другой функции, и вы можете контролировать, насколько большой прыжок вдоль линии кэша он принимает.
Свойство оператора switch - это код, который может быть принудительно выполнен назад или в шаблонах, выбирая параметр. Таким образом, вы можете работать с механизмами предварительной выборки и прогнозирования или пытаться работать против них.
Тот же метод может быть применен для генерации множества функций, чтобы гарантировать, что кеш может быть "заблокирован" по своему усмотрению. Таким образом, у вас может быть bigswitch001, bigswitch002 и т.д. Вы можете называть это с помощью переключателя, который вы также генерируете.
Если вы можете сделать каждую функцию (приблизительно) некоторое количество строк i-cache в размере, а также генерировать больше функций, чем будет входить в кеш, тогда проблема генерации кэширования команд становится легче контролировать.
Вы можете точно определить, насколько велика функция, весь оператор switch или каждая ветвь оператора switch, путем сброса ассемблера (с использованием gcc -S) или objdump.o файла. Таким образом, вы можете "настроить" размер функции, отрегулировав количество операторов case:. Вы также можете выбрать, сколько строк кеша попало, путем разумного выбора параметра для bigswitchNNN().
В дополнение ко всем другим способам, упомянутым здесь, еще один очень надежный способ заставить пропустить кэширование команд - это самомодифицирующийся код.
Если вы пишете на страницу кода в памяти (при условии, что вы настроили ОС, чтобы разрешить это), то, конечно, соответствующая строка кэша команд сразу становится недействительной, и процессор вынужден ее повторно выполнить.
Это не предсказание ветки, которое, кстати, вызывает промахи icache, но просто ветвящиеся. Вы пропускаете кеш команды всякий раз, когда процессор пытается запустить инструкцию, которая еще не была запущена. Современный x86 достаточно умен, чтобы последовательно выполнять команды предварительной выборки, поэтому вы вряд ли пропустите icache, просто выполнив переход от одной инструкции к другой. Но любая ветвь (условная или другая) перескакивает на новый адрес из последовательности. Если новый адрес команды не был запущен в последнее время и не находится рядом с уже запущенным кодом, скорее всего, он будет отсутствовать в кэше, и процессор должен остановиться и дождаться, когда инструкции поступят из основной ОЗУ. Это точно так же, как кэш данных.
Некоторые очень современные процессоры (последние i7) могут смотреть на ближайшие ветки в коде и запускать icache, предварительно задавая возможные цели, но многие не могут (игровые консоли). Извлечение данных из основной ОЗУ в icache полностью отличается от этапа "выборки команд" в конвейере, что является предсказанием ветвления.
"Сбор данных" является частью конвейера выполнения ЦП и относится к выводу кода операции из icache в блок выполнения ЦП, где он может начать декодирование и выполнять работу. Это отличается от "кэширования команд", который должен произойти во многих циклах раньше, и включает в себя схему кэширования, запрашивающую основной блок памяти для отправки нескольких байтов по шине. Первое - это взаимодействие между двумя этапами конвейера CPU. Второе - это взаимодействие между конвейером и кешем памяти и основной ОЗУ, что является гораздо более сложным элементом схемы. Имена смешаны схожими, но они полностью отдельные операции.
Таким образом, еще один способ вызвать пропуски кэша команд - написать (или создать) множество действительно больших функций, так что ваш сегмент кода будет огромным. Затем вызывайте дико от одной функции к другой, так что с точки зрения CPU вы делаете сумасшедшие GOTO по всей памяти.
Для вашего проекта требуется знание аппаратного кэша ваших целевых систем, включая, помимо прочего, его размер кеша (общий размер кеша), размер строки кэша (наименьшая кешируемая сущность), ассоциативность и политика записи и замены. Любой действительно хороший алгоритм, предназначенный для проверки производительности кэшей, должен учитывать все это, так как нет единого общего алгоритма, который бы эффективно тестировал все конфигурации кэша, хотя вы можете разработать эффективный параметризованный генератор тестовой процедуры, который может генерировать подходящую тестовую процедуру, достаточную для подробностей о конкретной архитектуре кеша целей. Несмотря на это, я думаю, что мое предложение ниже - довольно хороший общий тест, но сначала я хотел бы упомянуть:
Вы упомянули, что у вас есть тест кэша рабочих данных, который использует "большой массив целых чисел a [100].... [который обращается] к элементам таким образом, что расстояние между этими двумя элементами больше, чем кеш размер линии (32 байта в моем случае)." Мне любопытно, как вы определили, что ваш тестовый алгоритм работает, и как вы определили, сколько промахов кэша данных является результатом вашего алгоритма, в отличие от промахов, вызванных другими стимулами. Действительно, с тестовым массивом размером 100 * sizeof (int) ваша тестовая область данных составляет всего 400 байт на большинстве платформ общего назначения сегодня (возможно, 800 байт, если вы на 64-битной платформе или 200 байт, если вы используете 16-битная платформа). Для подавляющего большинства архитектур кэша весь тестовый массив будет входить в кеш много раз, что означает, что рандомизированные обращения к массиву будут приводить весь массив в кеш где-то вокруг (400/cache_line_size) * 2 доступа, и каждый доступ после этого будет хитом кеша, независимо от того, как вы заказываете доступ, если не появляется какое-либо прерывание таймера аппаратного обеспечения или ОС, и сбрасывает некоторые или все ваши кэшированные данные.
Что касается кэша команд: другие предложили использовать большой переключатель() - case case или вызовы функций для функций в разрозненных местах, ни один из которых не будет предсказуемо эффективным без тщательного (и я имею в виду ВНИМАТЕЛЬНО), определяющего размер код в соответствующих случаях, ветки или местоположения и размеры распределенных функций. Причиной этого является то, что байты всей памяти "складываются" (технически "псевдоним друг друга" ) в кеше в полностью предсказуемом шаблоне. Если вы тщательно контролируете количество инструкций в каждой ветки оператора switch() - case, вы можете получить что-то с вашим тестом, но если вы просто бросаете большое количество неизбирательного количества инструкций в каждом, вы не представляете, как они будут складываться в кеш и какие случаи switch() - case case псевдонимы друг друга, чтобы использовать их для выселения друг друга из кэша.
Я предполагаю, что вы не слишком знакомы с ассемблерным кодом, но вы должны поверить мне здесь, этот проект кричит об этом. Поверьте мне, я не один, чтобы использовать ассемблерный код, где его не вызывали, и я настоятельно предпочитаю программирование в OO С++, используя STL и полиморфные иерархии ADT, когда это возможно. Но в вашем случае на самом деле у них нет другого надежного способа сделать это, и сборка даст вам абсолютный контроль над размерами блоков кода, которые вам действительно нужны, чтобы иметь возможность эффективно генерировать определенные коэффициенты попадания кеша. Вам не обязательно становиться экспертом по сборке, и вам, вероятно, даже не нужно будет изучать инструкции и структуру, необходимые для внедрения пролога и эпилога на языке C (Google для "C-callable assembly function" ). Вы пишете прототипы функций extern "C" для своих функций сборки, и вы уходите. Если вам интересно узнать какую-либо сборку, чем больше логики теста вы вставляете в функции сборки, тем меньше эффекта "Гейзенберга" вы накладываете на свой тест, так как вы можете тщательно контролировать, куда идут инструкции по контролю тестирования (и, следовательно, их влияние на кеш инструкций). Но для основной части вашего тестового кода вы можете просто использовать кучу инструкций "nop" (кэш команд действительно не заботится о том, какие инструкции он содержит), и, возможно, просто поместите инструкцию процессора "return" внизу каждого блока код.
Теперь скажем, что кеш вашей команды - 32 КБ (довольно чертовски маленький по сегодняшним стандартам, но, возможно, все еще распространен во многих встроенных системах). Если ваш кеш является 4-сторонним ассоциативным, вы можете создать восемь отдельных контент-идентичных 8K-сборочных функций (которые, мы надеемся, заметили, это код на 64 КБ, вдвое больший размер кеша), основная часть которого - всего лишь куча инструкций NOP, Вы заставляете их падать один за другим в памяти (обычно просто определяя каждый из них в исходном файле). Затем вы вызываете их из функции тестового контроля с использованием тщательно вычисленных последовательностей для генерации любого желаемого коэффициента попадания в кеш (с довольно гранулярностью курса, так как каждая функция имеет длину 8K). Если вы вызываете 1-й, 2-й, 3-й и 4-й функции один за другим, вы знаете, что вы заполнили весь кеш этими кодами тестовых функций. Вызов любого из них снова в этот момент не приведет к провалу кэша команд (за исключением строк, выведенных собственными инструкциями функций контрольного контроля), но называя любой из других (5, 6, 7 или 8), позволяет просто выберите 5-е) выселите одного из других (хотя тот, который выселен, зависит от политики замены кэшей). На данный момент, единственный, кого вы можете назвать и знать, что вы не выбрали другого, - это тот, который вы только что назвали (пятый), и единственные, кого вы можете назвать и знаете, ВЫ ВЫБИРАЕТЕ другое - это тот, которого вы еще не называли (6-й, 7-й или 8-й). Чтобы сделать это проще, просто сохраните статический массив, размер которого совпадает с количеством тестовых функций, которые у вас есть. Чтобы вызвать выселение, вызовите функцию в конце массива и переместите указатель в верхнюю часть массива, сдвинув остальные. Чтобы НЕ вызывать выселение, вызовите тот, который вы недавно вызвали (тот, который находится в верхней части массива, не забудьте НЕ сдвигать остальные в этом случае!). Сделайте некоторые варианты этого (возможно, сделайте 16 отдельных функций сборки 4K), если вам нужна более тонкая детализация. Конечно, все это зависит от размера логики контрольного контроля, несущественного по сравнению с размером каждого ассоциативного "пути" кэш-памяти; для более позитивного контроля вы могли бы поместить логику контрольного контроля в собственные функции тестирования, но для идеального управления вам нужно полностью разработать логику управления без внутреннего разветвления (только ветвление в конце каждой функции сборки), но я думаю, что остановить здесь, поскольку это, вероятно, слишком усложняет ситуацию.
Отключенная манжета и не протестированная, вся одна из функций сборки для x86 может выглядеть так:
myAsmFunc1:
nop
nop
nop # ...exactly enough NOPs to fill one "way" of the cache
nop # minus however many bytes a "ret" instruction is (1?)
.
.
.
nop
ret # return to the caller
Для PowerPC это может выглядеть так же (также не проверено):
myAsmFunc1:
nop
nop
nop # ...exactly enough NOPs to fill one "way" of the cache
. # minus 4 bytes for the "blr" instruction. Note that
. # on PPC, all instructions (including NOP) are 4 bytes.
.
nop
blr # return to the caller
В обоих случаях прототипы С++ и C для вызова этих функций:
extern "C" void myAsmFunc1(); // Prototype for calling from C++ code
void myAsmFunc1(void); /* Prototype for calling from C code */
В зависимости от вашего компилятора вам может потребоваться подчеркнуть перед именем функции в самом коде сборки (но не в прототипе функции С++/C).
Для пропусков кэша команд вам необходимо выполнить сегменты кода, которые находятся далеко друг от друга. Разделение логики между несколькими вызовами функций было бы одним из способов сделать это.
Цепочка if if else в непредсказуемых условиях (например, входные или случайно сгенерированные данные) с количеством инструкций как в случае if, так и в другом случае, размер которого больше, чем строка кэша.