Как я могу вызвать пропущенное кэширование команд?

Question

Мне поручено генерировать определенное количество промахов кэширования данных и промахов кэша команд. Я смог обработать часть кеша данных без проблем.

Так что я остался с созданием промахов в кэше команд. Я не знаю, что их вызывает. Может ли кто-нибудь предложить метод их создания?

Я использую GCC в Linux.

Answer 1

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

Answer 2

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

Answer 3

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

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

Один из способов получить много кода, для небольших усилий - написать программу, которая генерирует исходный код.

Например написать программу для создания функции с огромным заявлением переключателя (в C) [Внимание, непроверенное]:

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-кеше в размере, а также генерировать больше функций, чем будет входить в кеш, тогда проблема генерации кэширования команд становится проще в управлении.

Вы можете видеть, насколько велика функция, весь оператор switch или каждая ветвь оператора switch, путем сброса ассемблера (с использованием gcc -S) или objdump .o-файла. Таким образом, вы можете «настроить» размер функции, отрегулировав количество операторов case:. Вы также можете выбрать, сколько строк кеша попало, путем разумного выбора параметра для bigswitchNNN().

Answer 4

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

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

Это не разветвляется прогноза, который вызывает ICACHE промах, кстати, а просто ветвления. Вы пропускаете кеш команды всякий раз, когда процессор пытается запустить инструкцию, которая еще не была запущена. Современный x86 достаточно умен, чтобы последовательно выполнять команды предварительной выборки, поэтому вы вряд ли пропустите icache, просто выполнив переход от одной инструкции к другой. Но любая ветвь (условная или другая) перескакивает на новый адрес из последовательности. Если новый адрес команды не был запущен в последнее время и не находится рядом с уже запущенным кодом, скорее всего, он будет отсутствовать в кэше, и процессор должен остановиться и дождаться, когда инструкции поступят из основной ОЗУ. Это точно так же, как кэш данных.

Некоторые очень современные процессоры (последние i7) могут просматривать предстоящие ветви в коде и запускать icache, предварительно набирая возможные цели, но многие из них не могут (игровые консоли). Извлечение данных из основной ОЗУ в icache полностью отличается от этапа «выборки команд» для конвейера, который является тем, что связано с прогнозом.

«Извлечение команд» является частью конвейера выполнения ЦП и относится к выводу кода операции из icache в блок выполнения ЦП, где он может начать декодирование и выполнять работу. Это отличается от «кэширования команд», который должен произойти во многих циклах раньше, и включает в себя схему кэширования, запрашивающую основной блок памяти для отправки нескольких байтов по шине. Первое - это взаимодействие между двумя этапами конвейера CPU. Второе - это взаимодействие между конвейером и кешем памяти и основной ОЗУ, что является гораздо более сложным элементом схемы. Названия схожу схожим образом, но они являются полностью отдельными операциями.

Таким образом, еще один способ вызвать пропуски кэша команд - написать (или сгенерировать) множество действительно больших функций, чтобы ваш сегмент кода был огромным. Затем вызывайте дико от одной функции к другой, так что с точки зрения CPU вы делаете сумасшедшие GOTO по всей памяти.

Answer 5

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

Вы упомянули, что у вас есть тест кэша рабочих данных, который использует «большой массив целых чисел a [100]. ... [который обращается] к элементам таким образом, что расстояние между двумя элементами больше, чем размер кеш-строки (32 байта в моем случае). «Мне любопытно, как вы определили, что ваш тестовый алгоритм работает и как вы определили, сколько промахов кэша данных является результатом вашего алгоритма, в отличие от промахов, вызванных другими стимулами. Действительно, с тестовым массивом размером 100 * sizeof (int) ваша тестовая область данных составляет всего 400 байт на большинстве платформ общего назначения сегодня (возможно, 800 байтов, если вы на 64-битной платформе или 200 байтов, если вы используя 16-битную платформу). Для подавляющего большинства архитектур кэша весь тестовый массив будет входить в кеш много раз, что означает, что рандомизированные обращения к массиву будут приводить весь массив в кеш где-то вокруг (400/cache_line_size) * 2 доступа, и каждый доступ после этого будет хитом кеша, независимо от того, как вы заказываете свои обращения, если не произойдет прерывание таймера аппаратного или программного обеспечения OS и сброс некоторых или всех ваших кэшированных данных.

Что касается кэша инструкций: другие предложили использовать большой оператор switch() - case case или вызовы функций для функций в разрозненных местах, ни один из которых не будет предсказуемо эффективным без тщательного (и я имею в виду ВНИМАТЕЛЬНО) проектирования размера кода в соответствующих ветвях или местоположениях & размеров распределенных функций. Причиной этого является то, что байты всей памяти «складываются» (технически «псевдоним друг друга») в кеше в полностью предсказуемом шаблоне. Если вы тщательно контролируете количество инструкций в каждой ветви оператора switch() - case, вы можете получить что-то с вашим тестом, но если вы просто бросаете большое количество неизбирательного количества инструкций в каждом, вы не представляете, как они будут складываться в кеш и какие случаи switch() - case case псевдонимы друг друга, чтобы использовать их для высылки друг друга из кеша.

Я предполагаю, что вы не слишком знакомы с ассемблером, но вы должны поверить мне здесь, этот проект кричит об этом. Поверьте мне, я не один, чтобы использовать ассемблерный код там, где его не вызывают, и я настоятельно предпочитаю программирование в OO C++, используя STL & полиморфные ADT-иерархии, когда это возможно. Но в вашем случае действительно нет другого надежного способа сделать это, и сборка даст вам абсолютный контроль над размерами блоков кода, которые вам действительно нужны, чтобы иметь возможность эффективно генерировать определенные коэффициенты попадания кэша. Вам не обязательно становиться экспертом по сборке, и вам, вероятно, даже не нужно будет изучать инструкции &, необходимые для реализации прологового кода C-языка & (Google для «C-callable assembly function»). Вы пишете прототипы функций extern «C» для своих функций сборки, и вы уходите. Если вам интересно узнать какую-либо сборку, чем больше логики теста вы вставляете в функции сборки, тем меньше эффекта «Гейзенберга» вы накладываете на свой тест, так как вы можете тщательно контролировать, куда идут инструкции по контролю тестирования (и, следовательно, их влияние на кеш инструкций). Но для большей части вашего тестового кода вы можете просто использовать кучу инструкций «nop» (кэш команд на самом деле не заботится о том, какие инструкции он содержит), и, возможно, просто поместите инструкцию «возврат» вашего процессора внизу каждой блок кода.

Теперь предположим, что кеш вашей команды составляет 32 КБ (довольно неплохо по сегодняшним меркам, но, возможно, все еще распространено во многих встроенных системах). Если ваш кеш является 4-сторонним ассоциативным, вы можете создать восемь отдельных контент-идентичных 8K-сборочных функций (которые, мы надеемся, заметили, это код на 64 КБ, вдвое больший размер кеша), основная часть которого - всего лишь куча инструкций NOP , Вы заставляете их падать один за другим в памяти (обычно просто определяя каждый из них в исходном файле). Затем вы вызываете их из функции тестового контроля с использованием тщательно вычисленных последовательностей для генерации любого желаемого коэффициента попадания в кеш (с довольно гранулярностью курса, так как каждая функция имеет длину 8K). Если вы звоните 1-й, 2-й, 3-й и 4-й функции один за другим, вы знаете, что вы заполнили весь кеш кодом этих тестовых функций. Вызов любого из них снова в этот момент не приведет к провалу кеша команд (за исключением строк, выведенных собственными инструкциями функции контроля), но называя любой из других (5, 6, 7 или 8, давайте просто выберите пятый) выселите одного из других (хотя тот, который выселен, зависит от политики замены вашего кеша). На данный момент, единственный, кого вы можете назвать и знать, НЕ ВЫБИРАЕТЕГО, - это тот, который вы только что назвали (пятый), и единственные, кого вы можете назвать и знаете, ВЫ ВЫБИРАЕТЕ, (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++ и прототипы C для вызова этих функций будет:

extern "C" void myAsmFunc1(); // Prototype for calling from C++ code 
void myAsmFunc1(void);   /* Prototype for calling from C code */ 

В зависимости от вашего компилятора вам может потребоваться подчеркнуть перед именем функции в самом коде сборки (но не в прототипе функции C++/C).